6

Javaで、イベントのストリーム上にスライディングウィンドウを実装しています。したがって、次のことを実行できるデータ構造が必要です。

  1. 新しいイベントが発生したときにデータ構造の最後に追加します。

  2. 古いイベントが処理されるときにデータ構造の先頭から削除します。

  3. データ構造の要素への標準のランダムアクセス（size()、 ）を取得します。get(i)一般に、一般的なリストの「読み取り」操作。

  4. 上記のすべての操作に効率的です。

  5. 無制限です。

他のアクセスは必要ありません。また、スレッドセーフは必要ありません。

私は現在、物事を稼働させるために、 ArrayListを使用してこれを行っています。しかし、私はもっと効率的なものが欲しいです。方法（上記のremove(0)2.）は、。を使用すると非効率的ArrayListです。

番号1と2は、標準のキュースタイルの操作です。ただし、QueueJDKでの実装（ArrayDequeなど）では、3では許可されていませんget(i)。

ですから、そのような実装があり、商用利用に適したライブラリが世の中にあるのではないかと思います。

そうでなければ、私は自分で書くことに頼ると思います...

4

8 に答える 8

4

キューの容量が固定されていれば問題ない限り、循環バッファーのタスクのようです。ただし、標準的な実装については知りません。しかし、ここにあなた自身の を巻くための素晴らしいレシピがあります.

于 2009-11-05T18:41:16.050 に答える
3

十分な大きさの配列がある場合は、基本的な配列でキューを実装し、リストの先頭にインデックスを使用し、必要に応じてラップアラウンドできるように mod 演算子を使用できます。

したがって、基本的に、挿入機能と削除機能をサポートする循環配列があります。

アップデート：

配列をより大きな配列にコピーするのは簡単な操作なので、挿入のステップとして、サイズを 2 倍にして、おそらく最後に近づいたら、配列をコピーするだけです。通常は増加してコピーするべきではないため、全体的には依然として非常に高速なアクセスが可能です。

于 2009-11-05T18:42:16.430 に答える
2

このキューに出入りするイベントの速度は?

一方では、「十分に大きな」循環バッファを持つことができます。

技術的には「有界」ですが、必要に応じて大きくすることで「無界」にすることができます。

同様に、「静か」な場合は、全体の容量を「縮小」できます。

しかし、多くのアプリケーションでは、100 個、1000 個、または 10000 個のアイテム容量の循環バッファーは事実上無制限です。

于 2009-11-05T18:57:10.003 に答える
1

そのようなインターフェースを実装すると私が考えることができる唯一のライブラリはLinkedListですが、率直に言って、パフォーマンス特性が何であるかはわかりません。

于 2009-11-05T18:32:39.157 に答える
1

独自に展開する代わりにこれを投げ出すだけなので、一粒の塩で受け取ってください: ランダムアクセスが必要な頻度とそこget(i)から必要なパフォーマンス (および一般的なキューサイズの大きさ) に応じて、ArrayDeque.toArray()[i]要素にアクセスする必要がある場合はいつでも使用できます。小さなキューサイズと時折のtoArray()使用System.arraycopy()ではかなり高速になるはずの隠れた用途。キューへのランダムアクセスが必要な理由と、それが必要な頻度を理解するのに役立ちます-おそらく、それなしでアルゴリズムを実装する別の方法があります。

于 2009-11-05T19:00:10.777 に答える
0

二項ヒープは、O(1) の償却された挿入と O(log n) の償却された削除の分を持つことができます。O(log**2 n) のランダムアクセスを償却することもできると思います。Queue-push は、連続する整数をキーとして要素をヒープに挿入します。

rbtree を使用すると、挿入、最小削除、およびランダム アクセスのすべてに対して、O(log n) 悲観的なキュー プッシュを実行できます。これは、ツリーがキーとして整数の連続セットを持ち、キューの k 番目の要素が k 番目のキーを持つツリー内の要素になるためです。

于 2009-11-05T19:37:06.530 に答える