1

時間に敏感なアイテムの配列があります。一定の時間が経過すると、最後のアイテムが脱落する必要があり、新しいアイテムが最初に配置されます。

これを行う最善の方法は何ですか？

4

11 に答える 11

10

配列またはリストの特別なインスタンスであるキューを使用することをお勧めします。時限イベントが発生したら、キューから最後のアイテムをポップしてから、新しいアイテムをプッシュします。

于 2008-09-29T14:08:22.427 に答える
7

おそらく、配列でこれを行う最も簡単な方法は、循環インデックスを使用することです。常に array[n] を確認するのではなく、array[cIndex] を参照します (cIndex は、インデックス付けされている配列内の項目を参照します (cIndex は、arraySize (cIndex % arraySize) に基づいてインクリメントされます)。

配列内の最も古い項目を削除する場合は、((cIndex + (arraySize - 1)) % arraySize) にある要素を参照するだけです。

または、linkedList アプローチを使用することもできます。

于 2008-09-29T14:12:03.527 に答える
6

代わりにキューを使用してください。

于 2008-09-29T14:06:51.823 に答える
1

キューを使用することにより、できればリンクされたリストを使用して実装されます。

于 2008-09-29T14:08:09.137 に答える
1

単純な配列ではなくQueue の使用を検討してください。

于 2008-09-29T14:08:32.723 に答える
1

LinkedList<T>には、完全に機能するはずの AddFirst および RemoveLast メンバーがあります。

編集:キューのドキュメントを見ると、内部配列を使用しているようです。実装が円形配列タイプのアルゴリズムを使用している限り、パフォーマンスは問題ないはずです。

于 2008-09-29T14:09:34.220 に答える
1

固定数のアイテムがある場合、キューは機能します。

「時間」がわかっている場合は、SortedDictionary に DateTime キーを指定し、Add メソッドをオーバーライドして、古すぎるキーを持つすべての項目を削除します。

于 2008-09-29T14:09:00.787 に答える
0

csharp 3 では、次のことができます。

original = new[] { newItem }.Concat(
    original.Take(original.Count() - 1)).ToArray()

しかし、おそらく特殊なデータ構造を使用する方が良いでしょう

于 2008-09-29T14:10:02.767 に答える
0

QueueFIFO配列に最適です。一般的な配列処理の場合、List (T)Insert(0, x)およびRemoveAt(0)メソッドを使用して、たとえばリストの前に項目を配置または削除します。

于 2008-09-29T14:11:58.737 に答える
0

技術的には、両端キューが必要です。キューには、一方の端のみから押し出されたアイテムがあります。端キューは両端で開いています。

ほとんどの言語では、最初の要素を削除して最後に別の要素を配置するだけで、配列操作が可能です。

または、ループしてすべての要素をシフトすることもできます。各要素 (最も古いものから開始) をその隣の要素に置き換えるだけです。次に、新しいアイテムを最後の要素に配置します。

両端キューが特定のサイズを超えないことがわかっている場合は、円形にすることができます。ただし、両端がどこにあるかを示すには、2 つのポインターが必要です。アイテムを追加および削除すると、それに応じてポインターが増減します。バッファ オーバーフロー状態 (つまり、ポインタが「交差」) を検出する必要があります。また、モジュラー演算を使用して、ポインターが配列の周りを一周するようにする必要があります。

または、配列内の各要素にタイムスタンプを付けて、「古く」なりすぎたときにそれらを削除することもできます。これを行うには、別の配列に同じ方法でインデックスを付けるか、2 つの要素配列の配列を作成し、サブ要素の 1 つにタイム スタンプを格納します。

于 2008-09-29T14:36:21.533 に答える
0

これを行う最速の方法を探している場合は、循環配列になります。配列内の現在の位置 (ndx) と配列の末尾 (end) を追跡します。最も古いアイテムを暗黙的に削除します。

循環配列は、私が知っている固定サイズのキューの最速の実装です。

たとえば、C/C++ では、int の場合は次のようになります (0 を取得すると終了します)。

int queue[SIZE];
int ndx=0;      // start at the beginning of the array
int end=SIZE-1;
int newitem;
while(1){
  cin >> newitem;
  if(!newitem)  // quit if it's a 0
    break;
  if(ndx>end)   // need to loop around the end of the array
    ndx=0;
  queue[ndx] = newitem;
  ndx++
}

多くの最適化を行うことができますが、自分で構築したい場合は、これが最速のルートです。

パフォーマンスを気にしない場合は、一般化する必要があるため、付属の Queue オブジェクトを使用してください。

最適化されている場合とされていない場合があり、固定サイズのリストをサポートしていない場合もあるため、使用する前にドキュメントを確認してください。

于 2008-09-29T16:48:20.390 に答える