高效生成大随机字节数组的方法

Question

我需要创建一个特定大小的大字节数组，但这个大小在运行之前是未知的。数组里的字节需要比较随机。这个字节数组的大小可能只有几KB，也可能达到几MB。我不想一个字节一个字节地去处理，这样太慢了——我需要的性能要跟numpy.random差不多。不过，这个项目里我没有numpy模块。有没有什么是标准Python安装里自带的，可以做到这一点的？还是说我需要自己用C语言编译一个？

对于那些想要时间测试的人：

>>> timeit.timeit('[random.randint(0,128) for i in xrange(1,100000)]',setup='import random', number=100)
35.73110193696641
>>> timeit.timeit('numpy.random.random_integers(0,128,100000)',setup='import numpy', number=100)
0.5785652013481126
>>> 

Answer 1

单纯引入numpy有什么问题呢？无论如何，这段代码可以生成一个随机的N位整数：

import random
N = 100000
bits = random.getrandbits(N)

如果你想检查第j位的值是否被设置，可以用 bits & (2**j)==(2**j) 这个方法。

补充一下：他其实是想要字节数组，而不是位数组。Ned的回答更好：your_byte_array= bytearray((random.getrandbits(8) for i in xrange(N))

Answer 2

有几种方法可以生成随机数据，有些比 os.urandom 更快。你还需要考虑数据是否需要从一个随机种子中确定性地生成。这在单元测试中非常重要，因为测试失败时需要能够重现。

简单明了：

lambda n:bytearray(map(random.getrandbits,(8,)*n))

我用上面的代码做单元测试，速度还不错，但能不能更快呢？

使用 itertools：

lambda n:bytearray(itertools.imap(random.getrandbits,itertools.repeat(8,n))))

itertools 和 struct 每次生成 8 个字节

lambda n:(b''.join(map(struct.Struct("!Q").pack,itertools.imap(
    random.getrandbits,itertools.repeat(64,(n+7)//8)))))[:n]

任何基于 b''.join 的方法都会占用 3-7 倍于最终 bytearray 的内存，因为它会在合并之前先把所有子字符串排队，而 Python 对象有很多存储开销。

使用专门的函数生成大块数据可以提高性能，并避免占用过多内存。

import random,itertools,struct,operator
def randbytes(n,_struct8k=struct.Struct("!1000Q").pack_into):
    if n<8000:
        longs=(n+7)//8
        return struct.pack("!%iQ"%longs,*map(
            random.getrandbits,itertools.repeat(64,longs)))[:n]
    data=bytearray(n);
    for offset in xrange(0,n-7999,8000):
        _struct8k(data,offset,
            *map(random.getrandbits,itertools.repeat(64,1000)))
    offset+=8000
    data[offset:]=randbytes(n-offset)
    return data

性能

• 0.84 MB/s : 原始方案使用 randint：
• 4.8 MB/s : bytearray(getrandbits(8) for _ in xrange(n)) : （其他人提供的方案）
• 6.4 MB/s : bytearray(map(getrandbits,(8,)*n))
• 7.2 MB/s : itertools 和 getrandbits
• 10 MB/s : os.urandom
• 23 MB/s : itertools 和 struct
• 35 MB/s : 优化后的函数（适用于长度 = 100MB ... 1KB）

注意：所有测试使用 10KB 作为字符串大小。结果在中间结果填满内存之前是一致的。

注意：os.urandom 旨在提供安全的随机种子。应用程序会用自己的快速伪随机数生成器（PRNG）扩展这个种子。这里有一个例子，使用 AES 计数模式作为 PRNG：

import os
seed=os.urandom(32)

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
backend = default_backend()
cipher = Cipher(algorithms.AES(seed), modes.CTR(b'\0'*16), backend=backend)
encryptor = cipher.encryptor()

nulls=b'\0'*(10**5) #100k
from timeit import timeit
t=timeit(lambda:encryptor.update(nulls),number=10**5) #1GB, (100K*10k)
print("%.1f MB/s"%(1000/t))

这可以以 180 MB/s 的速度生成伪随机数据。（没有硬件 AES 加速，单核）这只是上面纯 Python 代码速度的 约 5 倍。

附录

还有一个纯 Python 的加密库等待编写。将上述技术与 hashlib 和流密码技术结合起来看起来很有前景。这是一个小预告，一个快速的字符串异或（42MB/s）。

def xor(a,b):
    s="!%iQ%iB"%divmod(len(a),8)
    return struct.pack(s,*itertools.imap(operator.xor,
        struct.unpack(s,a),
        struct.unpack(s,b)))

Answer 3

os模块提供了一个叫做urandom的功能，即使在Windows系统上也可以使用：

bytearray(os.urandom(1000000))

这个功能的速度似乎非常快，实际上，我的测试结果比你的numpy还要好（当然，我们的机器可能差别很大）：

timeit.timeit(lambda:bytearray(os.urandom(1000000)), number=10)
0.0554857286941