2

これをどう説明すればいいのか100%わかりませんが、頑張ります。私は現在、構造体のセット(objsと呼ばれる)へのポインターを含む構造体(setと呼ばれる)があるプロジェクトに取り組んでいます。これらの構造体のセットにアクセスするには、onはそれらのメモリアドレス(配列など)を反復処理する必要があります。メイン構造体には、そのセット内の構造体の数が含まれています。これが私のやり方です

objs = set->objs;

for(n=0; n < set->numObjs; n++)
{
  do_something(objs);
  objs++;
}

私の質問は、リンクリストはより安全で、より速く、または何らかの方法でより良いでしょうか?代わりに構造体の配列はどうですか?

ありがとう。

4

3 に答える 3

3

すべてのデータがメモリ内に連続して存在し、CPU キャッシュを非常に効率的に使用するため、配列は通常、要素ごとにトラバースして操作する方がはるかに高速です。対照的に、リンクされたリストは多かれ少なかれキャッシュ使用の点で最悪です。なぜなら、すべてのリストノードがメモリの完全に別の部分になりやすく、キャッシュライン全体を単独で占有する可能性があるためです。

一方、リンクされたリストは、コンテナとして操作する方が簡単です。要素を挿入したり削除したりするコストがほとんどないためです。周りの配列。

好きなのを選びな。

または、プロファイルとプロファイルの両方を試してください。

于 2012-08-27T14:24:44.777 に答える
1

このソース部分は多少不完全ですが、objs は set->objs と同じ型へのポインターのようです。あなたがしていることは、配列構文でインデックスを付けるのではなく、ポインター演算を使用して、これらの obj のリストまたは配列を反復処理することです。ただし、obj のリストがシーケンシャル メモリに格納されているか、ポインターのインクリメントが機能せず、シーケンシャル リスト内の次の obj が得られません。

問題は、リストを維持および変更する限り、実際にどのような種類の操作を行いたいかです。たとえば、リストが基本的にほとんど変更されない静的リストである場合、順次リストは正常に機能するはずです。唯一の主要な操作がリストに何かを追加することである場合、最大数を知っていて、それだけの順次メモリを割り当てることができれば、おそらく順次リストで問題ありません。

リンクされたリストが優れているのは、次の領域です: (1) リストからの要素の挿入および/または削除、特に前面または背面にない要素、(2) 拡張可能で、特定の数に依存する必要がない。の要素をリストに追加します。

固定サイズのシーケンシャル リストを拡張するには、通常、新しいメモリ領域を割り当てて、リストを新しいメモリ領域にコピーする必要があります。

別のオプションは、基本的にリンクされた順次リストのセットであるデータ構造を持つことです。順次リストがいっぱいになり、さらにスペースが必要になると、別の順次リスト領域を割り当てて、2 つをリンクするだけです。ただし、このアプローチでは、空のスペースを管理するための追加のコードが必要になる場合があります。これは、アイテムを削除する必要があるか、新しいアイテムを挿入するときに何らかの並べ替えが必要かによって異なります。

これは、リンクされたリストに関するウィキペディアの記事です。

于 2012-08-27T14:35:01.163 に答える
0

おそらくメモリ キャッシュを効率的に使用しないため (リスト ノードは配列とは異なり、異なるメモリ ページにある可能性があります)、リンク リストは遅くなりますが、リンク リストを使用する方がおそらく簡単で安全です。リンクされたリストのソリューションが遅すぎることがわかった場合にのみ、配列を使用することをお勧めします。

于 2012-08-27T14:21:49.287 に答える