キューの複雑さの分析

Question

私は2つのキューを持っています.1つはストレージ用の配列を使用して実装され、もう1つはリンクされたリストを使用して実装されています。

私はエンキューとデキュー操作の複雑さは、このようになっていることを信じている -

LinkedListQueueエンキュー - O（1）

LinkedListQueue Dequeue- O（1）

ArrayQueueEnqueue - O（1 ）

ArrayQueueデキュー - O（n）の

だから私は彼らからの文字列を追加し、除去することにより、両方のキューをテストしました。ここで私が得た結果は、時間がとられるがミリ秒である -

私のビッグああの複雑さの分析は、これらの結果を積み重ねていますか？私が持っているLLQueue Enqueueの複雑さはO（1）ですが、わかるように1000文字列の場合は2ms、100000文字列の場合は79msです。それは期待されていますか？

私はArrayQueue DequeueをO（n）としてマークダウンしましたが、その結果はO（n）のように見えますか？ 20000と50000の文字列の間には大きなジャンプがありますが、50000の代わりに100000の文字列をデキューすると時間が2倍になります。

Answer 1

まず、ArrayQueueのデキュー操作がとても驚きです高価な。各デキューのキュー内容全体を移動していますか？はるかに優れたアプローチがあります。オンラインで「循環キュー」を参照してください。

今、測定に。ビッグ・オハイオの複雑さは、ストーリーの一部を伝えるだけです。

キャッシュ

それはあなたのテストはキューに要素の束をエンキューのように思えるし、それらをデキュー：あなたが実行している時間の測定を開始するときは、次のような複雑な効果、さまざまな表示されます。キュー全体がプロセッサのL1キャッシュに収まる場合は、すべてのメモリ操作が高速になります。

キューのサイズがL1キャッシュを超える場合、データはL2キャッシュに流出する必要があり、結果として2-3倍の速度低下が生じる可能性があります。キューのサイズがL2キャッシュを超えている場合、データはメインメモリに格納されなければならず、パフォーマンスがさらに低下します。たとえば5倍です。あなたのタイプの命名から

ガベージコレクション

、私はあなたがJavaやC＃のように、ガベージコレクションで言語を使用していることを推測します。そうであれば、プログラムはいつでも停止することができますが（今は重要ではありませんが）、メモリのクリーンアップに時間を費やします。

その他の効果

私は上記の2つの効果は、あなたがあなたのようなシナリオにに遭遇する可能性が最も高いだろうなものですが、多くその他の複雑な行動はであることを推測しますコンパイラ、VM、OS、およびハードウェアが含まれているため、パフォーマンス測定値の解釈が難しくなります。

パフォーマンスの測定値が正確にどのようになったのかを把握しようとすると楽しい学習体験となるかもしれませんが、それは簡単なことではありません。