Обычный подход к устранению предвзятости состоит в том, чтобы отбрасывать числа, выходящие за пределы желаемого диапазона. Как уже отмечалось, это расточительно. Можно свести к минимуму потери, начав с большего количества битов и одновременно сгенерировав несколько случайных чисел; вы можете добиться лучшего соответствия между диапазоном входов и выходов.
Например, возьмите бросок игральной кости. Выход имеет 6 возможностей. Наивный подход потребует 3 случайных бита для каждого произведенного случайного числа. В первом примере демонстрируется проблема с ячейками.
def pigeon_die(total_bit_count):
for i in xrange(total_bit_count // 3):
bits = random.getrandbits(3)
yield 1 + bits * 6 // 8
1 : 832855
2 : 417835
3 : 416012
4 : 833888
5 : 416189
6 : 416554
total 3333333
max/min 2.00448063998
Второй пример — обычно используемый расточительный подход. Вы можете видеть, что он генерирует меньше случайных чисел из того же количества случайных битов, но устраняется смещение.
def wasteful_die(total_bit_count):
for i in xrange(total_bit_count // 3):
bits = random.getrandbits(3)
if bits < 6:
yield 1 + bits
1 : 417043
2 : 415812
3 : 417835
4 : 416012
5 : 416645
6 : 417243
total 2500590
max/min 1.00486517946
Последний пример принимает 13 бит за раз и генерирует из них 5 случайных чисел. Это генерирует даже больше чисел, чем наивный подход!
def optimized_die(total_bit_count):
for i in xrange(total_bit_count // 13):
bits = random.getrandbits(13)
if bits < 6**5:
for j in range(5):
yield 1 + bits % 6
bits //= 6
1 : 608776
2 : 608849
3 : 608387
4 : 608119
5 : 607855
6 : 608559
total 3650545
max/min 1.00163525841
Выбор 13 бит был сделан путем логарифмирования по основанию 6 степени 2 и выбора того, который ближе всего к целому числу.
def waste_list(n):
for bit in range(1, 31):
potential = math.log(2**bit, n)
count = int(potential)
if count > 0:
waste = potential - count
yield waste, bit, count
for waste, bit, count in sorted(waste_list(6)):
print bit, count, waste
if bit == 3:
break
13 5 0.029086494049
26 10 0.0581729880981
8 3 0.0948224578763
21 8 0.123908951925
3 1 0.160558421704
Как видите, есть 4 варианта лучше, чем простые 3 бита.
person
Mark Ransom
schedule
28.12.2013
rand()предлагает что-то вроде этого:min + (int) (((double) rand() / (RAND_MAX + 1.0)) * (max - min + 1)). Идея состоит в том, чтобы масштабировать вывод изrand()в дробь в диапазоне[0, 1), затем умножить на ваш диапазон и добавить минимум, чтобы получить число в диапазоне[min, max). Вероятно, есть способы сделать это, не прибегая к более медленным операциям с плавающей запятой, но хотите ли вы их использовать, будет зависеть от ваших ожиданий производительности и от того, насколько сложным вы хотите получить... - person twalberg schedule 27.12.2013rand()возвращает фиксированное количество случайных битов, вы предлагаете использовать только некоторые из них, а остальные сохранить на потом? Это кажется гораздо более громоздким, чем необходимо, поскольку биты свободны. Если вы беспокоитесь об исчерпании потока битов (что на самом деле означает, что вы начали повторять случайную последовательность), вам следует рассмотреть лучший (настоящий?) случайный источник. - person Dwayne Towell schedule 27.12.2013