跳表中的随机水平函数

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_的随机变量。您可以了解有关此here的更多信息。http://puu.sh/XMwn

请注意，在内部，Random使用 where , , and 。

相反，randomLevel (大约)使用，其中p= 0.5。您可以了解有关发行版here的更多信息。

http://puu.sh/XMwT

本质上，randomLevel返回概率为0.5的0、概率为0.25的1、概率为0.125的2，依此类推，直到概率为0.5^7 (即*0.0078125** )的6 -- 与e221 Random.nextInt.中的 ~0.14 E120完全不同

这一点的重要性在于a skip list is an inherently data structure。通过利用链表的多个稀疏级别，它们可以实现O(log )搜索的平均运行时性能-类似于平衡的二进制搜索树，但复杂度较低的和使用较少的空间。Using a uniform distribution here would be appropriate，查看如何与较低的级别相比，较高级别的人口密度较低(注意：下面的级别向下增长) --这对于快速搜索是必要的。

​

​

Answer 2

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

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

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

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