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

Ответ 1

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

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

a[i] += 1

Профили:

• [0] * 20000000

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

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

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

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

  • Доступ: 175K/sec
  • Инициализация: 2.0s

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

  • Доступ: 175K/sec, предположительно, на основе профиля для другого array.array
  • Инициализация: 6.7s

Ответ 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.

Ответ 3

Попробуйте следующее:

x = [0] * 100000000

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

Использование массива в ~ 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

Ответ 7

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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

Ответ 10

Если

• скорость доступа к массиву 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 Я ищу еще лучший способ.