массивы длинных индексов в python

Question

Я пытаюсь сократить объем занимаемой памяти 10B последовательных целых чисел, ссылаясь на них как на индексы в логическом массиве. Другими словами, мне нужно создать массив из 10 000 000 000 элементов, но это далеко за пределы диапазона Long. Когда я пытаюсь ссылаться на индекс массива больше sys.maxint, массив взрывается:

x = [False] * 10000000000
Traceback (most recent call last):
  File "", line 1, in 
    x = [0] * 10000000000
OverflowError: cannot fit 'long' into an index-sized integer

Что я могу сделать? Кажется, я не могу найти кого-то в сети с такой проблемой ... Вероятно, ответ таков: "python не может обрабатывать массивы больше 2B".

Answer 1

С 32-битным адресным пространством любой язык будет изо всех сил пытаться обратиться к такому массиву. Тогда возникает проблема того, сколько реальной памяти у вас есть на вашем компьютере.

Если вам нужны элементы массива 10B, каждый элемент представляет true или false, используйте array.array ('I', ...) ...

container = array.array('I', [0]) * ((10000000000 + 31) // 32)

Затем вы можете устанавливать и очищать биты, используя обычные операции маскирования и сдвига.

Альтернатива:

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

Answer 2

Пакет bitarray выглядит так, как будто это еще одна полезная опция.

Answer 3

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

Например, если вы знаете, что в этом диапазоне, [0,10 ** 10), присутствует только несколько членов, используйте set(), или, если верно обратное, почти каждый элемент присутствует, кроме дробь, используйте отрицательный набор, то есть element not in mySet.

Если элементы стремятся сгруппироваться вокруг небольших диапазонов, вы можете использовать кодировку длины прогона, например, [xrange(0,10),xrange(10,15),xrange(15,100)], которую вы просматриваете, разбивая пополам, пока не найдете подходящий диапазон, и если индекс четный, тогда элемент находится в наборе. вставки и удаления включают немного перетасовку диапазонов.

Если ваш дистрибутив действительно плотный, но вам нужно немного больше, чем умещается в памяти (кажется, что это типично на практике), тогда вы можете управлять памятью, используя mmap и оборачивая сопоставленный файл с помощью адаптера, который использует механизм, аналогичный предложенному array('I') решению, уже предложенному.

Чтобы понять, насколько сжимаемы вы можете получить, попробуйте создать простой файл с разумным набором данных в упакованной форме, а затем примените общий алгоритм сжатия (такой как gzip), чтобы увидеть, какое сокращение вы видите. Если есть много сокращений, то вы, вероятно, также можете использовать некоторую оптимизацию пространства в вашем коде.

Answer 4

10B логических значений (1,25 МБ памяти, при условии, что Python нормален)

Я думаю, что у вас неверная арифметика - хранится суперкомпактно, логические значения 10B будут иметь значение 1,25 GIGA , _not__ MEGA , байтов.

Список занимает по крайней мере 4 байта на элемент, поэтому вам потребуется 40 ГБ, чтобы сделать это так, как вы хотите.

Вы можете хранить массив (см. Модуль array в стандартной библиотеке) в гораздо меньшем объеме памяти, чем этот, поэтому он может уместиться.

Answer 5

Другой вариант для очень больших битовых массивов - использовать bitstring . Он использует bytearray (или array.array в более старых версиях Python) для хранения данных, но его интерфейс представляет собой просто массив битов. Для вашего случая вы можете использовать:

>>> from bitstring import BitString
>>> s = BitString(10000000000)         # zero initialised
>>> s.set([9, 999999999, 253])         # set 3 bits to '1'
>>> s[66] = True                       # set another bit
>>> s.allset([9, 66])                  # check if bits are set to '1'
True

Я думаю, что предпочтительнее делать всю битовую маскировку и сдвигать себя!

Answer 6

От поисков вокруг некоторых, например PEP 353 (если я это понимаю) и этот обмен похоже, что реальная проблема, вероятно, зависит от платформы / системы. Достаточно ли у вас памяти для обработки 10 000 000 000 записей?