問題タブ [skip-lists]

サイズ (N) のメモリに既に並べ替えられたセットがあり、それを redis にダンプしたいのですが、head または tail を最初に挿入した場合、O(N) で実行できますか? または問題ではなく、挿入は O(log(N!)) ~ O(N log(N)) になります

詳細については、ハッシュマップとスキップリスト (順序付け用) を使用して、redis の並べ替えられたセットを実装します。

編集:この質問は、かなり長い間回答されていないか、少なくとも私にとっては少しあいまいです: Redis:挿入された要素が先頭または末尾にある場合、ZADD は O(logN) よりも優れていますか?

インターネットでスキップリストについて読んだところ、さまざまなデータ構造とすべてでそれがどのように機能するかがわかった. しかし、挿入時に二重連結リストをソートしたいので、二重連結リストでスキップリストを実装したいと本当に思っています。その時点で要素を挿入するときは、ソートされた方法でのみ挿入する必要があることを意味します。

ここでは、二重連結リストにデータをソートして挿入するメソッドを実装していますが、要素数が非常に多い場合、データを挿入してリストをソートして作成するのに時間がかかります。

既存の関数にスキップ リスト アルゴを追加する方法を教えてください。または、すべてを書き直す必要がありますか? 実装の助けをいただければ幸いです

コードは次のとおりです。

アンロールされたスキップ リストに関する情報が Google/Wikipedia にないのはなぜですか? たとえば、展開された連結リストとスキップ リストの組み合わせ。

1次元の浮動小数点間隔の大きなセットを考えてみましょう。

与えられた点を含むすべての間隔を見つけることが望まれます。たとえば、ポイント = 1.2 を指定すると、アルゴリズムは最初の間隔を返す必要があり、ポイント = 2.0 を指定すると、上記の例の最初の 2 つの間隔を返す必要があります。

私が扱っている問題では、この操作を多数の間隔で何度も繰り返す必要があります。したがって、ブルート フォース検索は望ましくなく、パフォーマンスは重要な要素です。

それについて調べた後、計算幾何学のコンテキストでインターバルスキップリストを使用してこの問題が解決されていることがわかりました。シンプルで効率的な C++ 実装が利用できるかどうか疑問に思っていました。

編集:問題についてより正確に言うと、N 個の間隔があり、M ポイントの場合、どの間隔に各ポイントが含まれているかを判断する必要があります。N と M は大きな数で、M は N よりも大きくなります。

私はこれで2か月間立ち往生しており、家庭教師とインターネットを試しました. 私が学んだことはすべて窓からゴミ箱に飛んでいるほど長い間悪化していると思います.

スキップ リスト ノードを宣言して使用したい。ノード配列を初期化してアクセスする方法がわかりません。ノードは配列をすべて NULL に初期化すると思いますが、ノード配列のインデックス [0] をその前のノード インデックス [0] を指すように設定できないのはなぜですか?

これが私のノードです：

リストの構造体はありません。メインで組み立てているだけです

次に、headSentinels を最初のノードにアタッチします。

メインでノードを使用する方法を理解できれば、残りのスキップ リストを理解できます。何かが私を縛っています、そしてそれはおそらく簡単です。

プログラムをコンパイルできますが、数値を挿入しようとすると、セグメンテーション エラーが発生します。

実際のスキップリストを作成する前に、最初に配列 [0] でリンクされたリストを組み立てたいだけです

スキップリストを実装しています。それが何であるかは重要ではありませんが、現在 1000 ノードでは機能しますが、10000 ノードでは機能しません。驚いたことに、変わってはいけない多くのことがゴミの値に変わっていました。たとえば、関数 insertNode の前後に inputValue を出力しました。常にインクリメントする必要がある場合でも、ゼロにリセットされることがあります。コードを見てみましょう (読み取りファイルの入力をスキップします。問題は while サイクルで発生します):

ヴァルグリンドを走らせました。無効なメモリの書き込み/読み取りが発生した後、変数が変更されたため、少なくとも私はそう信じています。そのため、サニティ チェックを追加しました。そして、私が思ったように、キーにアクセスしようとする前に無効なメモリの書き込み/読み取りはありませんでした[9999999999999999999999]。しかし、その行は int sanitycheck is changed しか実行できませんが、私は決して実行しません。

最後に、insertNode のコードを次に示します。これを引き起こす可能性のあるものは何もありません：

そして構造：

私はmallocも使用していません。ポインター操作はありますが、valgrind は私が何か悪いことをしたかどうかを検出する必要がありますよね? メモリが不足している場合は、例外が発生します。私が作成し、決してアクセス/書き込み/変更しない int が変更される可能性はありますか? 長文で申し訳ありませんが、どこに問題があるのか​​わかりません。

健全性チェックなしの Valgrind 出力 (keys[999...9]): http://pastebin.com/hWH3fri2

155 行目は while (inputFile >> inputKey) です。