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

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

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

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

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

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

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

  • TypeError: неподдерживаемый тип операндов для%: 'NoneType' и 'str'
  • Как получить python-сервер для преобразования recvline в строку?
  • Реализация кривой Коха?
  • установка IPython с двумя версиями Python (Windows)
  • Модули Jython и python
  • В интерфейсе администратора Django существует ли способ дублировать элемент?
  • Что такое синтаксис обозначения python .. ("dot dot")?
  • Отправить одностороннее сообщение всем потокам в Python
  • 10 Solutions collect form web for “Эффективный массив Python с 100 миллионами нулей?”

    Я сделал некоторое профилирование, и результаты полностью противоречат друг другу. Для простых операций доступа к массиву 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 / sec
      • Инициализация: 2.0s
    • array.array ('L', (0 для i в диапазоне (20000000)))

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

    Напомним, как работают целые числа 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) это число, sizeof(PyListObject) + K * sizeof(PyObject*) + d * sizeof(PyIntObject) память – 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 .

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

     x = [0] * 100000000 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Если

    • скорость доступа 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() 

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

    Python - лучший язык программирования в мире.