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

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，1以0.25，2与0.125，等等，直到6用0.5 ^ 7即* 0.0078125 ** -远比不同〜0.14从Random.nextInt。

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