タイトルが示すように、std :: listをスタックとして使用し、リストのすべての要素を反復処理するプログラムで問題が発生しました。リストが非常に大きくなったとき、プログラムはあまりにも長くかかっていました。
誰かがこれについて良い説明がありますか？スタック/キャッシュの動作ですか？
（リストをstd::vectorとstd::deque（ちなみに驚くべきデータ構造）に変更することで問題を解決し、すべてが突然非常に速くなりました）
編集：私はばかではなく、リストの真ん中にある要素にアクセスしません。私がリストで行った唯一のことは、最後/最初の要素を削除/追加し、リストのすべての要素を反復処理することでした。そして、私は常にイテレータを使用してリストを反復処理しました。
リストにはひどい (存在しない) キャッシュの局所性があります。すべてのノードは新しいメモリ割り当てであり、どこにでもある可能性があります。したがって、あるノードから次のノードへポインタをたどるたびに、メモリ内の新しい無関係な場所にジャンプします。そして、はい、それはパフォーマンスをかなり損ないます。キャッシュ ミスは、キャッシュ ヒットよりも 2 桁遅くなる場合があります。vector または deque では、ほぼすべてのアクセスがキャッシュ ヒットになります。ベクトルはメモリの 1 つの連続したブロックであるため、それを反復処理するのは可能な限り高速です。両端キューはメモリのいくつかの小さなブロックであるため、キャッシュ ミスが発生することがありますが、それでもまれであり、ほとんどのキャッシュ ヒットが得られるため、反復は依然として非常に高速です。
リストは、ほとんどすべてのキャッシュ ミスになります。そして、パフォーマンスは最悪です。
実際には、リンクされたリストがパフォーマンスの観点から正しい選択になることはほとんどありません。
編集：コメントが指摘したように、リストのもう1つの問題はデータの依存関係です。最新の CPU は、操作をオーバーラップするのが好きです。しかし、次の命令がこの命令の結果に依存している場合、それはできません。
ベクトルを反復処理している場合、それは問題ありません。メモリをチェックインすることなく、オンザフライで読み取る次のアドレスを計算できます。現在address を読んでいる場合x、次の要素は address に配置されますx + sizeof(T)。ここで、T は要素の型です。そのため、そこには依存関係がなく、CPU は次の要素またはその次の要素の読み込みをすぐに開始できますが、前の要素を処理している間もそのままです。そうすれば、データは必要なときにすぐに利用できるようになります。これにより、RAM 内のデータにアクセスするコストをさらに隠すことができます。
iリストでは、ノードからノードへのポインターをたどる必要があり、ロードされるi+1までi+1、どこを探すべきかさえわかりませんi+2。データ依存性があるため、CPU は一度に 1 つずつノードを読み取る必要があり、将来のノードがどこにあるかをまだ認識していないため、事前に読み取りを開始することはできません。
リストのすべてがキャッシュ ミスでなかった場合、これは大きな問題にはなりませんでしたが、多くのキャッシュ ミスが発生しているため、これらの遅延はコストがかかります。
これは、リストを使用するときに大量のキャッシュ ミスが発生するためです。ベクトルを使用すると、周囲の要素がプロセッサのキャッシュに格納されます。
次のstackoverflowスレッドを見てください。
キャッシュの問題があります。ベクトル内のすべてのデータは連続したチャンクに格納され、各リスト要素は個別に割り当てられ、メモリのかなりランダムな場所に格納される可能性があり、キャッシュ ミスが増える可能性があります。ただし、他の回答で説明されている問題のいずれかに遭遇することは間違いありません。
簡単な答えは、ベクターの反復処理は反復処理ではなく、配列のベースから開始して要素を 1 つずつ読み取るだけだからです。
これは C ではなく C++ とマークされているようですが、内部では同じことを行うため、配列を任意に大きく割り当てて、realloc()ing および memmove することで、配列の先頭と末尾に要素を追加できることを指摘する価値があります。 () 部屋がなくなった場合に、2 つのコンパニオン アレイ間で実行します。とても早い。
配列の先頭に要素を追加する秘訣は、配列の先頭でポインターを進め、先頭に要素を追加するときにそれを元に戻すことによって、配列の論理的な開始をバイアスすることです。（スタックの実装方法も）
まったく同じ方法で、C を作成して負の添字をサポートすることができます。
C++ はベクトル STL クラスを使用してこれらすべてを行いますが、内部で何が行われているかを覚えておく価値があります。
[編集: 私は訂正します。std::list には operator[] がありません。ごめん。]
あなたの説明からはわかりにくいですが、項目にランダムに (つまり、インデックスで) アクセスしようとしていたのではないかと思います。
for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }
イテレータを使用する代わりに:
for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }
"vector" と "deque" はどちらもランダム アクセスに適しているため、これらの型 (どちらの場合も O(1)) に対して適切に実行されます。しかし、「リスト」はランダムアクセスが苦手です。インデックスでリストにアクセスすると O(n^2) 時間かかりますが、イテレータを使用する場合は O(1) 時間かかります。