data-structures - スキップリスト-これまでに使用したことがありますか？

Question

ここの誰かがスキップリストを使ったことがあるかどうか疑問に思います。平衡二分木とほぼ同じ利点があるように見えますが、実装は簡単です。持っている場合、あなたはあなた自身を書いたのですか、それとも事前に書かれたライブラリを使用しましたか（もしそうなら、その名前は何でしたか）？

score 17 · Accepted Answer

私の理解では、データベースで使用するためのB ツリーほど、バイナリツリー(赤黒ツリーなど) に代わる有用な代替手段ではないため、レベル数を実行可能な最小値に抑えて対処することができます。パフォーマンス特性のために、基数 2 のログではなく基数 K のログを使用します。確率的スキップリストのアルゴリズムは、対応する B ツリーアルゴリズムよりも (IMHO) 正しく取得する方が簡単です。さらに、ロックフリースキップリストに関する文献もいくつかあります。数か月前にそれらを使用することを検討しましたが、HDF5ライブラリを発見する努力を断念しました。

このテーマに関する文献:

ビル・ピューによる論文:

非学術論文/チュートリアル:

Eternally Confuzzled (いくつかのデータ構造について議論があります)
Thomas A. Anastasio による「スキップリスト」

score 9 · Accepted Answer

実際、私のプロジェクトの 1 つで、独自の完全な STL を実装しています。そして、スキップリストを使用して実装しましたstd::map。私がそれを採用した理由は、バランスのとれたツリーのパフォーマンスに非常に近いシンプルなアルゴリズムでありながら、はるかに単純な反復機能を備えているためです。

また、Qt4 の QMapもスキップリストでしたstd::map。

score 8 · Accepted Answer

何年も前に、私は確率的アルゴリズムのクラスのために独自のものを実装しました。ライブラリの実装については知りませんが、長い間です。実装は非常に簡単です。私が思い出したように、それらは大規模なデータセットに対していくつかの非常に優れた特性を持ち、リバランスの問題のいくつかを回避しました. 実装も一般的なバイナリ試行よりも簡単だと思います。素敵な議論といくつかのサンプル C++ コードがここにあります:

http://www.ddj.us/cpp/184403579?pgno=1

実行中のデモンストレーションを含むアプレットもあります。かわいい 90 年代の Java の光沢はこちら:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

score 7 · Accepted Answer

Java 1.6 (Java SE 6) では、 ConcurrentSkipListSetおよびConcurrentSkipListMapがコレクションフレームワークに導入されました。ですから、誰かが実際にそれらを使用していると推測します。

スキップリストは、マルチスレッドの状況でロックの競合がはるかに少ない傾向があり、(確率的に) ツリーに似たパフォーマンス特性を持っています。

William Pugh による元の論文[pdf]を参照してください。

score 2 · Accepted Answer

私は、数年前にルールエンジンのリバーススキップリストと名付けたバリアントを実装しました。ほとんど同じですが、参照リンクは最後の要素から逆方向に実行されます。

これは、コレクションのバックエンドに向かう可能性が最も高い、並べ替えられたアイテムを挿入する方が高速だったためです。

これは C# で記述されており、正常に機能するようになるまで数回の反復が必要でした。

score 2 · Accepted Answer

スキップリストには、二分探索アルゴリズムによって達成されるのと同じ対数時間の検索制限がありますが、エントリの挿入または削除時にメソッドを更新するためにそのパフォーマンスが拡張されます。それにもかかわらず、スキップリストには境界が予想されますが、並べ替えられたテーブルのバイナリ検索には最悪の場合の境界があります。

score 1 · Accepted Answer

スキップリストは簡単に実装できます。ただし、挿入と削除の場合のスキップリストのポインタの調整には注意が必要です。これを実際のプログラムで使用したことはありませんが、実行時のプロファイリングを行っています。スキップリストは検索ツリーとは異なります。類似点は、スプレイツリーと同様に、一定期間の辞書操作に対して平均 log(n) が得られることです。不均衡な検索ツリーよりは優れていますが、バランスの取れたツリーよりは優れていません。

すべてのスキップリストノードには、スキップリストのさまざまなレベルへの current->next() 接続を表すフォワードポインターがあります。通常、このレベルは最大 ln(N) で制限されます。したがって、N = 100 万の場合、レベルは 13 です。これだけ多くのポインターがあり、Java では、参照データ型を実装するためのポインターの数の 2 倍を意味します。バランスの取れた検索ツリーは少なく、同じランタイムを提供します!!.

SkipList 対 Splay Tree 対 Hashディクショナリルックアップ ops のプロファイリングでは、ロックを削除したハッシュテーブルは 0.010 ミリ秒未満の結果をもたらします。

data-structures - スキップリスト-これまでに使用したことがありますか？

7 に答える 7

Related

Reference