Эффективный способ сделать большой случайный байтовый массив - PullRequest
Новая
       6

Эффективный способ сделать большой случайный байтовый массив

28 голосов
/ 12 августа 2011

Мне нужно создать большой байтарри определенного размера, но размер не известен до запуска. Байты должны быть довольно случайными. Размер байтового массива может составлять всего несколько КБ, но может достигать нескольких МБ. Я не хочу перебирать побайтово. Это слишком медленно - мне нужна производительность, похожая на 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
>>>

Ответы [ 4 ]

39 голосов
/ 12 августа 2011

Модуль os обеспечивает urandom, даже в Windows: 

bytearray(os.urandom(1000000))

Это, кажется, работает так быстро, как вам нужно, на самом деле, я получаю лучшее время, чем ваша няня (хотя наши машины могутсильно отличается): 

timeit.timeit(lambda:bytearray(os.urandom(1000000)), number=10)
0.0554857286941
7 голосов
/ 12 августа 2011

Что плохого в том, чтобы просто включить NumPy?В любом случае, это создает случайное N-разрядное целое число: 

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

Так что, если вам нужно узнать, установлено или нет значение j-го бита, вы можете сделать bits & (2**j)==(2**j)

РЕДАКТИРОВАТЬ: Он попросил байтовый массив, а не битовый массив.Нед лучше ответит: your_byte_array= bytearray((random.getrandbits(8) for i in xrange(N))

4 голосов
/ 04 мая 2017

Есть несколько возможностей, некоторые быстрее, чем os.urandom. Также подумайте, должны ли данные генерироваться детерминистически из случайного начального числа. Это неоценимо для модульных тестов, где сбои должны быть воспроизводимыми.

короткие и содержательные:

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

Я использовал выше для модульных тестов, и это было достаточно быстро, но можно ли сделать это быстрее?

с помощью itertools:

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

itertools и структура, генерирующая 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 раз память, потребляемую конечным байтовым массивом, временными объектами, поскольку он ставит в очередь все подстроки перед их объединением, а объекты 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

Производительность

  • .84 МБ / с : оригинальное решение с randint:
  • 4,8 МБ / с : bytearray(getrandbits(8) for _ in xrange(n)): (решение другого автора)
  • 6,4 МБ / с : bytearray(map(getrandbits,(8,)*n))
  • 7,2 МБ / с : itertools и getrandbits
  • 10 МБ / с : os.urandom
  • 23 МБ / с : itertools и struct
  • 35 МБ / с : оптимизированная функция (удерживается для len = 100 МБ ... 1 КБ)

Примечание: все тесты использовали размер строки 10 КБ. Результаты были согласованы до тех пор, пока промежуточные результаты не заполнили память.

Примечание: 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 МБ / с . (без аппаратного ускорения AES, одноядерный) Это всего лишь ~ 5x скорость кода выше чистого Python.

Добавление

Есть чистая крипто библиотека Python, ожидающая написания. Объединение вышеуказанных методов с hashlib и методами потокового шифрования выглядит многообещающе. Вот тизер, быстрый xor ( 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)))
3 голосов
/ 12 августа 2011 
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)]

...