生成由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分發的隨機數

回答

相關問題