4

Java でのスキップ リストの実装を見ていますが、次のメソッドの目的が気になります。

public static int randomLevel() {
    int lvl = (int)(Math.log(1.-Math.random())/Math.log(1.-P));
    return Math.min(lvl, MAX_LEVEL);
}

そして、上記の方法との違いは何ですか

Random.nextInt(6);

誰もそれを説明できますか？ありがとう。

4

2 に答える 2

8

Random.nextInt確率分布が区間[0, 6)で (ほぼ)離散一様分布である確率変数を提供する必要があります。詳細については、こちらをご覧ください。 http://puu.sh/XMwn

は、 m = 2^48、a = 25214903917、およびc = 11である線形合同ジェネレーターを内部的にRandom使用することに注意してください。

randomLevel代わりに (ほぼ) p = 0.5の幾何分布を使用します。ディストリビューションの詳細については、こちらをご覧ください。

http://puu.sh/XMwT

基本的に、確率0.5、0.25、0.125などで 0.5^7 まで、つまり* 0.0078125** を返します - ~ randomLevel0.14 fromとは大きく異なります。0126Random.nextInt

ここで重要なことは、スキップ リストは本質的に確率的なデータ構造であるということです。リンクされたリストの複数のスパースレベルを利用することで、 O(log n)検索の平均実行時パフォーマンスを達成できます。これは、バランスの取れた二分探索ツリーに似ていますが、それほど複雑ではなく、使用するスペースも少なくなります。ここで一様な分布を使用するのは適切ではありません。高いレベルは低いレベルに比べて人口密度が低いためです (注: 以下では、レベルは下に向かって成長します)。これは高速検索に必要です。

于 2012-08-22T06:03:11.140 に答える
1

リンクが言うように...

「これにより、random_level() 関数が 0 を返す可能性が 50%、1 を返す可能性が 25%、2 を返す可能性が 12.5% というようになります...」 したがって、分布は均等ではありません。ただし、 Random.nextInt() はです。0 から 5 までの任意の数が選択される可能性は同じです。

完全な実装は見ていませんが、おそらく発生するのは、randomLevel() を使用して n などの数値を選択したことです。次に、skiplist に追加する必要がある要素には、ポインター 0、1、...、n があります。各レベルを個別のリストと考えることができます。

なぜこのようなディストリビューションを使用するのですか? 均等に分散すると、その利点を得るために大量のメモリが必要になります。幾何分布を使用して可能性を減らすことにより、「スイート」スポットが達成されます。これで、より小さなメモリ フットプリントで値をすばやく取得できるという利点が実現されました。

于 2012-08-22T06:02:18.293 に答える