如何矢量化numpy中分发硬币的模拟？

Question

我有以下问题，这是一个重新设计的作业问题，我希望将其放入即将发布的教程中。

核心思想是这样的。

我有 800,000 个硬币要分配到 900,000 个插槽中。暴力破解的 python 循环模拟看起来像这样：

import random
for coin in coins: #assume we have a list of coins
    slot = random.choice(slots) #assume we have a list of slots, which are sets.
    slot.add(coin)

现在，如果我们在少量插槽中处理少量硬币，那速度非常快。但是有成千上万的硬币和老虎机，这时候一些速度优化可能真的很不错。有没有办法使用 numpy 来做到这一点？

FWIW 我看过 How to create a list of random integer vector whose sum is x and Generate multiple random numbers to equal a value in python 中提出的解决方案，但其中 none 是矢量化的。

Answer 1

这个怎么样：

import numpy as np
coins = 800000
slots = 900000

coin_positions = np.random.randint(slots, size=coins)

coins_per_slot = np.histogram(coin_positions, bins=np.arange(slots + 1))[0]

如果插槽比硬币少得多，您可以使用 binomial distribution 计算每个插槽的随机硬币数：将 n 个硬币分配给 k个槽，生成x~B(n,1 /k)。那么第k个格子里有x个币，你继续分发n-[=17= k-1 个插槽中的 ]x 个硬币：

for i in range(k, 0, -1):
    x = np.random.binomial(n, 1./i)
    coins_per_slot[i-1] = x
    n -= x

如何矢量化numpy中分发硬币的模拟？

How to vectorize simulation of distributing coins in numpy?

python

numpy

vectorization