問題タブ [skip-lists]

辞書を表すデータ構造を考案するように依頼されました。ディクショナリには、個別のキー番号を持つアイテムが保持されます。データ構造は、O(1) 時間で次の操作をサポートする必要があります: insert(x)、delete(x)、findMin()、findMax()、successor(x)、predecessor(x)。また、search(x) 操作は O(log n) 時間で行う必要があります。

課題は、スキップ リスト、ハッシュ テーブル、およびヒープに関するものでした。最適な構造はスキップ リストになると思いますが、O(1) tine で挿入と削除を実装する方法が見つかりませんでした。助言がありますか？

スタック オーバーフローに関する別の提案に従って、スキップ リストに関するJohn Shipman の優れた記事と、彼の Python 実装に関するドキュメントを調べました。コードはすべてありますが、説明のためにスニペットに分割されています。これは Web ページには最適ですが、そこからファイルを抽出する必要はありません。私が見つけたすべてのリンクは、同じページを指しています。

pip install pyskip他の実装をインストールします。他にどこを見るべきかわかりません。

REDIS のドキュメントでは、ソートされたセットに対する挿入操作と更新操作は O(log(n)) であると記載されています。

この質問では、基礎となるデータ構造であるスキップ リストに関する詳細を指定しています。

ただし、私がよく知らない REDIS 実装に依存する特殊なケースがいくつかあります。

• ソートされたセットの先頭または末尾に追加することは、おそらく O(log(n)) 操作ではなく、O(1)ですよね? この質問は留保に同意するようです。
• 要素を取り出してわずかに異なるスコアで再度挿入するか、順序が変更されていないことを確認する必要があるため、順序が変更されていない場合でもメンバーのスコアを更新することはまだ O(log(n)) です。変更されないため、違いはスコアの挿入または更新の間の一定の操作のみです。右？この場合、私が間違っていることを本当に願っています。

どんな洞察も大歓迎です。

Java の Collections Framework のほとんどのクラスは、デフォルトでは非同期ですが、スレッドセーフにする必要がある場合は、同期するクラスにすることができます。同期にはパフォーマンスのペナルティがあるため、スレッドセーフである必要のないものを書いている場合は、非同期バージョンを使用する方がよいでしょう。

しかし、ConcurrentSkipListMapこのスキームには従いません。非同期バージョンはありません。SkipListMapCollections Framework の残りの部分に沿って、スレッド セーフを必要としないアプリケーション用のより高速な unsynchronized がないのはなぜですか?

私が考えることができるのは、Skip List の最も単純な実装はすでにスレッドセーフであるため、同期バージョンを使用してもパフォーマンスが低下することはないということだけです。これにはある程度の意味がありますが、ソース コードを調べても、それはまったくわかりません。コードにブロックはありませんがsynchronized、Javadoc は

このクラスは、SkipLists の並行バリアントを実装します...

これは、アルゴリズムを変更してスレッドセーフにするのが面倒であることを示唆しています。後で、私たちは読んだ

これらのリストの基本的な考え方は、同時挿入との競合を避けるために、削除時に削除されたノードの「次の」ポインタをマークすることです...

また、何らかのオーバーヘッドが関係しているようにも聞こえます。

このオーバーヘッドが非常に小さいため、非スレッドセーフにする価値がないというだけSkipListMapですか?

きめの細かいロック メカニズムを使用して、c でロック ベースのスキップリストを実装しようとしています。コードを実行すると、適用されたロック メカニズムが粗いように見えます。ノード構造内で定義された pthread_mutex_t ロック変数を使用して、挿入のために前のノードにロックを設定し、使用後に解放します。リスト全体がロックされているわけではなく、ノードのみがロックされていますが、まだ大まかなロック メカニズムを実装しているようです。ロック メカニズムが実行されるコードの一部を以下に示します。実装が間違っていますか？

スキップリストのコーディングで従う論文は

編集:スキップリストにノードを挿入するためのコード

スキップリストへの挿入に問題があります。スキップ リストに要素を挿入すると、上位レベルではなく下位レベルにのみ要素が追加されます。ダウンレベルに行こうとすると爆発します。あなたの助けに感謝。ありがとうございました。