問題タブ [skip-lists]

スキップリストで指定された要素 x を見つける方法を探しています。これはリストの k 番目です (その前に k-1 要素があります)。アルゴリズムの予想時間は O(log K) である必要があります

O（log n）を取る既知のアルゴリズムを見つけましたが、ここではO（log K）です。

よろしくお願いします

ジェネリックを使用して SkipList を実装しようとしていますが、問題が発生しました。ノードをインスタンス化できないようです。

ノード クラス:

リストクラス:

その行の をp1 = new SkipNode<E>(SkipNode.negInf, null);削除し<E>て this:p1 = new SkipNode(SkipNode<E>.negInf, null);に変更しようとしましたが、これはあまり意味がありませんが、試してみようと思いました。また、パラメーターで「-oo」を実行しようとしましたが、Node コンストラクターのパラメーターを文字列と整数に変更する必要があります。

私は何を間違っていますか？

SkipList を作成しようとしていますが、ジェネリック データ型を使用するメソッドがあります。

ここにあなたを連れて行きます：

問題はcompareTo()方法にあります。メソッドはcompareTo()type に対して未定義ですE。Eclipse では、次のような 2 つの型キャストを追加する必要があります。

((String) p.getRight().getKey().compareTo((String) key) <= 0 )

なぜそれが欲しいのStringですか？データ型は何でもかまいません。代わりにtypecast を実行しようとしEましたが、Eclipse はそれを に戻したいと考えていますString。どんな助けでも大歓迎です。

上記のコードを実行すると、挿入された最初の要素 (この例では 3) は常にリストの最後の要素になります。他のすべての要素は正しい順序で挿入されます。上記のプログラムは、2-39-50-500-2000-3 を表示します。さらに 100 個の値を挿入すると、より大きな値を配置しても、挿入された最初の要素が常に最後になることを除いて、それらはすべて正しい位置に挿入されます。

指を置くことはできませんが、挿入を配置するときにリストの最後の要素を無視していることは明らかです。誰かがこれに光を当てることができれば感謝します。ありがとう！

最小の追加メモリ オーバーヘッドを使用して BST と同じくらい優れたパフォーマンスを発揮するスキップ リストを実装しようとしていますが、現時点では、メモリ制限を考慮していなくても、SkipList 実装のパフォーマンスは非常に素朴なバランス BST 実装とはかけ離れています。いわば、手作りのBTS :) -

参考として、William Pugh PUG89の元の論文と、Sedgewick -13.5- の Algorithms in C で見つけた実装を使用しています。私のコードは再帰的な実装です。挿入操作と検索操作の手がかりは次のとおりです。

これは、検索操作のコードです。

sl_node -skip list node- は次のようになります。

おわかりのように、これは本の実装と比較すると特別なことも高度なものも何もない実装ですが、Balaced BTS コードはここでは必要ないと思うので共有しません。新しいノードの高さが 16*lg(n) より大きい場合の挿入 (n はノードの数)。

つまり、私が言ったように、最大​​の高さが最高の理論上のものよりも 16 倍大きい場合にのみ、3 つのバランスを再調整します。

ただし、最初に、p=.5 および n=262144 を使用して、いくつかのデータを見てみましょう。SkipList 内のノードのレベルには、次の分布があります。

これは、記事の理論とほぼ完全に一致します。つまり、レベル 1 が 50%、レベル 2 が 25% などです。入力データは、std::default_random_engine と均一な int 分布を備えた std::random_device として知られる、利用可能な最高の疑似乱数ジェネレーターから取得されました。入力はかなりランダムに見えます :) !

SkipList 内の 262144 個の要素をランダムな順序で「すべて」検索するのに必要な時間は、私のマシンでは 315 ミリ秒ですが、単純な BTS での同じ検索操作の所要時間は 134 ミリ秒であるため、BTS はスキップリスト。これは、「スキップ リスト アルゴリズムは、バランスの取れたツリーと同じ漸近的な期待時間境界を持ち、シンプルで高速で、使用するスペースが少ない」PUG89から期待していたものとはまったく異なります。

ノードの「挿入」に必要な時間は、SkipList の場合は 387 ミリ秒、BTS の場合は 143 ミリ秒で、単純な BST のほうがパフォーマンスが優れています。

入力番号のランダムなシーケンスを使用する代わりにソートされたシーケンスを使用すると、物事はもう少し面白くなります。ここでは、私の貧弱な自家製 BST が遅くなり、262144 のソートされた int の挿入に 2866ms かかりますが、SkipList は 168ms しか必要としません。

しかし、検索時間に関しては、BST はまだ高速です! ソートされた入力の場合、77ms に対して 234ms であり、この BST は 3 倍高速です。

p-factor の値が異なると、わずかに異なるパフォーマンス結果が得られました。

最後になりましたが、メモリ使用量のグラフは、ノードあたりのレベル数を増やすと、メモリ フィンガープリントに大きな影響を与えることを示しています。メモリ使用量は、すべてのノードの追加ポインタを格納するために必要なスペースの合計として計算されます。

このすべての後、追加のメモリ オーバーヘッドを考慮せずに、BTS と同じくらい優れたパフォーマンスを発揮する SkipList を実装する方法について、どなたかコメントをいただけませんか?

SkipListに関するDrDobbs LINKの記事について知っています。すべての論文を調べました。検索および挿入操作のコードは、PUG89の元の実装と正確に一致するため、私のものと同じくらい優れているはずであり、記事はパフォーマンスを提供しませんとにかく分析しましたが、他のソースは見つかりませんでした。手伝って頂けますか？

どんなコメントでも大歓迎です！

ありがとう！:)

skipListSearch()誰かがandskipListInsert()メソッドを説明してもらえますか? このコードは、Adam Drozdek の著書Data Structures and Algorithms in C++からのものです。このスキップリストでは、挿入にリストの再構築は必要なく、異なるレベルのノードの分散が適切に保たれるようにノードが生成されます。

maxLevel = 4. 15 要素の場合、必要な 1 ポインター ノードの数は 8、2 ポインター ノードは 4、3 ポインター ノードは 2、4 ポインター ノードは 1 です。ノードが挿入されるたびに、1 から 15 までの乱数 r が生成されます。r < 9 の場合、レベル 1 のノードが挿入されます。r < 13 の場合、第 2 レベルのノードが挿入されます。r < 15 の場合、それは第 3 レベルのノードです。r = 15 の場合、レベル 4 のノードが生成され、挿入されます。

自分でクラスを作成するよりも、Java パッケージの既存のクラスを使用する方がよいと同僚が認めたくないので、私は同僚と熱心に議論しています。

イテレータも機能するように、スレッドセーフな方法でセットにアクセスしたいと考えています。

クラスは見つかりましたが、必要のないインターフェイスConcurrentSkipListSetを実装する必要があります。Comparable彼は、これは同期化されたもの全体を書くよりも悪いと主張しています。私はノーと言います。

実装させない ConcurrentSkipListSet よりも優れた Java クラスはありますComparableか?