問題タブ [skip-lists]

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

最近、スキップ リストと呼ばれるデータ構造に出会いました。二分探索木と非常によく似た動作をしているようです。

二分探索木に対してスキップ リストを使用する必要があるのはなぜでしょうか。

[解決済み]

そこで、ソートされた二重リンクスキップリストを作成してみることにしました...

どのように機能するかをよく理解していると確信しています。x を挿入すると、プログラムは x を配置する適切な場所をベース リストから検索し (ソートされているため)、(概念的には) コインを裏返し、「コイン」が に落ちた場合、その要素はその上のリストに追加されます。 (または要素を含む新しいリストが作成されます)、その下の要素にリンクされ、コインが再び裏返されます。「コイン」がいつでも b に着地すると、挿入は終了します。また、すべてのリストに -infinite を開始点として格納して、開始点より小さい値を挿入できないようにする必要があります (つまり、値が見つからないことを意味します)。

x を検索するには、「左上」(最も高いリストの最も低い値) から開始し、「右に移動」して次の要素に移動します。値が x より小さい場合は、「行き過ぎ」て値が x より大きいまで、次の要素に進みます。この場合、最後の要素に戻って 1 レベル下に移動し、x が見つかるか、x がまったく見つからなくなるまで、この連鎖を続けます。

x を削除するには、単に x を検索し、リストに表示されるたびに削除します。

今のところ、番号を格納するスキップ リストを作成するだけです。STL には私を支援できるものは何もないと思うので、整数値を保持し、検索、削除、および挿入のメンバー関数を持つクラス List を作成する必要があります。

私が抱えている問題は、リンクを扱うことです。前の要素と前の要素へのポインターを使用して「水平」リンクを処理するクラスを作成できると確信していますが、「垂直」リンクを処理する方法がわかりません (対応する要素を指す他のリストに?)

私の論理に欠陥がある場合は教えてください。主な質問は次のとおりです。

1. 縦リンクの対処法とリンクの考え方が正しいかどうか
2. クラス List のアイデアを読んだので、List は単一の整数ではなく、整数のベクトルを保持する必要があると考えています。実際、私はかなり前向きですが、検証が必要です。
3. コイントスは int 関数を呼び出すだけで、rand()%2 が 0 または 1 の値を返し、それが 0 の場合は値が「レベルアップ」し、0 の場合は挿入が終了したと想定しています。これは間違っていますか？
4. -infinite に似た値を格納する方法は?

編集:私はいくつかのコードを書き始め、List コンストラクターの処理方法を検討しています....その構築では、「-infinite」値を vectorname[0] 要素に格納する必要があると推測しています。作成後に insert を呼び出すだけで、x を適切な場所に配置できます。

スキップリストからノードを削除する際に問題が発生しました。私は次の構造を持っています：

問題は、与えられた値を持つノードを検索して削除する関数にあると思います。関数は次のように実装されます。

関数はそのままで正常に動作しますが、コメントされた2行のコメントを外すと、リストが壊れているようです。ブレークとは、次のテストコードが終了しないことを意味します。

問題は、リストにさらに値を挿入する最後のforループにあります。これらの2行がコメントアウトされている場合、プログラムは約10秒で終了します。コメントを外すと、数分で終わらないので無限ループに入っているようです。それがスキップリストからノードを削除する正しい方法であるかどうかわからないので、挿入関数も投稿しています：

だから、私の質問は次のとおりです。

1. プログラムが壊れてしまうのはなぜですか。また、メモリから削除したいノードを実際に削除しながら、プログラムを機能させるにはどうすればよいですか。
2. これはスキップリストを実装する正しい方法ですか、それとも間違ったアプローチを使用していますか？

ロックフリースキップリストを実装する必要があります。論文を探してみました。残念ながら、私が見つけたのは、ロックフリーの単一リンクリスト（多くのフレーバー）だけでした。しかし、ロックフリースキップリストを実装するにはどうすればよいですか？

こんにちは皆さん、私は新しいので、スキップリストで問題が発生したので、あなたが助けてくれると確信しています。ここにコードがあります

私は正常にコンパイルしますが、実行のために実行すると、突然動作しなくなります助けてください

最近スキップリストについて読んでいます。

静的データセットに対して非常に複雑なSQLクエリを実行するWebアプリケーションがあります。

SQLクエリのmd5ハッシュを生成し、コレクションに存在する場合はクエリのキャッシュされたデータセットを返すキャッシュシステムを実装したいと思います。

辞書とスキップリストのどちらのアルゴリズムが良いでしょうか？なんで？

http://msdn.microsoft.com/en-us/library/ms379573%28VS.80%29.aspx#datastructures20_4_topic4

私は本当にこのリストの確率のことを理解していません. 「n/2 + 1 個以下のノードを検査する必要がある」というステートメントに加えて (n はリストの長さ)。 + 2 つのノードを調べる". この声明は、次のリンクで読みました: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

私はスキップ ポインターについて読んでいました。ここで「等間隔」が何を意味するのか誰か教えてもらえますか? また、Java または Python でそのようなことを行うコードも見たいと思います。

プロジェクトに実装するには、リストタイプのデータ構造が必要です。実際には、ある種のリストである必要はありませんが、高速である必要があり、データ（他のデータ構造）を常に挿入/削除/取得するために使用します。何かを挿入、検索、再挿入、削除、再検索などを行う可能性があるため、アクションはランダムです。

これまでのところスキップリストが最速であることがわかりましたが、それよりも速いものは何ですか？