Как эффективно рассчитать сумму бросков кубиков?

Question

Следующий код:

import random
def roll(num_dice,num_faces):
    return sum([random.randint(1,num_faces) for x in range(num_dice)])

случайным образом генерирует сумму кубиков с num_dice num_faces, но это медленно (O(N)) для большого количества игральных костей.

Как эффективнее рассчитать это в python?

Answer 1

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

import numpy as np
def roll_np(num_dice,num_faces):
    return sum((np.array(range(num_faces))+1)*np.random.multinomial(num_dice,[1/float(num_faces)]*num_faces))

Время выполнения этой реализации не зависит от num_dice.Я проверил это:

from time import time
t=time();roll_np(10000,6);print(time()-t) 

34997

0.0005793571472167969

t=time();roll_np(10000,6);print(time()-t) 

34938

0.0005676746368408203

t=time();roll_np(10000000,6);print(time()-t) 

34996283

0.0006160736083984375

t=time();roll_np(10000000,6);print(time()-t) 

34996047

0.000567913055419921

Answer 2

Для вычисления в O(1) посмотрите на эту функцию:

https://docs.scipy.org/doc/numpy/reference/generated/numpy.random.multinomial.html

если рассчитать

np.random.multinomial(num_dices,[1/float(num_faces)]*num_faces)

время выполнения зависит только от num_faces, а не от num_dices