Как ускорить заполнение массива в Python?

Question

Я пытаюсь заполнить заранее выделенный байт-массив, используя следующий код:

# preallocate a block array
dt = numpy.dtype('u8')
in_memory_blocks = numpy.zeros(_AVAIL_IN_MEMORY_BLOCKS, dt)

...

# write all the blocks out, flushing only as desired
blocks_per_flush_xrange = xrange(0, blocks_per_flush)
for _ in xrange(0, num_flushes):
    for block_index in blocks_per_flush_xrange:
        in_memory_blocks[block_index] = random.randint(0, _BLOCK_MAX)

    print('flushing bytes stored in memory...')

    # commented out for SO; exists in actual code
    # removing this doesn't make an order-of-magnitude difference in time
    # m.update(in_memory_blocks[:blocks_per_flush])

    in_memory_blocks[:blocks_per_flush].tofile(f)

Некоторые точки:

• num_flushes низкий, около 4 - 10
• blocks_per_flush - это большое число, порядка миллионов
• in_memory_blocks может быть довольно большим буфером (я установил его на 1 МБ и на 100 МБ), новремя очень удобное ...
• _BLOCK_MAX - максимум для 8-байтового целого без знака
• m - это hashilib.md5()

Генерация 1 МБ с использованием приведенного выше кода занимает ~ 1 с;500 МБ занимает ~ 376 с.Для сравнения, моя простая программа на C, которая использует rand (), может создать файл размером 500 МБ за 8 секунд.

Как улучшить производительность в цикле выше?Я почти уверен, что игнорирую что-то очевидное, что вызывает огромную разницу во времени выполнения.

Answer 1

В связи с тем, что 0.._BLOCK_MAX охватывает все возможные значения для numpy.uint8 (я предполагаю, что numpy.dtype('u8') (т.е. numpy.uint64 является опечаткой), вы можете использовать:

import numpy as np

for _ in xrange(0, num_flushes):
    in_memory_blocks = np.frombuffer(np.random.bytes(blocks_per_flush),
                                     dtype=np.uint8)

    print('flushing bytes stored in memory...')
    # ...

Этот вариант ~ в 8 раз быстрее, чем @ hgomersall's * :

$ python -mtimeit -s'import numpy as np' '
>     np.uint8(np.random.randint(0,256,20000000))'
10 loops, best of 3: 316 msec per loop

$ python -mtimeit -s'import numpy as np' '
>     np.frombuffer(np.random.bytes(20000000), dtype=np.uint8)'
10 loops, best of 3: 38.6 msec per loop

Если numpy.dtype('u8') не является опечаткой и вам действительно требуется numpy.uint64, тогда:

a = np.int64(np.random.random_integers(0, _BLOCK_MAX, blocks_per_flush))
in_memory_blocks = a.view(np.uint64) # unsigned

Примечание: np.int64() не делает копию, если dtype массива уже np.int64. .view(numpy.uint64) принудительно интерпретирует его как неподписанный (также копия не выполняется).

Answer 2

Поскольку вы размещаете смежные блоки, вы должны быть в состоянии сделать следующее (полностью избавиться от внутреннего цикла):

for _ in xrange(0, num_flushes):
    in_memory_blocks[:blocks_per_flush] = numpy.random.randint(
            0, _BLOCK_MAX+1, blocks_per_flush)

    print('flushing bytes stored in memory...')

    # commented out for SO; exists in actual code
    # removing this doesn't make an order-of-magnitude difference in time
    # m.update(in_memory_blocks[:blocks_per_flush])

    in_memory_blocks[:blocks_per_flush].tofile(f)

При этом используется функция numpy.random.randint, которая выделяет целый блок памяти и заполняет его случайными целыми числами (см. Комментарий Дж. Ф. Себастьяна ниже о numpy.random.randint против random.randint). Насколько я могу видеть, нет никакого способа заполнить предварительно выделенный массив, используя множество случайных подпрограмм. Другая проблема заключается в том, что randint numpy возвращает массивы int64. Если вам нужны целые числа другого размера, то вы можете использовать методы набора номера, например numpy.uint8. Если вы хотите, чтобы randints охватывали весь диапазон типа, тогда @ J. Метод Ф. Себастьяна , представленный ниже с использованием numpy.random.bytes, будет наилучшим (почти в любом случае!).

Однако простые тесты показывают разумное время (того же порядка, что и код C). Следующий код проверяет время для выделения массивов uint8 из 20 000 000 случайных целых чисел с использованием метода numpy:

from timeit import Timer
t = Timer(stmt='a=numpy.uint8(numpy.random.randint(0, 100, 20000000))',
        setup='import numpy')
test_runs = 50
time = t.timeit(test_runs)/test_runs
print time

На моем 4-летнем ноутбуке Core2 он занимает около 0,7 секунды на каждое выделение (он работает 50 раз, так что весь тест займет больше времени) Это 0,7 с на 20 000 000 случайных целых чисел uint8, так что я бы ожидал что-то около 20 с для всех 500 МБ.

Больше памяти означало бы, что вы могли бы выделять большие порции сразу, но вы по-прежнему эффективно тратите время, выделяя и записывая 64 бита для каждого целого, когда вам нужно только 8 (я не определял этот эффект количественно). Если он все еще недостаточно быстр, вы можете вызвать реализацию C, используя интерфейс numpy ctypes. Это действительно довольно легко использовать, и вы не получите практически никакого замедления по сравнению с чистым C.

Общее сообщение о том, что при использовании numpy всегда старайтесь использовать numpy-подпрограммы там, где они существуют, помня, что возврат к C с помощью ctypes не слишком болезнен. В целом, эта методология позволяет действительно довольно эффективно использовать python с очень небольшим замедлением для числовой обработки.

Редактировать: Что-то еще, что только что пришло мне в голову: как это реализовано выше, я думаю, вы бы сделали дополнительную ненужную копию. Если in_memory_blocks имеет длину blocks_per_flush, то лучше назначить ему возврат из numpy.random.randint, чем выделять его для определенного подмассива (который в общем случае должен быть копия). Итак:

in_memory_blocks = numpy.random.randint(0, _BLOCK_MAX+1, blocks_per_flush)

вместо:

in_memory_blocks[:blocks_per_flush] = numpy.random.randint(
        0, _BLOCK_MAX+1, blocks_per_flush)

Однако, если рассчитать это по времени, первый случай не приведет к значительному увеличению скорости (всего около 2%), поэтому, вероятно, не стоит беспокоиться о слишком большом количестве. Я предполагаю, что подавляющее количество времени тратится на генерацию случайных чисел (что я и ожидал).

Answer 3

Если вы просто пытаетесь заполнить файл байтами block_size за раз, это может быть быстрее, чем предыдущие ответы.Основываясь на генераторах и полностью обходя создание массива:

import numpy as np

def random_block_generator(block_size):
    while True:
        yield np.random.bytes(block_size)

rbg = random_block_generator(BLOCK_SIZE)

Тогда вы используете:

f = open('testfile.bin','wb')

for _ in xrange(blocks_to_write):
    f.write( rbg.next())

f.close()

Numpy использует детерминированную генерацию случайных чисел (следующее число в последовательности всегда одинаково,это только начинается в случайном месте, когда это инициализирует).Если вам нужны истинные случайные данные (степень криптографии), тогда вы можете использовать import Crypto.Random as cr и yield cr.get_random_bytes(block_size) вместо np.

Кроме того, если ваш BLOCK_SIZE является определенной константой, вы можете использовать выражение генератора, подобное этому (используя библиотеку Crypto на этот раз):

import Crypto.Random as cr
from itertools import repeat

BLOCK_SIZE = 1000

rbg = (cr.get_random_bytes(BLOCK_SIZE) for _ in repeat(0))

f = open('testfile.bin','wb')

for _ in xrange(blocks_to_write):
    f.write( rbg.next())

f.close()

Это включает реализацию rbg=... и выполнение.Этот метод генератора, даже с немного более медленным Crypto.Random, будет максимально использовать данные дискового ввода-вывода задолго до того, как он максимизирует вычисления (хотя я уверен, что другие ответы тоже).

ОБНОВЛЕНИЕ:

Некоторые данные о времени на Athlon X2 245 -

• Крипто: генерировать 500 МБ, не записывать - 10,8 с (46 МБ / с)
• Крипто: генерировать500 МБ и запись - 11,2 с (44,5 МБ / с)
• Numpy: генерировать 500 МБ, не записывать - 1,4 с (360 МБ / с)
• Numpy: генерировать 500 МБ изапись - 7,1 с (70 МБ / с)

Таким образом, цифровая версия примерно в 8 раз быстрее (достаточно быстро, чтобы максимально использовать мой старый диск).Я протестировал оба из них, используя форму выражения генератора, а не форму функции генератора.

Answer 4

Я не очень хорош в оптимизации, но я не вижу, как ваш код может работать быстрее. Вы используете чисто итераторы и структуру доступа O (1).

Проблема, я думаю, в том, что вы выбираете язык. Помните, что вы работаете на виртуальной машине, и переводчик в этом. Ваша программа на С всегда будет работать на порядок быстрее.