Geekly Articles each Day

スキップリストについてもう一度...

...またはコンソールアプリケーション用にAlenkaを取得した方法


さまざまなテストタスクを実装することで、プロのレベルを迅速に高めることができるという意見がかなり広まっています。 私自身は、時々トリッキーなテストスレッドを掘り下げて、常に良い状態になるように解決するのが好きです。 どういうわけか、ある会社でインターンシップの競争的な課題を完了していましたが、タスクは面白くて面白かったようです。その短いテキストを次に示します。

あなたの同僚の初心者が彼の困難な仕事について話しに来たと想像してください-彼は整数のセットを昇順に並べるだけでなく、LthからRthまでの順序セットのすべての要素を与える必要があります！
これは基本的なタスクであり、C＃でソリューションを作成するのに10分かかると述べました。 まあ、または1時間。 または2。 またはチョコレート「Alyonka」

セットでは重複が許可され、要素の数は10 ^ 6以下であると想定されます。

ソリューションの評価にはいくつかのコメントがあります。

3人のプログラマーがコードを評価およびテストします。
  • Billは、10 KB以下のテストでソリューションを実行します。
  • Stephenのテストでは、リクエストの数は10 ^ 5以下であり、追加のリクエストの数は100以下です。
  • マークのテストでは、クエリの数は10 ^ 5以下です。
解決策は非常に興味深い可能性があるため、説明する必要があると考えました。

解決策


抽象リポジトリを用意しましょう。

追加（e）-アイテムをストアに追加し、範囲（l、r）-lからr要素へのスライスを示します。

簡単なストレージオプションは次のとおりです。
動的配列に基づいてアプローチの複雑さを推定します。

C範囲（l、r）-スライスを取ることはO（r-l）と推定できます。

C追加（e）-最悪の場合の挿入はO（n）に対して機能します。ここで、nは要素の数です。 n〜10 ^ 6の場合、挿入がボトルネックになります。 改善されたストレージオプションは、この記事の後半で提案されます。

ソースコードの例はここにあります 。

より適切なオプションは、たとえば次のとおりです。
Cormenを開いてRBツリーがどのように機能するかを思い出す準備がほぼ整いましたが、偶然にSkipListに関するWikipediaの記事に出会いました 。

スキップリスト


Skiplistは、複数のリンクリストに基づいて、検索ツリーのランダムな代替手段です。 1989年にWilliam Pughによって発明されました。 検索、挿入、および削除の操作は、対数的にランダムな時間で実行されます。

このデータ構造は広く知られていません（ちなみに、 Habréには非常に豊富に記述されています ）が、漸近的な推定値は良好です。 好奇心のために、私はそれを実現したかった、さらに適切なタスクがあった。

さらに、私が解決に使用したすべてのソースからの簡単な絞り込みを行います。

ソートされた、単純に接続されたリストがあるとします：

最悪の場合、検索はO（n）で実行されます。 どのように加速できますか？

私が仕事をしているときにレビューしたビデオ講義の1つで、ニューヨークの急行列車について素晴らしい例を挙げました。


アイデアは次のとおりです。レベル内のノードは均等に分散される必要がありますが、一定数のノードを含む一定数のレベルを追加できます。 上位レベルのそれぞれに、下位レベルの要素の半分がある場合の例を考えてみましょう。


完全なSkipListが例に示されており、実際にはすべてが似ていますが、少し間違っています:)

検索する


これが検索方法です。 72番目の要素を探しているとします。



挿入


挿入では、物事はもう少し複雑です。 要素を挿入するには、一番下のリストのどこに挿入するかを理解し、同時に特定の数の上位レベルにそれをプッシュする必要があります。 しかし、それぞれの特定の要素をプッシュするためにいくつのレベルが必要ですか？

この方法で解決することが提案されています。挿入するとき、新しい要素を最低レベルに追加し、ドロップするまでコインを投げ始め、その要素を次の上位レベルにプッシュします。
要素を挿入してみましょう-67。まず、以下のリストのどこに要素を挿入するかを見つけます。



彼はコインが連続して2回落ちることを提案した。 したがって、要素を2レベル上にプッシュする必要があります。



インデックスアクセス


インデックスでアクセスするには、次の操作を行うことをお勧めします。各遷移をその下にあるノードの数でマークします。



i番目の要素にアクセスした後（ところで、O（ln n）で取得します）、カットするのは難しくないようです。

Range（5、7）を見つける必要があるとします。 まず、インデックス5の要素を取得します。


そして今、範囲（5、7）：


実装について


SkipListノードが次のような場合、実装は自然なようです。
SkipListNode {
int Element;
SkipListNode[] Next;
int [] Width;
}
実際、これはWilliam PugによるCの実装で行われました 。

しかし、C＃では、その長さも配列に格納されますが、可能な限り最小のメモリ量で実行したかった（判明したように、タスクの条件では、すべてが厳密に評価されていませんでした）。 同時に、SkipListの実装と拡張RBツリーがほぼ同じ量のメモリを使用するようにしました。

メモリ消費量を削減するための答えは、java.util.concurrentパッケージのConcurrentSkipListMapを詳しく調べると、予想外に見つかりました。

二次元スキップリスト


1つのディメンション内のすべての要素の単純に接続されたリストがあるとします。 2番目の方法では、下位レベルへのリンクを持つ遷移の「エクスプレスライン」があります。
ListNode {
int Element;
ListNode Next;
}

Lane {
Lane Right;
Lane Down;
ListNode Node;
}

不誠実なコイン


メモリ消費を削減するには、「不正な」コインを使用します。要素を次のレベルにプッシュする可能性を減らします。 William Pughは、いくつかのプッシュ確率値のスライスをレビューしました。 ½との値を検討する場合、実際には、メモリ消費量を削減してほぼ同じ検索時間が得られました。

乱数生成について少し


ConcurrentSkipListMapの基本を詳しく調べると、次のように乱数が生成されていることに気付きました。
int randomLevel() {
int x = randomSeed;
x ^= x << 13;
x ^= x >>> 17;
randomSeed = x ^= x << 5;
if ((x & 0x80000001) != 0)
return 0;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;
return level;
}
この記事では、 XOR を使用して擬似乱数を生成する方法について詳しく読んでください 。 速度の特定の向上に気付かなかったため、使用しませんでした。

結果のストレージのソースコードは、 ここで表示できます 。

一緒にgooglecode.com （プロジェクトページネーション ）からピックアップできます。

テスト


3種類のストレージが使用されました。
  1. ArrayBased（動的配列）
  2. SkipListBased（パラメーター¼のスキップリスト）
  3. RBTreeBased（赤黒木：同様のタスクを実行した友人の実装）。
10 ^ 6要素を挿入するための3種類のテストが実施されました。
  1. 昇順アイテム
  2. 降順アイテム
  3. ランダムアイテム
テストは、i5、8GB RAM、SSD、Windows 7 x64を搭載したマシンで実施されました。
結果：
配列RBTreeスキップリスト
ランダム127033ミリ秒1020ミリ秒1737ミリ秒
注文済み108ミリ秒457ミリ秒536ミリ秒
降順256337ミリ秒358ミリ秒407ミリ秒
かなり期待される結果。 要素が最後を除いてどこかに挿入されたときに配列に挿入すると、動作が最も遅くなることがわかります。 同時に、SkipListはRBTreeよりも低速です。

測定も行われました：各ストレージに10 ^ 6個の要素が挿入された状態でメモリにどれくらいかかるか。 スタジオプロファイラーが使用されました。簡単にするために、次のコードが起動されました。
var storage = ...
for ( var i = 0; i < 1000000; ++i)
storage.Add(i);
結果：
配列RBTreeスキップリスト
割り当てられた合計バイト8,389,066バイト24,000,060バイト23,985,598バイト
それでも非常に期待される結果：動的配列のストレージはメモリの使用量が最も少なく、SkipListとRBTreeはほぼ同じ量を使用しました。

アリヨンカとのハッピーエンド


問題の状況に応じて、同僚、泣き言を言う人が、私のためにバーを開いた。 私の決定は最高得点とされました。 誰かがこの記事が役立つことを願っています。 ご質問があれば、喜んでお答えします。

PS：SKB Konturでインターンシップに参加しました。 これは同じ質問に答えることではありません=）

Source: https://habr.com/ru/post/J139870/

More articles:


All Articles