Эффективный массив Python с 100 миллионами нулей?

Question

Каков эффективный способ инициализации и доступа к элементам большого массива в Python?

Я хочу создать в Python массив со 100 миллионами записей, 4-байтовые целые числа без знака, инициализированные нулем. Я хочу быстрый доступ к массиву, желательно с непрерывной памятью.

Странно, но NumPy массивы работают очень медленно. Есть ли альтернативы, которые я могу попробовать?

Существует модуль array.array , но я не вижу способа эффективно выделить блок из 100 миллионов записей.

Ответы на комментарии:

• Я не могу использовать разреженный массив. Этот алгоритм будет слишком медленным, потому что массив очень быстро становится плотным.
• Я знаю, что Python интерпретируется, но наверняка есть способ выполнять быстрые операции с массивами?
• Я провел некоторое профилирование и получаю около 160К обращений к массиву (поиск или обновление элемента по индексу) в секунду с помощью NumPy. Это кажется очень медленным.

Answer 1

Я провел некоторое профилирование, и результаты совершенно нелогичны. Для простых операций доступа к массиву numpy и array.array в 10 раз медленнее, чем собственные массивы Python .

Обратите внимание, что для доступа к массиву я выполняю операции вида:

a[i] += 1

Профили:

• [0] * 20000000

  • Доступ: 2,3 М / с
  • Инициализация: 0,8 с

• numpy.zeros (shape = (20000000,), dtype = numpy.int32)

  • Доступ: 160 К / с
  • Инициализация: 0,2 с

• array.array ('L', [0] * 20000000)

  • Доступ: 175K / сек
  • Инициализация: 2,0 с

• array.array ('L', (0 для i в диапазоне (20000000)))

  • Доступ: 175K / сек, предположительно, на основе профиля для другого массива. Массив
  • Инициализация: 6,7 с

Answer 2

Просто напоминание о том, как работают целые числа Python: если вы выделяете список, говоря

a = [0] * K

, вам нужна память для списка (sizeof(PyListObject) + K * sizeof(PyObject*)) и память для одного целочисленного объекта 0,Пока числа в списке остаются ниже магического числа V, которое Python использует для кэширования, у вас все в порядке, потому что они являются общими, то есть любое имя, которое указывает на число n < V, указывает на точно такой же объект.Вы можете найти это значение с помощью следующего фрагмента:

>>> i = 0
>>> j = 0
>>> while i is j:
...    i += 1
...    j += 1
>>> i # on my system!
257 

Это означает, что, как только число превысит это число, вам понадобится память sizeof(PyListObject) + K * sizeof(PyObject*) + d * sizeof(PyIntObject), где d < K - это числоцелые числа выше V (== 256).В 64-битной системе sizeof(PyIntObject) == 24 и sizeof(PyObject*) == 8, то есть наихудшее потребление памяти составляет 3 200 000 000 байтов.

При numpy.ndarray или array.array потребление памяти остается постоянным после инициализации, но вы платите за объекты-оболочки, которые создаются прозрачно, как сказал Томас Воутерс.Вероятно, вам следует подумать о преобразовании кода обновления (который получает доступ и увеличивает позиции в массиве) в код на языке C, используя Cython или scipy.weave.

Answer 3

Попробуйте это:

x = [0] * 100000000

На моем компьютере выполняется всего несколько секунд, и доступ к нему близок к мгновенному.

Answer 4

Если вы не можете векторизовать свои вычисления, Python / Numpy будет медленным. Numpy работает быстро, потому что векторизованные вычисления происходят на более низком уровне, чем Python. Все основные функции написаны на C или Fortran. Следовательно, sum(a) - это не цикл Python с большим количеством обращений, это один вызов C низкого уровня.

Демонстрационная страница Numpy's Performance Python содержит хороший пример с различными опциями. Вы можете легко получить 100-кратное увеличение, используя скомпилированный язык более низкого уровня, Cython или используя векторизованные функции, если это возможно. Это сообщение в блоге , показывающее 43-кратное увеличение при использовании Cython для простого использования.

Answer 5

Для быстрого создания используйте модуль массива.

Использование модуля массива для создания ~ в 5 раз быстрее, но примерно в два раза медленнее для доступа к элементам по сравнению с обычным списком:

# Create array
python -m timeit -s "from array import array" "a = array('I', '\x00'
 * 100000000)"
10 loops, best of 3: 204 msec per loop

# Access array
python -m timeit -s "from array import array; a = array('I', '\x00'
* 100000000)" "a[4975563]"
10000000 loops, best of 3: 0.0902 usec per loop

# Create list
python -m timeit "a = [0] * 100000000"
10 loops, best of 3: 949 msec per loop

# Access list
python -m timeit  -s "a = [0] * 100000000" "a[4975563]"
10000000 loops, best of 3: 0.0417 usec per loop

Answer 6

Маловероятно, что вы найдете что-нибудь быстрее, чем numpy array. Реализация самого массива так же эффективна, как и, скажем, в C (и в основном такая же, как array.array, только с большей полезностью.)

Если вы хотите ускорить свой код, вам придется делать это, делая это. Несмотря на то, что массив реализован эффективно, доступ к нему из кода Python имеет определенные накладные расходы; например, при индексации массива создаются целочисленные объекты, которые нужно создавать на лету. numpy предлагает ряд операций, эффективно реализованных в C, но не видя реального кода, который работает не так, как вам хотелось бы, трудно сделать какие-либо конкретные предложения.

Answer 7

Если

• скорость доступа к array.array приемлема для вашего приложения
• компактное хранилище является наиболее важным
• вы хотите использовать стандартные модули (без зависимости NumPy)
• вы находитесь на платформах с / dev / zero

Вам может быть интересно следующее. Он инициализирует array.array примерно в 27 раз быстрее, чем array.array ('L', [0] * size):

myarray = array.array('L')
f = open('/dev/zero', 'rb')
myarray.fromfile(f, size)
f.close()

Вкл. Как инициализировать целочисленный объект array.array с нулями в Python Я ищу еще лучший способ.

Answer 8

В дополнение к другим отличным решениям, другой способ - использовать dict вместо массива (существующие элементы не равны нулю, в противном случае они равны нулю). Время поиска O (1).

Вы также можете проверить, находится ли ваше приложение в оперативной памяти, а не выгрузить его. Это всего лишь 381 МБ, но система может не дать вам все это по любой причине.

Однако есть и некоторые очень быстрые разреженные матрицы ( SciPy и ndsparse ). Они сделаны на низком уровне C, и также могут быть хорошими.

Answer 9

Я бы просто создал ваш собственный тип данных, который не инициализирует ЛЮБЫЕ значения.

Если вы хотите прочитать индексную позицию, которая НЕ была инициализирована, вы возвращаете нули. Тем не менее, не инициализируйте хранилище.

Если вы хотите прочитать позицию индекса, которая была инициализирована, просто верните значение.

Если вы хотите записать в индексную позицию, которая НЕ была инициализирована, инициализируйте ее и сохраните ввод.

Answer 10

NumPy - подходящий инструмент для большого однородного массива фиксированного размера. Доступ к отдельным элементам чего-либо в Python не будет таким быстрым, хотя операции с целым массивом часто могут выполняться со скоростью, аналогичной C или Fortran. Если вам нужно быстро выполнить операции с миллионами и миллионами элементов по отдельности, из Python вы можете получить только очень много.

Какой алгоритм вы используете? Откуда вы знаете, что использование разреженных массивов слишком медленно, если вы еще не пробовали это? Что вы подразумеваете под "эффективными"? Вы хотите быструю инициализацию? Это узкое место вашего кода?