倍増配列を使用してキャッシュ無視スタックを実装できることを読みました。
1/B分析により、各プッシュとポップが償却された I/O の複雑さをどのように持つのか、誰か説明してもらえますか?
2 に答える
3
スタックは次の操作をサポートしています。
- 押す
- ポップ
これらの 2 つの操作は、O(1) プッシュと O(1) ポップを使用して単一リンク リストを使用して実行できますが、格納された要素がメモリ全体に分散されるため、キャッシュの問題が発生します。このアプローチでは、リストの先頭にプッシュし、リストの先頭からポップします。
動的配列をデータ構造として使用し、配列の最後にプッシュおよびポップできます。(配列内の最後に埋められた位置をインデックスとして追跡し、要素をプッシュおよびポップするときにそれを変更します)。
配列のサイズを変更する必要がないため、ポッピングは O(1) になります。
配列の最後に余分なスペースがある場合、プッシュは O(1) になります。
問題は、要素をプッシュしようとしたときにスペースがない場合です。この場合、2 倍の大きさ (2n) の新しい配列を作成し、n 個の要素をそれぞれコピーしてから、要素をプッシュします。
すでにサイズが n であるが、最初は空である配列があるとします。
n+1 要素を配列にプッシュすると、最初の n 要素は O(1)*n = O(n) 時間かかります。
+1 要素は、配列の新しいコピーを作成する必要があるため、O(n) 時間かかります。
したがって、n+1 個の要素を配列にプッシュすると O( 2n ) になりますが、定数を削除して、O(n) または要素数の線形であると言うことができます。
そのため、1 つの要素をプッシュする場合は一定の操作よりも時間がかかる場合がありますが、多数の要素をプッシュする場合は直線的な量の作業が必要になります。
動的配列は、すべての要素が可能な限り互いに近くにあるため、キャッシュに適しているため、複数の要素が同じキャッシュラインにある必要があります。
于 2012-08-27T04:31:45.923 に答える
1
標準スタックはキャッシュを気にしないと思います。プッシュ/ポップのシーケンスは隣接するアドレスでなければならないため、アクセスの 1/B のみでフォールトし、B 操作ごとに 1 回だけ新しいキャッシュ ラインをヒットできます。(注: スラッシングを防ぐために、引数には少なくとも 2 つのキャッシュ ラインが必要です。)
于 2012-08-27T03:19:14.730 に答える