問題タブ [skip-lists]

ではredis.h、skipnode は次のように定義されています。

var とはspanどういう意味ですか? この変数は何を保存しますか?

n 個の要素を挿入した後、スキップ リストによって使用されると予想されるスペースはどれくらいですか?

最悪の場合、スペースの消費量が際限なく増える可能性があると予想しています。

ウィキペディアには「スペース O(n)」とあります。

これはどのように証明できますか？

（単純なリンクされた）リストを、リンクされたリストから派生したスキップリストに変換したいと思います。paramとして（リンク）リストを取得する変換コンストラクター内で、*でstackoverflowを取得します。私はそのctorをメインから一度だけ呼び出します。新しいSkipListがループワイズで呼び出される可能性はありますか？

スキップリストから要素を挿入または削除するのにかかる時間については、少し混乱しています。

高さHのスキップリストがあり、各レベルにn / 2^iエントリが含まれているとします。
n=キーと値のペアの総数
i=スキップリストのレベルi<=H

ここで、理論に従って、挿入操作は次のアクションを実行します
。1.キー<=挿入されているキーを見つけます。
2.このキーを挿入します
。3。ベースレベルより上のレベルにこのエントリをランダムに作成します。

スキップリストがリンクリストに基づいていると仮定しましょう。
ステップ1：O（n）を取る必要があります。
ステップ2：O（1）である必要があります。
ステップ3：O（log n）時間である必要があります。私はまだこの論理で混乱しています、そしてそれは以下の質問の一部になるでしょう

質問

1. 上記の事実に基づいて、挿入の時間はO（n）+ O（1）+ O（log n）であるべきではありませんか？低次の項を無視すると、O（n）+ O（log n）で進む必要がありますか？

2. ステップ3でも、挿入されているキー<=キーを検索するには、O（n）時間かかり、次に挿入するためにo（1）時間がかかります。挿入の実行時間が非常に複雑になりますか？

スキップリストへの挿入にはO（log n）時間がかかると本は言っています。重要な情報が不足しているに違いありません。この概念をよく理解するのを手伝っていただけませんか。

QMapがrb-treeではなくスキップリストのデータ構造で実現したのはなぜですか？並行性データ構造体とスキップリストの利点については、rb-tree、長所、短所よりも非常に興味深いSOスレッドがあります。それは確かに有用なリンクを備えた非常に興味深いダイアログですが、QMapはスレッドセーフではなく、箱から出してアクセスを同期するためのミューテックスロックを行いません。ラッパーまたはサブクラス化が必要です。

私にとっては、rb-treeの代わりに「手作り」のスキップリストを書くのは簡単ではないので、これも明らかではありません。

スレッドセーフではないQtコンテナのコンテキストでkill機能はありますか？

事前にTnx。

平均的なケースでスキップ リストの挿入の時間計算量が O(log n) である理由と、n 要素のスキップ リストの高さが高い確率で O(log n) である理由を教えてください。そして、各レイヤーの平均検索時間が O(1) である理由。

最近、の実装であるConcurrentSkipListMapに出くわしました。今、なぜそれが として実装されているのだろうか。skip listConcurrentNavigableMapskip list

同時ナビゲート可能なマップskip listの「標準」実装はありますか? 特に良いのは何ですか？skip list

A* のオープン リストにスキップ リストを使用することに興味があります。しかし、私を悩ませているのは、その確率論的な性質です。オープン リストは、非常に小さなセットから膨大な数のノードまでさまざまであり、それぞれのパフォーマンスを維持する必要があります。

私が理解しているように、スキップリストはランダムに小さなデータセットに対して悪い結果を与える可能性が高くなります。多数の短いパスが生成されると、これが問題になる可能性があると思います。

これを修正して、乱数をある程度ウォッチドッグしないように考えていました。各レベルのノード数の現在の合計を保持し、各レベル間のノードの理想的な分散を維持するために、介入してノードを特定のレベルにすることがあります。

特定のアプリケーションでこれがどれだけうまく機能するかはわかりません。代わりに、開いているリストの別のデータ構造に集中する必要があるかもしれません。

私がスキップリストで読んだすべての記事は、そのような最適化について言及していません. 私はパフォーマンスプロファイリングゲーム全体にかなり慣れていないので、文書化されたデータ構造を改善しようとするのをためらっています.

いくつかのブログや lucene の Web サイトでは、lucene が転置インデックスでデータ構造「スキップ リスト」を使用していることを知っています。しかし、私はそれについていくつかのパズルを持っています。

1:一般的に、スキップリストはメモリ上で使用される可能性がありますが、転置インデックスはディスク上に格納されます。では、インデックスを検索するときに lucene はどのように使用するのでしょうか? ディスク上でスキャンするか、メモリにロードするだけですか？

2:skip リストの挿入演算子は、次のレベルに挿入するかどうかを決定するためにランダム (0,1) を使用することがよくありますが、lucenne の導入では、すべての用語で一定の間隔のように見えます。

間違っている場合は修正してください。

これまでに見つけたスキップ リストの実装はすべて、キーを使用し、それらを値に関連付けていました。しかし、私が必要としているのは、インデックス位置 i に値を挿入できるスキップ リストです。これにより、このインデックス i に続くすべての値に対して、インデックスを 1 つ増やしてクエリを実行できます。

ここに明確化のための小さな例があります:

5 がインデックス 3 に挿入され、値 6 が 1 インデックス上に移動したため、現在valueは 6 になっているはずです。

スキップ リストを使用して、このようなデータ構造を構築することができます。こちらのインデックス可能なスキップリストを参照してください: http://en.wikipedia.org/wiki/Skip_list

しかし、実装が見つかりませんでした。このようなデータ構造を持つことは非常に便利です。たとえば、大量のリストに対して多数のランダムな挿入とアクセスがある場合などです。