Как эффективно рассчитать сумму бросков костей?
Следующий код:
import random
def roll(num_dice,num_faces):
return sum([random.randint(1,num_faces) for x in range(num_dice)])
генерирует случайным образом сумму костей с num_dicenum_faces-гранями, но работает медленно (O(N)) для большого количества костей.
Каков более эффективный способ вычислить это в python?
Если вы бросаете столько игральных костей, что линейное время представляет собой проблему, вероятно, пришло время использовать приближение.
Если вы выполняете повторяющиеся испытания, вы можете предварительно вычислить, чтобы каждое испытание было лучше, чем линейное время. Это помогает?
Ответы 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
Это также требует времени, линейного по количеству кубиков. Это быстрее, потому что Cython, но все же линейно по количеству кубиков.
На самом деле, похоже, я неправильно прочитал источник numpy.random.multinomial — реализация использует другой алгоритм, чем тот, за который я его принял. Время выполнения действительно пропорционально количеству граней, а не количеству игральных костей.
Вы можете вычислить его гораздо быстрее, если воспользуетесь полиномиальным распределением:
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
О каком большом вы говорите? Вы достигаете предела памяти? Если это так, то поможет использование выражения генератора или любой другой подход, который не материализует полный список. В противном случае попробуйте
numpy. Но я не думаю, что здесь можно избежать линейной временной сложности.