問題タブ [skip-lists]

http://www.boyet.com/articles/LockfreeQueue.htmlに基づく比較とスワップを使用して、C でロック フリー キューを実装しました。

うまく機能していますが、このキューを実装したロックフリーのスキップリストに統合しようとしています。スキップ リストをプライオリティ キューとして使用しており、プライオリティの競合が発生した場合に複数の値を格納するために、各ノード内のロック フリー キューを使用したいと考えています。ただし、優先順位の競合を検出したときにスキップ リストでノードを管理する方法により、キューが空でない場合にのみ、アイテムをキューに追加できる必要があります。

キューのロックフリーの性質により、この操作を実際に実行する方法がわかりません。

基本的に、アトミックな enqueue_if_not_empty 操作をどのように記述すればよいでしょうか?

Skip lists指定された 2つ (それぞれ n 個のキーを持つ) を時間の複雑さ (最悪の場合) で 1 つSkip ListにO(n)マージするにはどうすればよいですか?

アルゴリズムを探しているだけです - 特定の実装/言語はありません。

私は、プライオリティ キューを実装して、比較的シンプルな Astar の効率的な実装を可能にすることに関心があります (プライオリティ キューはシンプルです)。

スキップ リストは単純な O(1) の抽出最小操作と O(Log N) の挿入操作を提供するため、O(log N) の抽出を持つフィボナッチ ヒープを実装するのがより困難な場合と競合する可能性があります。 Min と O(1) の挿入。まばらなノードを持つグラフには Skip-List が適しているのに対し、ノードが密に接続されている環境にはフィボナッチ ヒープが適していると思います。

これにより、通常はフィボナッチ ヒープが改善される可能性があります。

ConcurrentSkipListSetスキップリストでバックアップされているJava Collection Frameworkで見つけました。しかし、Javaにスキップリストはありますか? 私のユースケースではセットが機能しません。重複をサポートするインデックス可能なリストが必要です。

ZADD の redisドキュメントには、操作が O(log N ) であると記載されています。

ただし、挿入された要素がソート順の最初または最後にある場合、ZADD が O(log N ) よりも優れているかどうかは誰にもわかりませんか?

たとえば、特定の実装では、これは O(1) になる可能性があります。

具体的には、redisチュートリアルには次のように記載されています。

ソートされたセットは、スキップ リストとハッシュ テーブルの両方を含むデュアル ポート データ構造を介して実装されるため、要素を追加するたびに、Redis は O(log( N )) 操作を実行します。

最初と最後に O( k ) 挿入をサポートするようにスキップ リストを変更することはもっともらしく思われます。ここで、 kはスキップ リストの最大レベルです。

私はskiplistを実装していますが、非常に不明確なエラーが表示されます

エラーは、含んでいるのはskipset構造の関数ではないと言っています。ミスなど、エラー一覧をご覧ください

ランク操作をサポートするロックフリーのスキップリスト実装および/または研究論文を知っている人はいますか (つまり、k 番目の要素を見つける)? または、そのような操作が機能しない根本的な理由を知っている人はいますか?

ボーナスポイント：

ガベージ コレクションを想定していない実装。私の経験では、かなりの数の研究論文がメモリ管理を無視しています。

サポート：

ランク操作が通常のスキップリストでどのように行われるかについての説明: 「A Skip List Cookbook」 by William Pugh

ロックフリーのスキップリストのより良い説明の 1 つについては、Keir Fraser による「Practical lock-freedom」を参照してください。

優れたロックフリー スキップリスト実装の 1 つ: http://www.1024cores.net/home/parallel-computing/concurrent-skip-list

ロックフリーの二重連結リストに関する研究は数多くあります。同様に、ロックフリー スキップ リストについても多くの研究があります。しかし、私が知る限り、ロックフリーの二重リンクスキップリストを管理した人は誰もいません。反対の研究、またはその理由を知っている人はいますか?

編集: 特定のシナリオは、高速分位数 (50%、75% など) アキュムレータを構築するためのものです。サンプルは O(log n) 時間でスキップ リストに挿入されます。イテレータを現在の分位数に維持することで、挿入された値を現在の分位数と O(1) 時間で比較でき、挿入された値が分位点の左または右にあるかどうか、および分位点がどのくらい離れているかを簡単に判断できます。その結果、移動する必要があります。前のポインターを必要とするのは左の移動です。

私が理解しているように、一度に挿入および削除する複数のスレッドに直面して、以前のポインターの一貫性を保つことから問題が発生します。解決策には、ポインター マーキングの巧妙な使用がほぼ確実に含まれると思います。

このようなスキップリストでは：

要素4は、2番目と3番目のリストでそれ自体にアクセスできますか？私が尋ねる理由は、スキップリストの削除操作を実装する方法を理解しようとしているためです。ありがとうございました

私はのための最良のアルゴリズムを見つけようとしています

。

の定義がideal skip list、最初のレベルにすべての要素がある場合、上のレベルにはそれらの半分、次のレベルにはそれらの4分の1などがあります。

O(n)特定のノードであるかどうかに関係なく、元のリンクリストの各ノードにコインを投げて、上に行くかどうかに関係なく、現在のノードの2階に別の複製ノードを作成するランタイムについて考えています。 。最終的に、このアルゴリズムはO（n）を生成しますが、より良いアルゴリズムはありますか？

よろしく