Выбор случайной выборки от очень большого генератора

Question

Я пытаюсь протестировать некоторые стратегии для игры, которые можно определить с помощью 10 неотрицательных целых чисел, которые в сумме дают 100. Из них 109 выбирают 9, или примерно 10 ^ 12 из них, поэтому сравнивать их все не так практично. Я хотел бы взять случайную выборку из примерно 1 000 000 из них.

Я пробовал методы из ответов на этот вопрос , и этого , но все они все еще кажутся слишком медленными, чтобы работать. Похоже, что самый быстрый способ на моей машине займет около 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

Похоже, что отбор проб для отбраковки займет около 3 миллионов лет, так что это тоже не так.

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

Numpy на помощь!

В частности, вам нужен полиномиальный дистрибутив:

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

Вы также можете начать со списка из 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

Answer 2

Пара сложных вопросов:

• Есть ли какая-то причина, по которой вы должны сформировать всю совокупность, а затем произвести выборку этой совокупности?
• Зачем вам нужно проверять, равны ли ваши цифры 100?

Вы можете сгенерировать набор чисел, суммирующих значение. Проверьте первый ответ здесь:

Случайные числа, которые добавляют к 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)]