☰

データ構造名: 組み合わせ配列/リンクリスト 質問する

tag-icon • tag-icon algorithm language-agnostic data-structures
データ構造名: 組み合わせ配列/リンクリスト 質問する

リンク リストの利点と固定サイズ配列の利点を組み合わせたデータ構造を思いつきました。これは非常に明白なことのように思えるので、誰かがすでに考えついて名前を付けていると思います。これは何と呼ばれているか知っている人はいますか。

小さな固定サイズの配列を用意します。配列に入れたい要素の数が配列のサイズより大きい場合は、新しい配列と、古い配列と新しい配列の間に任意のポインタを追加します。

つまり、次のようになります。

Static array
—————————————————————————
|1|2|3|4|5|6|7|8|9|a|b|c|
—————————————————————————

Linked list
————  ————  ————  ————  ————
|1|*->|2|*->|3|*->|4|*->|5|*->NULL
————  ————  ————  ————  ————

My thing:
————————————  ————————————
|1|2|3|4|5|*->|6|7|8|9|a|*->NULL
————————————  ————————————

編集: 参考までに、このアルゴリズムは、最悪の場合の追加/削除パフォーマンスがかなり悪く、平均的な場合もそれほど良くありません。私のシナリオでの大きな利点は、読み取り操作のキャッシュ パフォーマンスが向上することです。

賞金に関する編集: Antal SZさんの回答は完璧でよく調査されていたので、懸賞金をあげたいと思いました。どうやらStack Overflowでは懸賞金をあげた直後に回答を受け入れることはできないようで、待つしかありません（確かに私は意図懸賞金制度を多少乱用していますが、素晴らしい回答をした人に報いるという名目でそうしています）。もちろん、誰かがするより良い答えを提供できれば、彼らにさらなる力を与え、代わりに彼らが賞金を獲得できる可能性が高くなります。

名前の編集: 私は何に興味がないあなたは専門家がそう呼んでいるからという理由でそう呼ぶのでなければ、そう呼んでも構いません。あなたが思いついた名前なら、私は興味がありません。私が欲しいのは、教科書やGoogleで調べられる名前です。（また、ヒント：Antalの回答は私が探していたものです。あなたの答えが「展開されたリンクリスト」で、とても正当な理由ですが、それは明らかに間違っています。

ベストアンサー1

それは展開されたリンクリスト速度とスペースの点で2つの利点があるようです。まず、各ノードの要素数が適切なサイズであれば（例えば（最大で1キャッシュラインのサイズ）の場合、メモリの局所性の向上により、キャッシュパフォーマンスが大幅に向上します。次に、O（ん/メートル）リンク、ここでん展開されたリンクリストの要素数であり、メートルは、任意のノードに格納できる要素の数ですが、かなりの量のスペースを節約することもできます。これは、各要素が小さい場合に特に顕著です。展開されたリンク リストを作成する場合、実装では一般にノードにスペースを残そうとするようです。つまり、完全なノードを挿入しようとすると、要素の半分が移動されます。したがって、最大で 1 つのノードが半分未満になります。また、私が見つけた情報によると (自分で分析したわけではありません)、ランダムに挿入すると、ノードは実際には約 4 分の 3 がいっぱいになる傾向があり、操作がリストの末尾で行われる傾向がある場合はさらにいっぱいになります。

そして、他のみんな（Wikipediaを含む）が言っているように、あなたはチェックしてみるといいかもしれませんスキップリストスキップリストは、順序付けられたデータをO(logん) 挿入、削除、検索の実行時間は予想どおりです。これはリンクリストの「タワー」で実装されており、各層は上に行くほど要素が少なくなります。一番下には通常のリンクリストがあり、すべての要素があります。各層では、要素の数はp（通常は1/2または1/4）。その構築方法は次のとおりです。リストに要素が追加されるたびに、その要素は最下行の適切な場所に挿入されます（これは「検索」操作を使用しており、これも高速化できます）。次に、確率でp、それはその上のリンクリストの適切な場所に挿入され、必要に応じてそのリストが作成されます。それがより上位のリストに配置されていた場合は、また確率的に上に現れるpこのデータ構造で何かをクエリするには、常に最上位のレーンをチェックして、それが見つかるかどうかを確認します。表示される要素が大きすぎる場合は、次の最下位のレーンにドロップして、再度検索を開始します。これは、バイナリ検索のようなものです。Wikipedia では、わかりやすい図を使って、非常にわかりやすく説明しています。もちろん、メモリ使用量は悪化し、キャッシュ パフォーマンスは向上しませんが、一般的には高速になります。

参考文献

おすすめ記事