从非常大的发电机中选择随机样本

Question

我试图测试游戏的一些策略，这可以由10个非负整数定义，加起来为100.有109个选择9，或大约10 ^ 12这些，所以比较它们都不实用。我想随机抽取大约1,000,000个这样的样本。

我尝试过来自the answers to this question，and this one的方法，但所有这些方法似乎都太慢了。最快的方法似乎在我的机器上需要大约180个小时。

这就是我试图制作发电机的方法（改编自之前的SE答案）。出于某种原因，更改prob似乎不会影响将其转换为列表的运行时间。

def tuples_sum_sample(nbval,total, prob, order=True) :
    """ 
        Generate all the tuples L of nbval positive or nul integer 
        such that sum(L)=total.
        The tuples may be ordered (decreasing order) or not
    """
    if nbval == 0 and total == 0 : yield tuple() ; raise StopIteration
    if nbval == 1 : yield (total,) ; raise StopIteration
    if total==0 : yield (0,)*nbval ; raise StopIteration
    for start in range(total,0,-1) :
        for qu in tuples_sum(nbval-1,total-start) :
            if qu[0]<=start :
                sol=(start,)+qu
                if order :
                    if random.random() <prob:
                        yield sol
                else :
                    l=set()
                    for p in permutations(sol,len(sol)) :
                        if p not in l :
                            l.add(p)
                            if random.random()<prob:
                                yield p

拒绝抽样似乎需要大约300万年，所以这也是如此。

randsample = []
while len(randsample)<1000000:
    x = (random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100),random.randint(0,100))
    if sum(x) == 100:
        randsample.append(x)
randsample

谁能想到另一种方法呢？

谢谢

Answer 1

一些具有框架挑战性的问题：

• 您是否有必要生成整个人口，然后对该人口进行抽样？
• 为什么你需要检查你的数字是否总和为100？

您可以生成一组总和为数值的数字。看看这里的第一个答案：

Random numbers that add to 100: Matlab

然后生成您想要的这些集合的数量（在这种情况下为1,000,000）。

import numpy as np

def set_sum(number=10, total=100):
    initial = np.random.random(number-1) * total

    sort_list = np.append(initial, [0, total]).astype(int)
    sort_list.sort()

    set_ = np.diff(sort_list)

    return set_

if __name__ == '__main__':
    import timeit

    a = set_sum()

    n = 1000000
    sample = [set_sum() for i in range(n)]

Answer 2

Numpy救援！

具体来说，你需要一个multinomial发行版：

import numpy as np
desired_sum = 100
n = 10
np.random.multinomial(desired_sum, np.ones(n)/n, size=1000000)

它在几秒钟内输出一个包含一百万行10个随机整数的矩阵。每行总计达100。

这是一个较小的例子：

np.random.multinomial(desired_sum, np.ones(n)/n, size=10)

哪个输出：

array([[ 8,  7, 12, 11, 11,  9,  9, 10, 11, 12],
       [ 7, 11,  8,  9,  9, 10, 11, 14, 11, 10],
       [ 6, 10, 11, 13,  8, 10, 14, 12,  9,  7],
       [ 6, 11,  6,  7,  8, 10,  8, 18, 13, 13],
       [ 7,  7, 13, 11,  9, 12, 13,  8,  8, 12],
       [10, 11, 13,  9,  6, 11,  7,  5, 14, 14],
       [12,  5,  9,  9, 10,  8,  8, 16,  9, 14],
       [14,  8, 14,  9, 11,  6, 10,  9, 11,  8],
       [12, 10, 12,  9, 12, 10,  7, 10,  8, 10],
       [10,  7, 10, 19,  8,  5, 11,  8,  8, 14]])

总和似乎是正确的：

sum(np.random.multinomial(desired_sum, np.ones(n)/n, size=10).T)
# array([100, 100, 100, 100, 100, 100, 100, 100, 100, 100])

Python only

您还可以从10个零的列表开始，迭代100次并每次递增一个随机单元格：

import random
desired_sum = 100
n = 10
row = [0] * n
for _ in range(desired_sum):
    row[random.randrange(n)] += 1

row
# [16, 7, 9, 7, 10, 11, 4, 19, 4, 13]
sum(row)
# 100