java - Java CircularFifoQueue のパフォーマンス

Question

CircularFifoQueue クラスの仕組みを理解するのに少し苦労しています。したがって、私の要件では、固定サイズ (約 6000 要素) の FIFO キューが必要です。最初はArrayDequeueを使用していましたが、パフォーマンスがかなり悪かったです。次に、CircularFifoQueue について読んで試してみました。パフォーマンスの向上は見られますが、まだ高速ではありません。

私の質問は次のとおりです。キューがいっぱいで、要素を追加するとどうなりますか? 基になる配列全体がコピーされますか? たとえば、設定されるオフセットはありますか

  head = (head + 1) % size;

後者の場合、アルゴリズムのパフォーマンスが悪いと思います。

ありがとう！

Answer 1

ドキュメントでは、への挿入について次のように述べていますCircularFifoQueue。

キューがいっぱいの場合、新しい要素を挿入できるように、最後に追加された要素が破棄されます。

パフォーマンスに関して言えば、定数時間で実行されるadd、remove、peek、pollおよびofferメソッドを除いて、このデータ構造のすべてのメソッドは線形時間で実行されるか、さらに悪いことに注意してください。