在Python中无模块和时钟生成（伪）随机数

Question

我正在参加一个比赛，用Python创建一个机器人来玩游戏。问题是，我的环境里没有安装任何C语言支持，所以我无法使用random、numpy和scipy这些模块。

我大约有400MB的内存可用，我想找个方法在游戏中生成0到1之间均匀的随机数，用于模拟。

我之前用过时钟时间来生成一个随机数，但问题是我需要生成很多数字，而时钟变化不大，这样就会导致生成的数字总是一样。实际上，我最多只能在1秒内生成大约10万个数字。

我考虑过加载一些数据，但这样的话，机器人就总是使用相同的数字。不过，我需要使用的数字的情况又稍微有些不同。

我使用的是Python 2.7，希望大家能给点建议。

Answer 1

数学是你最好的答案：http://en.m.wikipedia.org/wiki/Linear_congruential_generator

X(n+1) = (aX(n)+c) mod m

x2 = (a*x1+c)%m

Answer 2

如果这个脚本在Linux上运行，可以试试用 /dev/urandom：

with open('/dev/urandom', 'rb') as f:
    random_int = reduce(lambda acc, x: (acc << 8) | x, map(ord, f.read(4)), 0)

• f.read(4) 这个命令会读取4个字节的数据
• map(ord, f.read(4)) - 这个命令会把读取到的字节转换成数字
• reduce(lambda ..., map(...), 0) - 这个命令会把数字列表合并成一个整数

Answer 3

顺便提一下，random模块里有一个叫做Wichman-Hill生成器的类，它是用纯Python写的（不需要C语言）：

>>> import random
>>> rng = random.WichmannHill(8675309)
>>> rng.random()
0.06246664612856567
>>> rng.random()
0.3049888099198217

下面是整理过的源代码：

class WichmannHill(Random):

    def seed(self, a=None):
        a, x = divmod(a, 30268)
        a, y = divmod(a, 30306)
        a, z = divmod(a, 30322)
        self._seed = int(x)+1, int(y)+1, int(z)+1

    def random(self):
        """Get the next random number in the range [0.0, 1.0)."""
        x, y, z = self._seed
        x = (171 * x) % 30269
        y = (172 * y) % 30307
        z = (170 * z) % 30323
        self._seed = x, y, z
        return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0

Answer 4

你可以使用一种叫做 梅森旋转算法 的实现。我找到了一种 这个，它是根据维基百科上的伪代码制作的。

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Based on the pseudocode in https://en.wikipedia.org/wiki/Mersenne_Twister. Generates uniformly distributed 32-bit integers in the range [0, 232 − 1] with the MT19937 algorithm

Yaşar Arabacı <yasar11732 et gmail nokta com>
"""
# Create a length 624 list to store the state of the generator
MT = [0 for i in xrange(624)]
index = 0

# To get last 32 bits
bitmask_1 = (2 ** 32) - 1

# To get 32. bit
bitmask_2 = 2 ** 31

# To get last 31 bits
bitmask_3 = (2 ** 31) - 1

def initialize_generator(seed):
    "Initialize the generator from a seed"
    global MT
    global bitmask_1
    MT[0] = seed
    for i in xrange(1,624):
        MT[i] = ((1812433253 * MT[i-1]) ^ ((MT[i-1] >> 30) + i)) & bitmask_1


def extract_number():
    """
    Extract a tempered pseudorandom number based on the index-th value,
    calling generate_numbers() every 624 numbers
    """
    global index
    global MT
    if index == 0:
        generate_numbers()
    y = MT[index]
    y ^= y >> 11
    y ^= (y << 7) & 2636928640
    y ^= (y << 15) & 4022730752
    y ^= y >> 18

    index = (index + 1) % 624
    return y

def generate_numbers():
    "Generate an array of 624 untempered numbers"
    global MT
    for i in xrange(624):
        y = (MT[i] & bitmask_2) + (MT[(i + 1 ) % 624] & bitmask_3)
        MT[i] = MT[(i + 397) % 624] ^ (y >> 1)
        if y % 2 != 0:
            MT[i] ^= 2567483615

if __name__ == "__main__":
    from datetime import datetime
    now = datetime.now()
    initialize_generator(now.microsecond)
    for i in xrange(100):
        "Print 100 random numbers as an example"
        print extract_number()