1

これまでに見つけたスキップ リストの実装はすべて、キーを使用し、それらを値に関連付けていました。しかし、私が必要としているのは、インデックス位置 i に値を挿入できるスキップ リストです。これにより、このインデックス i に続くすべての値に対して、インデックスを 1 つ増やしてクエリを実行できます。

ここに明確化のための小さな例があります:

//pseudocode
//let skipList sk be a list of ints, containing 5 elements.

//insert 6 at index 3
sk.insert(3, 6);

//insert 5 at index 3
sk.insert(3, 5);

//get index 4
int value = sk.get(4);

5 がインデックス 3 に挿入され、値 6 が 1 インデックス上に移動したため、現在valueは 6 になっているはずです。

スキップ リストを使用して、このようなデータ構造を構築することができます。こちらのインデックス可能なスキップリストを参照してください: http://en.wikipedia.org/wiki/Skip_list

しかし、実装が見つかりませんでした。このようなデータ構造を持つことは非常に便利です。たとえば、大量のリストに対して多数のランダムな挿入とアクセスがある場合などです。

4

2 に答える 2

1

あなたが投稿したウィキペディアのページに実装へのリンクがあるようです: http://code.activestate.com/recipes/576930/

パイソンだけど。

または、既存の C++ 実装にリンク幅を追加し、インデックス付きルックアップを実装します。

于 2013-01-17T13:56:44.787 に答える
0

コレクション内で k 番目に大きい値を返すメソッドを持つスキップリスト クラスを C# で実装しました。メソッドに必要なことを正確に実行しますget。

ただし、挿入メソッドは常にリストをソートしたままにするため、位置を指定しません。そのため、位置は既存の値のルックアップによって決定されます。

https://github.com/htoma/algorithms/blob/master/Algorithms/Algorithms/Sources/SkipLists/SkipList.cs、メソッドを見てくださいFindKLargestElement

于 2013-10-21T12:22:13.507 に答える