java - 跳跃列表中的随机级别函数

Question

我正在查看 skip list implementation in 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);

谁能解释一下？谢谢。

Answer 1

Random.nextInt应提供一个随机变量，其概率分布(大约)为 discrete uniform distribution在 [0, 6) 区间内。 您可以了解更多相关信息 here . http://puu.sh/XMwn

请注意，内部 Random 使用 linear congruential generator其中 m = 2^48, a = 25214903917, and c = 11 .

---

randomLevel(大约)使用 geometric distribution其中 p = 0.5。您可以了解更多分布 here .

http://puu.sh/XMwT

本质上，randomLevel 返回 0 的概率为 0.5，1 的概率为 0.25 , 2 与 0.125 等直到 6 与 0.5^7 即 *0.0078125** -- 与 Random.nextInt 中的 ~0.14 有很大不同。

---

现在这个的重要性在于a skip list is an inherently probabilistic data structure .通过利用多级稀疏链表，它们可以实现 O(log n) 搜索的平均运行时性能——类似于平衡二叉搜索树，但不那么复杂并且使用更少的空间。 Using a uniform distribution here would not be appropriate ，了解如何与较低级别相比较高级别的人口密度较低(注意:下面，级别向下增长)——这是快速搜索所必需的。