如何有效地生成一组具有预定义分布的唯一随机数?

我有一个具有一些概率分布的项目图:

Map itemsDistribution; 

给定一定的m我必须生成一Set从上述分布中采样的m元素。

截至目前,我正在使用天真的方式:

 while(mySet.size < m) mySet.add(getNextSample(itemsDistribution)); 

getNextSample(...)方法根据概率从分布中提取对象。 现在,随着m增加,性能严重受损。 对于m = 500itemsDistribution.size() = 1000元素,有太多的颠簸,并且函数在while循环中保留太长时间。 生成1000个这样的集合,并且您有一个可以爬行的应用程序。

是否有更有效的方法来生成具有“预定义”分布的唯一随机数集? 大多数收集改组技术等是均匀随机的。 解决这个问题的好方法是什么?

更新 :循环将调用getNextSample(...) “至少” 1 + 2 + 3 + ... + m = m(m+1)/2次。 这是在第一次运行中,我们肯定会得到该集合的样本。 第二次迭代,它可能被调用至少两次,依此类推。 如果getNextSample本质上是顺序的,即遍历整个累积分布以找到样本,则循环的运行时复杂度至少为: n*m(m+1)/2 ,’n’是数字分布中的元素。 如果m = cn; 0<c<=1 m = cn; 0<c<=1则循环至少为Sigma(n ^ 3)。 这也是下限!

如果我们通过二分搜索替换顺序搜索,则复杂性至少为Sigma(log n * n ^ 2)。 有效但可能不是很大。

此外,由于我将上述循环调用了k次,因此无法从分布中删除,以生成k这样的集合。 这些集合是项目随机“计划”的一部分。 因此,一组“项目”。

问题不太可能是你展示的循环:

设n是分布的大小,我是getNextSample的调用次数。 我们有I = sum_i(C_i),其中C_i是getNextSample的调用次数,而集合的大小为i。 为了找到E [C_i],观察到C_i是泊松过程的到达间时间,其中λ= 1-i / n,因此以λ 指数分布 。 因此,E [C_i] = 1 /λ=因此E [C_i] = 1 /(1-i / n)<= 1 /(1-m / n)。 因此,E [I]

也就是说,对一组大小m = n / 2进行采样平均需要小于2m = n次调用getNextSample。 如果这是“慢”和“爬行”,可能是因为getNextSample很慢。 这实际上并不令人惊讶,因为分配传递给方法的方式不合适(因为该方法必须迭代整个分布以找到随机元素)。

以下应该更快(如果m <0.8 n)

 class Distribution { private double[] cummulativeWeight; private T[] item; private double totalWeight; Distribution(Map probabilityMap) { int i = 0; cummulativeWeight = new double[probabilityMap.size()]; item = (T[]) new Object[probabilityMap.size()]; for (Map.Entry entry : probabilityMap.entrySet()) { item[i] = entry.getKey(); totalWeight += entry.getValue(); cummulativeWeight[i] = totalWeight; i++; } } T randomItem() { double weight = Math.random() * totalWeight; int index = Arrays.binarySearch(cummulativeWeight, weight); if (index < 0) { index = -index - 1; } return item[index]; } Set randomSubset(int size) { Set set = new HashSet<>(); while(set.size() < size) { set.add(randomItem()); } return set; } } public class Test { public static void main(String[] args) { int max = 1_000_000; HashMap probabilities = new HashMap<>(); for (int i = 0; i < max; i++) { probabilities.put(i, (double) i); } Distribution d = new Distribution<>(probabilities); Set set = d.randomSubset(max / 2); //System.out.println(set); } } 

预期的运行时间是O(m /(1-m / n)* log n)。 在我的计算机上,在大约3秒内计算出一组1_000_000的大小为500_000的子集。

正如我们所看到的,当m接近n时,预期的运行时接近无穷大。 如果这是一个问题(即m> 0.9 n),以下更复杂的方法应该更好:

 Set randomSubset(int size) { Set set = new HashSet<>(); while(set.size() < size) { T randomItem = randomItem(); remove(randomItem); // removes the item from the distribution set.add(randomItem); } return set; } 

为了有效地实现删除,需要不同的分布表示,例如二叉树,其中每个节点存储其根的子树的总权重。

但这是相当复杂的,所以如果已知m明显小于n,我就不会走那条路。

首先在两个维度中生成一些随机点。

在此处输入图像描述

然后应用您的发行版

在此处输入图像描述

现在找到分布中的所有条目并选择x坐标,并且您的随机数字具有所请求的分布,如下所示:

在此处输入图像描述

您应该实现自己的随机数生成器(使用MonteCarlo方法或任何良好的统一生成器,如梅森捻线机)并基于反演方法( 此处 )。

例如:指数定律:在[0,1]生成一个统一的随机数u然后你的指数定律的随机变量将是: ln(1-u)/(-lambda) lambda being the exponential law parameter and ln the natural logarithm

希望它会有所帮助;)。

我认为你有两个问题:

  1. 您的itemDistribution不知道您需要一个集合,因此当您构建的集合变大时,您将选择已在集合中的许多元素。 如果你从set all full和remove元素开始,那么对于非常小的集合,你将遇到同样的问题。

    您选择后,是否有理由不从itemDistribution删除该元素? 那么你不会两次选择相同的元素?

  2. itemDistribution的数据结构选择看起来很可疑。 您希望getNextSample操作快速。 从值到概率的映射不会强制您迭代每个getNextSample的映射的大部分。 我不擅长统计数据,但你itemDistribution用另一种方式表示itemDistribution ,比如概率图,或者所有较小概率的总和+概率与集合元素的概率?

您的性能取决于getNextSample函数的工作方式。 如果您在选择下一个项目时必须迭代所有概率,则可能会很慢。

从列表中选择几个唯一随机项的好方法是首先对列表进行随机播放,然后从列表中弹出项。 您可以使用给定的分布对列表进行一次洗牌。 从那时起,选择你的m项只是弹出列表。

这是概率shuffle的实现:

 List prob_shuffle(Map dist) { int n = dist.length; List a = dist.keys(); int psum = 0; int i, j; for (i in dist) psum += dist[i]; for (i = 0; i < n; i++) { int ip = rand(psum); // 0 <= ip < psum int jp = 0; for (j = i; j < n; j++) { jp += dist[a[j]]; if (ip < jp) break; } psum -= dist[a[j]]; Item tmp = a[i]; a[i] = a[j]; a[j] = tmp; } return a; } 

这不是Java,而是在C语言中实现后的伪文本,所以请一定要带上它。 想法是通过从未洗涤区域连续挑选物品来将物品附加到洗牌区域。

在这里,我使用了整数概率。 (可能性不必添加到特殊值,它只是“越大越好”。)您可以使用浮点数但由于不准确,您可能最终在选择项目时超出数组。 你应该使用项目n - 1然后。 如果你添加那个安全网,你甚至可以拥有总是最后被选中的概率为零的项目。

可能有一种方法可以加快拣选循环,但我真的不知道如何。 交换使任何预先计算变得无用。

在表格中累积您的概率

  Probability Item Actual Accumulated Item1 0.10 0.10 Item2 0.30 0.40 Item3 0.15 0.55 Item4 0.20 0.75 Item5 0.25 1.00 

创建一个介于0.0和1.0之间的随机数,并对第一个项目进行二进制搜索,其总和大于生成的数字。 将以期望的概率选择该项目。

Ebbe的方法称为拒绝抽样

我有时使用一种简单的方法,使用逆累积分布函数 ,这是一个将0和1之间的数字X映射到Y轴的函数。 然后,您只需生成0到1之间的均匀分布的随机数,并将该函数应用于它。 该function也称为“分位数function”。

例如,假设您要生成正态分布的随机数。 它的累积分布函数叫做Phi 。 相反的是probit 。 有很多方法可以生成正常的变量,这只是一个例子。

您可以以表格的forms轻松地为您喜欢的任何单变量分布构建近似累积分布函数。 然后你可以通过表查找和插值来反转它。

如果你不太关心随机性属性,那么我这样做:

  1. 为伪随机数创建缓冲区

    双buff [MAX]; // [edit1]双伪随机数

    • MAX的尺寸应该足够大……例如1024 * 128
    • type可以是any( float,int,DWORD ……)
  2. 用数字填充缓冲区

    你有多个数字范围x = < x0,x1 >和概率函数probability(x)由你的概率分布定义,所以这样做:

     for (i=0,x=x0;x<=x1;x+=stepx) for (j=0,n=probability(x)*MAX,q=0.1*stepx/n;j 

    stepx是你对项目的准确性(对于整数类型= 1),现在buff[]数组具有你需要的相同分布,但它不是伪随机的。 另外你应该添加检查j是否不是>= MAX以避免数组溢出,并且最后buff[]的实际大小为j (由于舍入可能小于MAX)

  3. shuffle buff[]

    做几个交换buff[i]buff[j]的循环,其中i是循环变量, j是伪随机<0-MAX)

  4. 写你的伪随机函数

    它只是从缓冲区返回数字。 在第一次调用时,在第二个buff[1]返回buff[0] ,依此类推...对于标准生成器当你点击buff[]结束时,再次重新buff[]并再次从buff [0]开始。 但是,由于您需要唯一的数字,因此无法达到缓冲区的末尾,因此将MAX设置为足以满足您的任务要求,否则无法保证唯一性。

[笔记]

MAX应足够大,以存储您想要的整个发行版。 如果它不够大,那么概率很低的物品可能会完全丢失。

[edit1] - 调整回答一点以匹配问题需求(由meriton感谢指出)

PS。 初始化的复杂度是O(N) ,而get数是O(1)