6

スタックを実装する 2 つの異なる方法、リンク リストと動的配列について調べていました。動的配列に対する連結リストの主な利点は、あまりにも多くの要素が挿入された場合に動的配列のサイズを変更する必要があるのに対し、連結リストのサイズを変更する必要がないため、多くの時間とメモリを浪費することでした。

これが C++ に当てはまるかどうか疑問に思いました (新しい要素が挿入されるたびに自動的にサイズ変更されるベクター クラスがあるため)。

4

8 に答える 8

13

メモリ使用のパターンがかなり異なるため、この 2 つを比較することは困難です。

ベクトルのサイズ変更

ベクトルは、必要に応じて動的にサイズ変更されます。これは、メモリの新しいチャンクを割り当て、データを古いチャンクから新しいチャンクに移動 (またはコピー) し、古いチャンクを解放することによって行われます。典型的なケースでは、新しいチャンクは古いチャンクの 1.5 倍のサイズです (一般に信じられていることとは反対に、実際には 2 倍というのは非常に珍しいようです)。つまり、再割り当て中の短時間、実際に保存しているデータの約 2.5 倍のメモリが必要になります。残りの時間、使用中の「チャンク」は、最小で 2/3 rdsがいっぱいになり、最大で完全にいっぱいになります。すべてのサイズの可能性が同じである場合、平均で約5/6 のフルが期待できます。別の方向から見ると、スペースの約 1/6、つまり約 17% が「無駄」になることが予想されます。

そのような一定の係数でサイズを変更すると (たとえば、4Kb の増分で成長するなど、特定のサイズのチャンクを常に追加するのではなく)、償却された一定時間の追加と呼ばれるものが得られます。つまり、配列が大きくなるにつれて、サイズ変更が指数関数的に少なくなります。配列内の項目がコピーされた平均回数は一定になる傾向があります (通常は約 3 回ですが、使用する成長係数によって異なります)。

リンクされたリストの割り当て

リンクされたリストを使用すると、状況はかなり異なります。サイズ変更は見られないため、一部の挿入で余分な時間やメモリ使用量が発生することはありません。同時に、基本的に常に余分な時間とメモリが使用されていることがわかります。特に、リンク リスト内の各ノードには、次のノードへのポインタが含まれている必要があります。ポインタのサイズと比較したノード内のデータのサイズによっては、これにより大きなオーバーヘッドが発生する可能性があります。たとえば、s のスタックが必要だとします。がポインタと同じサイズである典型的なケースでは、それは常に 50% のオーバーヘッドを意味します。ポインタが_intintint; 2 倍のサイズはかなり一般的です (64 ビット ポインター、32 ビット int)。このような場合、最大 67% のオーバーヘッドが発生します。つまり、明らかに十分であり、各ノードは格納されるデータの 2 倍のスペースをポインターに割り当てます。

残念ながら、これは多くの場合、氷山の一角にすぎません。典型的な連結リストでは、各ノードは個別に動的に割り当てられます。少なくとも小さなデータ項目 ( などint) を格納している場合、ノードに割り当てられるメモリは、実際に要求する量よりも大きくなる可能性があります (通常はそうなるでしょう)。そのため、int とポインターを保持するために 12 バイトのメモリを要求しますが、得られるメモリのチャンクは、代わりに 16 または 32 バイトに切り上げられる可能性があります。ここで、少なくとも 75%、おそらく最大 88% のオーバーヘッドを見ています。

速度に関する限り、状況はかなり似ています。メモリの動的な割り当てと解放は、多くの場合非常に遅くなります。通常、ヒープ マネージャーには空きメモリのブロックがあり、必要なサイズに最も適したブロックを見つけるためにそれらを検索するのに時間を費やす必要があります。次に、（通常）そのブロックを2つの部分に分割する必要があります.1つは割り当てを満たすため、もう1つは他の割り当てを満たすために使用できる残りのメモリです。同様に、メモリを解放すると、通常、同じ空きブロックのリストに戻り、隣接するメモリ ブロックが既に解放されているかどうかをチェックします。これにより、2 つを元に戻すことができます。

大量のメモリ ブロックの割り当てと管理はコストがかかります。

キャッシュの使用

最後に、最近のプロセッサーでは、もう 1 つの重要な要因であるキャッシュの使用に遭遇します。ベクトルの場合、すべてのデータが隣り合っています。次に、使用中のベクトルの部分が終了した後、空のメモリがいくつかあります。これにより、キャッシュの使用率が大幅に向上します。使用しているデータはキャッシュされます。使用していないデータは、キャッシュにほとんどまたはまったく影響を与えません。

リンクされたリストを使用すると、ポインター (および各ノードで発生する可能性のあるオーバーヘッド) がリスト全体に分散されます。つまり、関心のある各データのすぐ隣には、ポインタのオーバーヘッドと、使用していないノードに割り当てられた空き領域があります。つまり、キャッシュの有効サイズは、リスト内の各ノードの全体的なオーバーヘッドとほぼ同じ係数で縮小されます。 7/8は、ポインターや純粋なガベージの格納に費やされます。

概要

リンクされたリストは、ノードの数が比較的少なく、それぞれが非常に大きい場合にうまく機能します。(より典型的なスタックのように) 比較的多数のアイテムを扱っている場合、それぞれが非常に小さいため、時間やメモリの使用量を節約できる可能性ははるかに低くなります。まったく逆に、そのような場合、リンクされたリストは基本的に時間とメモリの両方を大量に浪費する可能性がはるかに高くなります。

于 2012-12-11T16:26:39.090 に答える
2

まず、リンクされたリストと動的配列の間のパフォーマンスのトレードオフは、それよりもはるかに微妙です。

C++ のベクトル クラスは、要件により、「動的配列」として実装されます。つまり、要素を挿入するための償却定数コストが必要です。これを行う方法は、通常、アレイの「容量」を幾何学的に増加させることです。つまり、容量がなくなる (または容量が少なくなりそうになる) たびに容量を 2 倍にします。最終的に、これは、再割り当て操作 (新しいメモリ チャンクの割り当てと現在のコンテンツのコピー) が数回しか行われないことを意味します。実際には、これは、再割り当てのオーバーヘッドが対数間隔で小さなスパイクとしてパフォーマンス グラフにのみ表示されることを意味します。これが「償却定数」コストの意味です。これらの小さなスパイクを無視すると、

リンク リストの実装では、再割り当てのオーバーヘッドはありませんが、フリーストア (動的メモリ) に新しい要素をそれぞれ割り当てるオーバーヘッドがあります。そのため、オーバーヘッドはもう少し規則的です (スパイクではなく、時々必要になることがあります) が、動的配列を使用するよりも重要になる可能性があります。私の意見では、連結リストは、コピー (または移動) に非常にコストがかかるオブジェクトに対してのみ推奨されます。しかし、結局のところ、これはあらゆる状況でテストする必要があるものです。

最後に、参照の局所性は、多くの場合、要素を広範囲に使用およびトラバーサルするアプリケーションの決定要因になることを指摘することが重要です。動的配列を使用する場合、要素は次々にメモリにパックされ、CPU が読み取り/書き込み操作の前にメモリをプリエンプティブにキャッシュできるため、順序通りのトラバーサルを行うことは非常に効率的です。通常の連結リストの実装では、ある要素から次の要素へのジャンプは、通常、非常に異なるメモリ位置間でかなり不規則なジャンプを伴い、この「プリフェッチ」動作を効果的に無効にします。そのため、リストの個々の要素が非常に大きく、それらに対する操作の実行に通常非常に時間がかかる場合を除き、リンクされたリストを使用する際のこのプリフェッチの欠如が主要なパフォーマンスの問題になります。

std::listご想像のとおり、有利なアプリケーションの数がほとんどないため、リンク リスト ( ) を使用することはめったにありません。非常に多くの場合、大きくてコピーにコストがかかるオブジェクトの場合、単純にポインターのベクトルを使用する方が望ましいことがよくあります (基本的に、リンクされたリストと同じパフォーマンスの利点 (および欠点) が得られますが、メモリの使用量は少なくなります (ポインターをリンクするため))。 ) 必要に応じてランダムアクセス機能を利用できます)。

私が考えることができる主なケースは、連結リストが動的配列 (または のようなセグメント化された動的配列std::deque) よりも優先される場合で、(どちらかの端ではなく) 中央に要素を頻繁に挿入する必要がある場合です。ただし、このような状況は通常、ソートされた (または何らかの方法で順序付けられた) 要素のセットを保持している場合に発生します。この場合、ツリー構造を使用して要素を格納します (たとえば、二分探索木 (BST))。リンクリストではありません。そして、多くの場合、そのようなツリーは、半連続メモリ レイアウト (幅優先レイアウトなど) を使用して、動的配列またはセグメント化された動的配列 (キャッシュ無視動的配列など) 内にノード (要素) を格納します。

于 2012-12-11T15:47:58.287 に答える
1

std::vectorは動的配列を使用してstd::list実装されますが、リンクリストとして実装されます。両方のデータ構造を使用することにはトレードオフがあります。ニーズに最適なものを選択してください。

  • ご指摘のとおり、動的配列は、それ自体を拡張する必要があるため、アイテムがいっぱいになると、アイテムの追加に時間がかかる可能性があります。ただし、すべてのメンバーがメモリ内でグループ化されているため、アクセスが高速です。この緊密なグループ化により、通常、キャッシュがより使いやすくなります。

  • リンクリストのサイズを変更する必要はありませんが、CPUがメモリ内をジャンプする必要があるため、リストをトラバースするのに時間がかかります。

于 2012-12-11T15:30:47.933 に答える
0

http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style 44:40 にスキップします。ビデオで説明されているように、Bjarne 自身std::vectorによる. すべての要素を隣り合わせにメモリに保存するため、メモリにキャッシュされるという利点がありますstd::list。これは、要素の追加と削除、および検索にもstd::vector当てはまります。std::vector彼は、std::listは よりも 50 ～ 100 倍遅いと述べていstd::vectorます。

本当にスタックが必要な場合はstd::stack、独自に作成するのではなく、実際に使用する必要があります。

于 2012-12-11T15:39:17.873 に答える