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

Question

我正在查看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应该提供一个随机变量，其概率分布是（大约）在区间[0, 6)上的离散均匀分布。您可以在此处了解更多信息。 http://puu.sh/XMwn

请注意，内部Random使用线性同余生成器，其中m = 2^48、a = 25214903917和c = 11。

---

randomLevel相反（大约）使用p = 0.5的几何分布。您可以在此处了解有关分发的更多信息。

http://puu.sh/XMwT

从本质上讲，randomLevel返回0概率为0.5、0.251、0.125等，直到0.5 ^7即 *0.0078125** -与~0.14 from大不相同。26Random.nextInt

---

现在这一点的重要性在于，跳过列表是一种固有的概率数据结构。通过利用多个稀疏级别的链表，它们可以实现O(log n)搜索的平均运行时性能——类似于平衡二叉搜索树，但不太复杂且占用空间更少。在这里使用均匀分布是不合适的，看看如何与较低级别相比，较高级别的人口密度较低（注意：下面，级别向下增长） - 这对于快速搜索是必要的。

Answer 2

就像链接说的那样......

“这给了我们 50% 的 random_level() 函数返回 0 的机会，25% 的返回 1 的机会，12.5% 的返回 2 的机会……”因此分布不均匀。但是， Random.nextInt() 是。选择 0 到 5 之间的任何数字的可能性相同。

我还没有查看完整的实现，但可能发生的是我们用来选择一个数字的 randomLevel()，比如 n。然后，需要添加到跳过列表的元素将具有指针 0、1、...、n。您可以将每个级别视为一个单独的列表。

为什么要使用这样的发行版？好吧，一个均匀的分布将需要太多的内存来获得它所带来的好处。通过使用几何分布减少机会，获得了“最佳”点。现在实现了快速获取值、内存占用更少的优势。