リンクされたリストデータ構造の調整は、ランダムなルックアップを高速にしますか？

Question

私は現在、二重リンクリストを使用しています（C ++ std::list）それぞれに一意の整数識別子があるレコードの束を保持する。リンクされたリストは、リストでは、次のアイテムには常にその前身よりも大きな一意の識別子があるように、並べ替えられた順序で作成されます。

私が直面している問題は、時折、アイテムを相対ソートされた位置にすばやく挿入できることを意味し、プレーンリンクリストを使用すると、この操作は$ o（n）$であり、パフォーマンスの問題を引き起こしていることを意味します。一般的に、これは私がバイナリツリーのようなものを使用したいことを意味します（C ++ std::map）、しかし、私はまた、良好なパフォーマンスを得るために、二重リンクリストの次の機能にも依存しています。

• $ O（1）$時間で、あるリンクリストから別のリストに連続的なセクションをスプライスする機能。 （償却$ o（1）$または$ o（ log log n）$で十分です。）

私が活用したい私のデータの1つの機能は、それぞれの整数が前任者よりもまったく多い隣接するレコードの長い範囲があることが多いことです。アイテムの相対ソートされた位置を検索する場合、重複した識別子がないため、常にそのような隣接する記録の外にあります。

置換データ構造または拡張を二重リンクリストに見つけたいと思います。これにより、一定の時間内にあるリスト全体から別のセクションにスプライスし続けることができますが、新しいレコードを挿入するソートされた位置を見つけることができます$ o（n）$ timeよりも優れています。

その他の操作には、アイテム全体の前方および後方反復が含まれます。レコードインデックスはゼロから始まり、一般に順次64ビットに向かって上方に成長し、そのような場合にはコードがうまく機能します。時々、後続のレコードの前にいくつかのレコードが利用できない場合があります。これは、パフォーマンスの問題を引き起こすこれらの欠落したレコードの挿入です。

私にとって発生する可能性のあるアプローチの1つは、いくつかのインデックスの位置をキャッシュすることです。スプライスがキャッシュされたエントリと重複する可能性のあるアイテムを削除すると、キャッシュが無効になります。このキャッシュを使用すると、線形検索を行う代わりに、検索が検索されている位置に最も近いキャッシュポイントイテレーターから検索を開始できます。ただし、隣接するレコードの機能をより完全に活用したいと思います。また、各地域が連続したレコードのリンクされたリストである隣接する地域のトップレベルのリンクリストがある階層リンクリストについても考えましたが、これを提供するためにリンクされたリストを適応させるクリーンな方法はありませんでした機能。おそらくこのようなことは以前に行われたことがありますか？スキップリストは近いことがわかりますが、Splice（）の機能は表示されません。さらに、汎用スキップリストは、連続したレコード内で挿入が発生しないという事実を活用しません。

Answer 1

簡単なアプローチの1つは、極端な範囲の二重にリンクされたリストを使用することです。ここでは、各範囲が一連の連続したレコードを表します。各範囲内のレコードは、二重リンクリストで表すことができます。

これにより、$ o（1）$ timeスプライシングを行う能力が維持され、挿入操作には$ o（k）$の時間がかかります。ここで、$ k $は$ o（n）$、$ $ $の範囲数です。 n $はレコードの数です）。レコードよりも多くの範囲がある場合、これは部分的な改善かもしれません。

これが簡単なスキップリストやバイナリツリーよりも優れているかどうかはわかりません。

バイナリツリーを使用している場合でも、効率的なスプライシングができることに注意してください。スプライシング操作は$ o（1）$ timeではなくなりましたが、$ o（ log ell）$ timeで実行できます。ここで、$ ell $はスプライスされたセグメントのレコード数です。これは$ o（1）$ timeスプライシングほど速くはありませんが、異なる操作の相対的な頻度に応じて、考慮できる別のデータ構造です（たとえば、現実的なデータセットのベンチマーク）。

そして、もちろん、これらのアイデアを、例えば、範囲のバイナリツリーと組み合わせることができます。そこでは、それぞれの範囲が連続したレコードの二重にリンクされたリストです。挿入には$ o（ lg k）$ timeがかかり、スプライシングは$ o（ lg ell）$ timeで実行できます（どちらも潜在的に$ o（ lg n）$よりも優れている可能性があります。単純なバイナリツリー）。