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

40
我需要创建一个特定大小的大字节数组,但在运行时未知大小。这些字节需要相当随机。字节数组大小可能只有几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
>>> 

6
打开/dev/urandom - Santa
2
Python提供了一个便携式接口到/dev/urandom:请参见我的(第二个)答案。 - Ned Batchelder
4个回答

59

即使在Windows系统上,os模块也提供了urandom函数:

bytearray(os.urandom(1000000))

这段代码似乎可以达到你所需要的速度,事实上,我在我的机器上比你的 numpy 库获得了更好的时间性能(尽管我们的机器可能存在巨大差异):

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

只想补充一点,随机模块可以比在Linux上的os.urandom更快地生成伪随机数据。

In [102]: timeit.timeit(lambda: bytearray(os.urandom(2**16)), number=100) Out[102]: 0.03401689900783822

In [103]: timeit.timeit(lambda: (random.getrandbits(8 * 2**16)).to_bytes(2**16, sys.byteorder), number=100) Out[103]: 0.01772290701046586
- manabear
os.random() 可能会在 Linux 上阻塞。请参见 PEP 524 - Anton Leontiev

12

有几种可能性,比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的任何操作都会使用大量临时对象,因为它会将所有子字符串排队并连接在一起,而Python对象具有大量的存储开销,所以最终的bytearray占用的内存将是其消耗内存的3-7倍。

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

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

性能

  • .84 MB/s:使用randint的原始解决方案:
  • 4.8 MB/sbytearray(getrandbits(8) for _ in xrange(n)):(其他用户提供的解决方案)
  • 6.4MB/sbytearray(map(getrandbits,(8,)*n))
  • 7.2 MB/sitertoolsgetrandbits
  • 10 MB/sos.urandom
  • 23 MB/sitertoolsstruct
  • 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的速度产生伪随机数据。(无硬件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)))

7

仅仅包含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))


这很好。我是否错过了一些将长整型转换为字节数组或字节缓冲区的明显方法? - Paul
1
无法使用NumPy,因为我的环境受到限制,只能使用非常有限的外部包。 - Paul
@Paul - Ned已经提供了解决方案。抱歉我不太擅长阅读理解,将其误读为bitarray。如果你想要一行代码,你可以这样做:bytearray((random.getrandbits(8) for i in xrange(N)) - dr jimbob
KISS原则:不要导入你实际上不需要的包。 - cowbert

4
import random
def randbytes(n):
    for _ in xrange(n):
        yield random.getrandbits(8)

my_random_bytes = bytearray(randbytes(1000000))

在这里,itertools 可能会有所帮助,它总是会有用的...

我的时间表明,这比 [random.randint(0,128) for i in xrange(1,100000)] 快五倍左右。


看看我的时间。我正在寻找大约30-100倍的加速。 - Paul
1
在我所写的机器上,使用 random.getrandbits(8) 作为 random.randint(0, 256) 的替代品能够提高约6倍的速度。 - Karl Knechtel

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接