0

アンロールされたスキップ リストに関する情報が Google/Wikipedia にないのはなぜですか? たとえば、展開された連結リストとスキップ リストの組み合わせ。

4

2 に答える 2

1

おそらく、パフォーマンスが向上したとしても、通常はあまり改善されず、正しくコーディングするのにいくらか関与するためです。

まず、展開された連結リストは通常​​、非常に小さなノード サイズを使用します。ウィキペディアの記事にあるように、「ノードが単一のキャッシュ ラインまたはその数倍のキャッシュ ラインを満たすのに十分な大きさ」です。最新の Intel プロセッサでは、キャッシュ ラインは 64 バイトです。スキップ リスト ノードには、ノードあたり平均2 つのポインターがあります。つまり、フォワード ポインターは、ノードあたり平均 16 バイトです。さらに、ノードのデータが何であれ、スカラー値の場合は 4 または 8 バイト、参照の場合は 8 バイト (ここでは 64 ビット マシンを想定しています)。

つまり、「要素」の合計は 24 バイトです。ただし、要素のサイズは固定されていません。それらには、さまざまな数の前方ポインターがあります。したがって、各要素のフォワード ポインターの最大数の配列を割り当てて各要素を固定サイズにする必要があります (32 レベルのスキップ リストの場合は 256 バイトが必要です)。または、正しいサイズの動的に割り当てられた配列を使用します。 . したがって、要素は本質的に次のようになります。

struct UnrolledSkipListElement
{
    void* data; // 64-bit pointer to data item
    UnrolledSkipListElement* forward_pointers; // dynamically allocated
}

これにより、要素のサイズがわずか 16 バイトに減少します。ただし、アンロールから得たキャッシュに適した動作の多くが失われます。次にどこに行くかを見つけるには、forward_pointers配列を逆参照する必要がありますが、これによりキャッシュ ミスが発生するため、展開によって得られた節約がなくなります。さらに、動的に割り当てられたポインターの配列は自由ではありません。そのメモリの割り当てには、(わずかな) オーバーヘッドが伴います。

その問題を回避する方法を見つけることができたとしても、まだ多くは得られません。リンクされたリストを展開する大きな理由は、検索するときにすべてのノード (見つけたノードまで) にアクセスする必要があるためです。したがって、各リンク トラバーサルで節約できる時間はいつでも、非常に大きな節約になります。しかし、スキップ リストを使用すると、大きなジャンプが発生します。たとえば、完全に編成されたスキップ リストでは、最初のジャンプで半分のノードをスキップできます (探しているノードがリストの後半にある場合)。展開されたスキップ リスト内のノードに 4 つの要素しか含まれていない場合、レベル 0、1、および 2 でのみ節約できます。より高いレベルでは、3 つ以上先のノードをスキップしているため、結果として、キャッシュミス。

そのため、スキップ リストは展開されていません。これは、実装に多少の手間がかかり、パフォーマンスが向上したとしてもあまり効果がないためです。また、リストが遅くなる可能性があります。

于 2015-02-16T14:13:02.060 に答える
0

リンクされたリストの複雑さは O(N) です

スキップ リストの複雑さは O(Log N)

展開されたリンク リストの複雑さは、次のように計算できます。

O (N / (M / 2) + Log M) = O (2N/M + Log M)

ここで、M は単一ノードの要素数です。

Log M は有意ではないため、

Unrolled Linked List の複雑さは O(N/M)

Skip リストと Unrolled リンク リストを組み合わせると仮定すると、新しい複雑さは次のようになります。

O(Log N + "N1/M などの展開されたリンク リストからの何か")

これは、「新しい」複雑さが、最初に誰かが考えるほど良くないことを意味します。新しい複雑さは、元の O(Log N) よりもさらに悪い可能性があります。実装もより複雑になります。したがって、ゲインは疑わしく、かなり疑わしいです。

また、単一のノードには多くのデータがありますが、単一の「前方」配列しかないため、「ツリー」もバランスが取れておらず、これにより方程式の O(Log N) 部分が台無しになります。

于 2015-02-16T19:45:48.583 に答える