生成由Zipf分发的随机数

Zipf probability distribution经常用于模拟P2P系统中项目的文件大小分布或项目访问分布。例如"Web Caching and Zip like Distribution Evidence and Implications"，但Boost或GSL (Gnu Scientific Library)均未提供使用此分布生成随机数的实现。我还没有找到使用通用搜索引擎的（可信）实现。生成由Zipf分发的随机数

如何通过使用U（0,1）随机生成器例如根据Zipf分布来分布的随机数Mersenne twister？

来源

2009-09-02 dmeister

最近的一篇论文（Maurizio Naldi，2015）提出了一个具有交换时间和准确性的参数的近似算法。对于alpha的合理范围（0 <= alpha <= 2），错误不会超过0.1％。有关VGAM，请参阅https://arxiv.org/pdf/1511.01480.pdf – 2017-07-12 13:02:54

zipfR是一个免费的开源库，用R实现。VGAM是另一个R包，它也实现Zipf。

还值得注意的是，Gnu Scientific Library有Pareto distribution的implementation这实际上是离散Zipf分布的连续模拟。

另外，Zeta distribution相当于Zipf for infinite N。 GSL的implementation的Riemann zeta function，所以你可以使用它来自己构建分布。

来源

2009-09-02 11:05:45

+1。它的'dzipf'函数将为您提供每个等级的概率列表，您可以使用它来生成项目访问。 – 2013-04-19 09:52:51

numpy.random.zipf使用python生成Zipf示例。

来源

2009-09-02 11:15:47

不幸的是，它使用黎曼的zeta函数，所以它只需要指数高于1，而许多P2P种群最好以低于1的指数来建模。 – 2013-04-19 09:57:08

下面是n项目与参数alpha >= 0一个Python齐普夫样分布发生器：

import random 
import bisect 
import math 

class ZipfGenerator: 

    def __init__(self, n, alpha): 
     # Calculate Zeta values from 1 to n: 
     tmp = [1./(math.pow(float(i), alpha)) for i in range(1, n+1)] 
     zeta = reduce(lambda sums, x: sums + [sums[-1] + x], tmp, [0]) 

     # Store the translation map: 
     self.distMap = [x/zeta[-1] for x in zeta] 

    def next(self): 
     # Take a uniform 0-1 pseudo-random value: 
     u = random.random() 

     # Translate the Zipf variable: 
     return bisect.bisect(self.distMap, u) - 1

来源

2012-01-09 12:48:16 stanga

优秀的答案。对于Python 3.x，添加“from functools import *” – 2012-03-20 01:11:08

或者，也许''从functools import reduce'' – 2015-03-28 12:34:01

正是我需要的，非常感谢！ – hayesti 2015-06-23 23:01:51

我们在讨论中this thread @stanga的答案。他的算法有一些很好的优化建议。

来源

2015-06-24 20:20:25 hayesti

目前，这几乎没有答案。你应该在这里包括你的解决方案，不要只是指它。 – 2015-06-24 20:22:39

最近针对Apache Commons Math库的下一个版本（> = 3.6）开发了一种生成Zipf分布随机变量的非常有效的算法（请参阅代码here）。它利用拒收反演采样，并且对小于1的指数也有效。它不需要预先计算CDF并将其保存在内存中。此外，生成一个样本的成本是不变的，并且不会随着项目的数量而增加。

来源

2015-10-18 16:38:26 otmar

生成由Zipf分发的随机数

回答

相关问题