問題タブ [skip-lists]

ConcurrentDictionaryJava の .NET にほぼ相当するように見えますConcurrentHashMap。Java に相当する .NET はありますConcurrentSkipListMapか? 見つかりませんでした。

PS インターフェイスのみが動作するという点で同等です。同等の実装 (スキップ リスト) も機能します。

スキップリストがどのように機能するかについての基本的な理解があると思いますが、C初心者であることに加えて、スキップリストに慣れていないため、いくつかの点、特にリストの初期化で混乱しています。これが私が従おうとしているコードです：

私はまだ C でポインターの配列を使って何もしていません。誰かが私を助けてくれるほど親切かどうか、いくつか質問があります。

最初にやっsizeof(int)たら 4sizeof(Node*)が出て 8 だったのでsizeof(Node)12 になると思っていたのに 16 になってしまったのはなぜですか? SkipListその内容のサイズと比較してのサイズと同じ混乱。どちらが原因なのかtypedefアンドを取り出してみましたが、サイズは16のままでした。[1]

次に、[1] が にあるのはなぜstruct Node *next[1]ですか? list->header->next[i]後で必要ですか？next[i]1を超えても大丈夫ですか？各ノードのポインターの数が可変であるという理由だけで、配列にして後で個別に増やしますか?

第三に、なぜlist->header->next[i] = list->header最初は代わりにNULL?

アドバイス/コメントは大歓迎です、ありがとう。

それで、私は最終的に機能するスキップリストの作成を完了したと思い、自分の作業をチェックして検索機能のタイミングを調べる必要があると考えました. 使い方のチュートリアルを見つけて、次のclock()ように実装しました。

これを行って N 対時間をプロットすると、対数的に見えるグラフが得られると思いましたが、代わりに私のグラフは線形に見えます。

時間の複雑さを試してテストするために関数のタイミングを調整する方法について誤解がありますか、それともスキップリストが本来あるべき検索をしていないだけですか? 念のため、スキップリストの実装全体を次に示しますが、検索関数は次のように呼び出されfindElement()ます。

どんなアドバイスでも大歓迎です、ありがとう。

次のようなスキップ リストを実装しています。

私がオンラインで見た説明では、スキップ リストの先頭と末尾に無限大/負の無限大キーがありますが、それらはすべて数字キーで使用されています。

<and演算子はキーに使用できると想定できる==ので、心配する必要はありませんstring < string

しかし、ヘッド/テール ポインターとして持つ最小/最大型の値を見つけるにはどうすればよいでしょうか? INT_MAXor INT_MINbut のようなものはありますか?

Java で基本的なredis サーバーを実装しようとしています。しかし、そのデータベースを実装するためにどのデータ構造を使用する必要があるかはわかりません。最初は、値を格納でき、コマンドを実装できるので、シンプルHashMapで十分だと思いました。しかし、深く掘り下げると、データベースのより複雑なデータ構造を必要とする、などのコマンドを見つけることができました。<Object, Object>GETSETGETBITSETBITZADD

タイプ ConcurrentSkipListMap の値列を持つ HashMap を使用する必要があると思います。私は正しいですか？助けてください。

また、Set コマンドの String 値をバイナリ値に変換して格納する必要がありますか?

n ノードのリンク リストがあります。k 番目のノードを削除し、その中に要素を表示したいと考えています。n の値が比較的小さく、問題の複雑さが問題にならない場合、これは簡単です。

問題は、リンクされたリストに n >=200000 のノードがあり、比較的大きな値 (k=150000 など) のノードを削除したい場合です。

この問題の通常の解決策は、リンクされたリスト全体をトラバースし、ノードを削除することです (解決策の複雑さは O(n) です)。ただし、これは単純で簡単な解決策であり、より多くの時間がかかります。この問題に対する他の解決策は、2 つのポインターを持つことですが、それでも最適な解決策ではありません。

最適で、最小限の時間で結果を提供するソリューションを探しています。

私の質問が明確であることを願っています。助けが要る..

スキップ リストのデータ構造を作成しようとしています。以下は、Node.js 用にこれまでに作成したコードのスナップショットです。

この場合にベクトルを使用すると、サイズを動的に変更できるため、はるかに優れていることを理解しています。配列を使用したい場合、どこに行けばいいのだろうと思っていました。

私は C++ を初めて使用するので、後で配列のサイズを割り当てることができるかどうか疑問に思っています。たとえば、サイズ 2 のポインター配列のみを持つ別のノードを追加したいとします。

スキップ リストに挿入するためのアルゴリズムはどのように見えますか?

通常、Google で検索するとこのようなものがポップアップ表示されますが、奇妙なことに、本やインターネットで役立つ情報を見つけることができないようです。

私が見つけることができる唯一のものは、スキップリストがどのように機能するかの説明です.

スキップリストにいくつかの要素を挿入しようとしています

ノードはキーでソートされます。ただし、前のキーよりも大きなキーを持つノードを挿入しようとすると、セグメンテーション違反が発生し、挿入関数で発生することがわかりました

の

なぜなら

無効です。なぜこれが起こっているのか理解できません。助けていただければ幸いです