22 декабря 2010

Генерация неслучайных чисел

Привет. Если вам приходилось использовать PRNG (Pseudorandom number generator), то вы наверняка пользовались уже готовой реализацией в языке программирования. Это хорошо, но не всегда стандартная функция генерации псевдослучайных чисел делает это так, как нам хочется.

К чему я это? Да к тому что иногда нужны не совсем случайные числа. Например нам нужно выбрасывать число из какой либо последовательности так, что бы эти числа не повторялись (если это конечно возможно) по два подряд. Зачем это нужно? Например когда нужно генерировать подземелье с не повторяющимися соседними комнатами. Объясняю. Когда у нас подряд идут две одинаковые комнаты, например две комнаты с колодцем, это выглядит не очень естественно.

Но меньше слов.

# -*- coding: utf-8 -*-
#!/usr/bin/env python

import random

class RandGenerator:
    def __init__(self):
        self._old = None

    def randint_nodubl(self, a, b):
        if a == b:
            return a
        rand = random.randint(a, b)
        while rand == self._old:
            rand = random.randint(a, b)
        self._old = rand
        return rand

def rand(func):
    dubl = 0
    old = None
    for i in range(100000):
        rand = func(0, 5)
        if rand == old:
            dubl += 1
        old = rand
    print(dubl)

if __name__ == '__main__':
    rand(random.randint)
    generator = RandGenerator()
    rand(generator.randint_nodubl)

Код я оставил без комментариев, потому что он очень простой. Наш PRNG элементарен и прям как прямая. Он генерирует число стандартным методом, и если число повторилось, генерируем еще раз. Для ускорения работы нашего генератора, мы можем генерировать последовательность заранее. В таком случае мы просто будем брать числа из cгенерированной последовательности, пока она не кончиться. Потом можно сгенерировать ее снова, или начать выбирать с начало. В этом случае нужно удостовериться, что если мы начнем снова брать числа сначала сгенерированной последовательности, то мы не нарушим правило генерации (в моем примере, не повторять число два раза подряд).

Генераторы псевдослучайных чисел может быть более сложный, например он сможет генерировать числа повторяющиеся не более трех раз в определенный период или наоборот стараться выкинуть давно не воспроизводимые числа. Важно помнить что генераторы псевдослучайных чисел могут генерировать числа с разным качеством псевдослучайности. Проще говоря, не забывайте оценивать на сколько случайны цифры вашего генератора, и помните что не всегда стоит делать их слишком случайными. Будьте проще.