問題タブ [skip-lists]

たくさんのイベントが予定されていますが、スケジュールされたイベントに 10 日間の間隔があり、その 10 日間でイベントが行われていないかどうかを確認したいと考えています。10日間隔を見つけるための適切なデータ構造と検索アルゴリズムはありますか?

Pythonでスキップリストを実装する方法を考えていました。

リンク リストを作成しましたが、リンク リストのさまざまなレベルを作成する方法と、ノードを検索またはリストに挿入するときにリストのすべてのレベルを反復処理する方法に問題があります。

質問がここにあるのか、プログラマー (または他の SE サイト) にあるのかはわかりませんが、バランスの取れたバイナリ ツリーとインデックス可能なスキップリストの関連する違いに興味がありました。この問題は、この質問のコンテキストで発生しました。ウィキペディアから：

スキップ リストは確率的なデータ構造であり、多くのアプリケーションで選択される実装方法としてバランス ツリーに取って代わる可能性が高いと思われます。スキップ リスト アルゴリズムは、バランス ツリーと同じ漸近的な期待時間境界を持ち、より単純で高速で、使用するスペースが少なくなります。

スキップリストのスペース要件は、階層の深さに依存しませんか? そして、少なくとも検索に関しては、二分木の方が使いやすいのではないでしょうか? スキップリストのメリット/デメリットは他にもありますか?

整数のスキップ リストを実装しました。メソッドの挿入をテストするときは、1 から 1000000 までの自然数をカウンター j の for ループに挿入します。私もストップウォッチを使っています。付録: 実際のプログラムでは、値は double です。(しかし、それは問題ではないはずです) 疑似コード:

グラフの時間/ノード数を作成すると、線形ですが、グラフのステップ/ノードは予想どおり対数です。(steps は、メソッド挿入のループサイクル (~operations) の数です)。

メソッドの挿入により、追加のノードが作成され、いくつかのポインターが設定されます。ノードは次の方法で実装されます。

スキップ リストはノードで構成されます。

Insert はクラス SkipList で定義され、次のように機能します。

ノードがブロックであり、n = node.depth right neighbours が配列に格納されているスキップ リストのバージョンも実装しましたが、グラフは時間/数値です。ノード数は依然として線形です (ステップ数/ノード数は対数です)。

「n」（格納する要素の数）を事前に知っていれば、配列のようなスキップリストは非常に効率的であると言うのは正しいでしょうか？

スキップ リストの最大レベルは です。スキップ リスト(log n + 1)を作成する前に最大レベルを知る必要があるため、格納される要素の数を把握する必要があります。

スキップリストの平均予想検索時間を決定するルビ関数を作成しようとしています。私は強い数学のバックグラウンドを持っていないので、この関数から得られる結果は正しくないと思います。

n= リスト内の要素数

base= 昇格確率の分母。つまり、4 つのノードのうちの 1 つが昇格された場合、ベース = 4

スキップリストとベースの要素数を取り、平均検索時間を返すRubyの方程式をどのように表現すればよいですか?

Java のConcurrentSkipListMapに基づいて同時スキップ リスト マップを実装しています。違いは、リストに重複を許可することと、リストをインデックス可能にすることです(リストの N 番目の要素を見つけるには O(lg( n)) 時間、標準のスキップ リストのような O(n) 時間ではなく)。これらの変更は問題を引き起こしていません。

さらに、スキップ リストのキーは可変です。たとえば、リスト要素が整数 {0, 4, 7} の場合、リスト構造の変更を求めることなく、中間要素のキーを [0, 7] の任意の値に変更できます。キーが (-inf, -1] または [8, +inf) に変更された場合、要素は削除され、リストの順序を維持するために再度追加されます。これを削除とそれに続く O(lg(n)) 挿入として実装するのではなく、これを削除とそれに続く線形トラバーサルとそれに続く O(1) 挿入として実装します (O(1) - 99 の予​​想される実行時間で)ノードが隣接ノードと交換される時間の割合)。

完全に新しいノードを挿入することは (起動後に) まれであり、ノードを削除する (すぐに再追加することなく) ことは決してありません。ほとんどすべての操作は、i 番目のインデックスの要素を取得するための elementAt(i)、またはキーが変更された後にノードを交換するための操作です。

私が直面している問題は、キー変更クラスを実装する方法にあります。概念的には、次のようなことをしたいと思います

(insertから呼び出されるサブメソッドはrun、同じ場所に同時に挿入しようとする 2 つのノードの問題を処理するために CAS を使用します (ConcurrentSkipListMap競合する挿入を処理する方法と同様) - 概念的には、これは最初のノードがノードをロックした場合と同じですただし、競合がない場合はオーバーヘッドが削減されます)。

このようにして、リストが常に順序どおりであることを確認できます (キーの更新が少し遅れても、最終的に更新が行われることは確実なので問題ありません。ただし、リストが順不同になると、事態は混乱する可能性があります)。問題は、このようにリストを実装すると、非常に多くのスレッドが生成され、1 つにつき 1 つNode(リストに数千のノードがある) になることです。それらのほとんどは、特定の時点でブロックされますが、数千のスレッドが発生することを懸念しています。スレッドをブロックすると、オーバーヘッドが非常に高くなります。

もう 1 つのオプションは、updateメソッドを同期させ、Runnableからインターフェイスを削除するNodeことです。これにより、2 つのスレッドが で更新をエンキューしNode、別のスレッドでこれらの更新を処理するのではなく、2 つのスレッドが交互にNode#updateメソッドを実行します。問題は、これがボトルネックになる可能性があることです。8 つの異なるスレッドがすべて一度に同じノードを更新することを決定した場合、キューの実装は問題なくスケーリングされますが、同期された実装は 8 つのスレッドのうち 7 つをブロックします (その後、6 つのスレッド、次に 5 つのスレッドをブロックするなど)。

したがって、私の質問は、スレッドの数を減らすことを除いて、キューの実装のようなものをどのように実装するか、または潜在的なボトルネックの問題がないことを除いて、同期された実装のようなものをどのように実装するかです。

最近、並べ替えられたリストで数値を検索するアルゴリズムに遭遇しました。これがその方法です。

与えられた: 与えられた数が検索されている数よりも大きいか小さいかを教えてくれるオラクル。

リストの最初の要素から始めます。1要素先にスキップして、検索されている数より先に進んでいるかどうかをオラクルに尋ねます.

そうでない場合は、2 つの要素をスキップして、行き過ぎたかどうかをオラクルに尋ねます。

4要素先をスキップしない場合など....

検索対象の番号を通過させる最初のスキップが見つかったら、検索対象の番号を含むサブインターバルを特定できます。

最後に、部分区間で二分探索を実行します。

このアルゴリズムの名前を知りたいと思っていたので、さらに調査を行うことができました。

ありがとう

だから私はスキップリストについて少し読んで、現在それを実装しています. しかし、これまで本当に得られなかったことが 1 つあります。スキップ リストがランダム化されるのはなぜですか? 私が見つけたすべての情報源で、スキップ リストは乱数を使用してアイテムが挿入されるレベルを決定していました。最適値を計算できませんでしたか? それとも、「4 つおきの項目」を上のレベルに挿入する必要があると言えませんか?