python - 高效随机抽样

Question

我的问题很简单: 我有一个包含 2000 万个 float 的数组。在该数组中，每个 float 都有被随机更改的概率 p。

最简单的方法是遍历数组，执行 if (rand(0,1) < p) then modify。

然而，即使是并行化，它也非常慢，我在想是否有更快的方法来随机获取一些索引进行修改。

我的第一个想法是选取 p * n 个随机数，其中 n 是数组中 float 的总数，但是，这并不完全代表概率分布，因为在第一种情况下没有任何东西可以保证只有 p*n float 将被修改。

想法？

PD:我正在使用 python 来实现，可能之前有人遇到过这个问题并在库中实现了一些东西，但我找不到它。

Answer 1

首先，如果 p 很高，即 >= 0.5，无论您做什么都不会节省太多时间，因为您仍然可能访问大部分元素。但是，如果 p 较低，您可以从 binomial distribution 中提取n=20M 和您确定要触摸多少元素的概率。

In [23]: np.random.binomial(20*10**6, 0.1)
Out[23]: 1999582

In [24]: np.random.binomial(20*10**6, 0.99999)
Out[24]: 19999801

In [25]: np.random.binomial(20*10**6, 0.5)
Out[25]: 10001202

In [26]: np.random.binomial(20*10**6, 0.0001)
Out[26]: 1986
[...]
In [30]: np.random.binomial(20*10**6, 0.0001)
Out[30]: 1989

In [31]: np.random.binomial(20*10**6, 0.0001)
Out[31]: 1988

这个数字是假设 n 次试验的成功次数，每次试验都有 p 的成功机会，这正是您的情况。