c++ - 最速のシーケンシャル アクセス

Question

最速の順次アクセスにはどのデータ構造を使用する必要がありますか?

• ベクター
• 単方向リスト
• 二重連結リスト

同期されていないデータ構造とはどういう意味ですか? ベクターを同期と呼ぶ人もいれば、そうでない人もいます。

配列はランダムな方法でもシーケンシャル アクセスでもアクセスできますが、LL はシーケンシャル アクセスでしかアクセスできません。

Answer 1

これらの3つのアイテムはすべて、シーケンス内の次のアイテムに直接アクセスできます。それは言った：

ベクター、リンクリスト、およびダブルリンクリストのシーケンシャルアクセスの複雑さは同じかもしれませんが、ベクトルがほとんどの場合、実際の最高のパフォーマンスを提供することは間違いありません。メソッドのパフォーマンスを見るとき、操作のO（n）またはΘ（n）だけでなく、多くの要因が考慮されます。

最新のC++仕様のベクトルは、連続したメモリ割り当てが保証されています（つまり、アイテムはメモリ内で次々に配置されます）。つまり、メモリから1つのオブジェクトを検索すると、近くのオブジェクトもL2およびL1キャッシュにロードされます（空間的局所性）。これは、CPUがメモリからコンテンツを取得する必要がないため、同じベクトル内の後続のアイテムへのアクセスがはるかに高速になることを意味します。

逆反復の場合、二重リンクリストとベクトルの両方で、O（1）が次の（前の）アイテムにアクセスできるようになりますが、同じ問題が発生します。二重リンクリストは、次のノードに到達するためにいくつかの操作を実行する必要があります（ただし、これは固定数の操作であるため、O（1）値です）。これには、次のオブジェクトへのポインターの値の読み取りと、その内容にアクセスするためのアドレス。ここでは、ベクトルが常に優位になります。

ベクトルを使用すると、任意のランダムノードに直接アクセスすることもできます。ダブルリンクリストとシングルリンクリストはどちらもそうすることができません。ランダムなインデックスを取得するには、最初から繰り返す必要があります（終了はダブルリンクリストのオプションでもあります）。

基本的に：99％の場合、ベクトルを使用する必要があります。多くの重要なメトリックを隠すため、実際のパフォーマンスをO（n）またはΘ（n）に依存しないでください。ベクトルの欠点は、要素の数が事前に予約されたスペースの量を超える場合、ベクトルのサイズを変更する必要があることです（通常、すべてのデータを新しい場所にコピーする必要があります）。特定のサイズのスマート予約により、この問題を軽減できます。そして一般的に、リンクリストを使用してこれを「解決」することは、熱心な事前最適化であり、助けになるのではなく、傷つくことになります。

Answer 2

配列はランダムな方法でもシーケンシャル アクセスでもアクセスできますが、LL はシーケンシャル アクセスでしかアクセスできません。

シーケンシャル アクセスは、ランダム アクセスの観点から実装された場合、最初から まで実際にシークする代替手段と比較すると一定nであり、これは時間的に線形です。

ランダム アクセスのコンテナーの場合、要素のシーケンシャル アクセスは次のnようになります。

cursor := getStartCursor()
cursor := cursor+n
getElementAt(cursor)

シーケンシャル アクセスのみのコンテナーの場合は、次のようになります。

cursor := getStartCursor()
for i = 0 to n:
    cursor := getNextCursor(cursor)
getElementAt(cursor)

また、単一の操作は、逆参照addとは異なるアルゴリズムの複雑さのカテゴリに属します。n

例えると、シーケンシャル アクセスはイースター エッグ ハントのようなもので、最初の 4 つの手がかりをまだ見つけていないと 4 つ目のエッグにスキップすることはできません。対照的に、各卵がどこにあるかの地図を使用すると、元の順序を含め、いつでも好きな卵に行くことができます.

Answer 3

アクセスの方向も重要です: 前から後ろへ: それらはすべて同じです (ただし、ベクトルの実装によっては、割り当てとインクリメントのほうが少し速い場合があります)。

間で逆にする必要がある場合: Double-Linked List と Vector (それを指摘してくれた Mahmoud に感謝します!)