9

状況は次のとおりです。
実際には数値であり、かなり大きくなる可能性のある文字列を格納するリストがあります（数億のアイテム）。
テキストである追加情報を表示するオプションがあるため、数値を文字列として保存します。

これは保存に大量のメモリを必要とするため、最大 500 万個のアイテムのみを保存することにしました。(これには約 250 ～ 300MB しかかかりません)。

リストは、計算の出力によって埋められます。数値が見つかった場合、それはリストに追加されます。この数値は常に既存のアイテムよりも大きくなります。

リストが 5 ミルに達したら、最初のアイテムを削除して、新しいアイテムをリストに追加します。

お気に入り：

    // Why is this so freaking slow???
    if (_result.Count == 5000000)
        _result.RemoveAt(0);
    _result.Add(result);

コメントでわかるように、これは非常に非常に遅いです。パフォーマンスが 15 分の 1 に低下しました。2分かかったところが、今では約30分かかります。

私はlinqのようなものをいくつか試しました.Skip(1).ToListが、それはリストを再作成するため、さらに遅くなります。

リストは正しい順序に保つ必要があるため、インデックスによる上書きはオプションではありません (適切な回避策を説明できる場合を除きます)。

私の質問:
これを行う適切な方法はありますか?

約 10000000000 の数字をチェックする必要があるかもしれないので、ここでのパフォーマンスが本当に必要です。もちろん、これには1日かかるかもしれませんが、1か月は少し長すぎます:(。

追加情報が必要な場合は、お気軽にお問い合わせください。喜んで提供いたします。

解決策:
これは O(1) を実行します

    // Set the _result
    Queue<object> _result = new Queue<object>(5000000);

    /// Inside the method
    // If the count has reach it's max, dequeue the first item
    if (_result.Count == 5000000)
        _result.Dequeue();
    _result.Enqueue(result);
4

5 に答える 5

4

アイテムを再注文したことはありますか？そうしないと、循環キューが非常にうまく機能します。

System.Collections.Generic.Queueは1つで、ダブルチェックしました。

キューの利点を拡張するために、これはRemoveAt（大まかに）実装です。

for (int i = 1; i < count; i++)
    items[i-1] = items[i];
count--;

は常に最初のアイテムであるためlist[0]、最初のアイテムを削除するにはすべてを移動する必要があります。

対照的に、キューは最初のアイテムを個別に追跡します。これにより、上記のコードが次のように変更されます。

head++
于 2012-09-20T17:46:32.790 に答える
1

循環キューをより適切に実装することをお勧めします。次に、すべての int をキューの最後にプッシュし、スペースがなくなると (固定サイズによって決定されます)、各操作で最初のオブジェクトをポップして一番下にプッシュする必要があります。O(1).

Array に対する利点は、必要になるまでスペースを事前に割り当てないことです。しかし、最後に、本当に int を int として格納することを検討してください。実行する操作に関係なく、数値は常に数値として格納する必要があります。

于 2012-09-20T17:44:55.080 に答える
0

配列を事前に割り当てて、配列の開始と終了を示す2つの整数を設定してみませんか。明らかに、どちらも0から始まります。部屋がなくなると、ラップアラウンドを開始します。

疑似ヘルパークラスの例：

class CircularArray
{
  const int maxSize = 5000000;
  private int[] arr = new int[maxSize];
  private int start = 0;
  private int end = 0;

  public void Add(int value)
  {
    int newEnd = (end + 1) % maxSize;
    if (newEnd == start)
      start = (start + 1) % maxSize;
    end = newEnd;
    arr[end] = value;
  }

  public int Get(int index)
  {
    int newIndex = (start + index) % maxSize;
    return arr[newIndex];
  }
}
于 2012-09-20T17:45:01.803 に答える
0

ArrayList の最初の項目を削除すると、他のすべての項目が下に移動します。循環キューを使用すると、元の順序を維持し、リストの先頭を削除するときに発生する時間のかかるシフトを排除できます。

于 2012-09-20T17:48:18.133 に答える
0

あなたを助けるかもしれLinkedList<T> Classませんか？両端の削除と追加はO（1）操作ですが、反復はO（n）になります。または、アクセス時にO（1）が必要な場合は使用できますDictionaryまたはSortedDictionary 別のカスタム実装はQueueDictionary、Oが必要なときに使用しました(1) 終了時または開始時 (キュー/デキュー) での追加と削除の両方、および値へのアクセスに対する操作。ここに QueueDictionary: C# で Queue と Dictionary を組み合わせた QueueDictionary を実装するにはどうすればよいですか?

于 2012-09-20T18:20:37.417 に答える