long-index arrays in python

Question

I'm attempting to shorten the memory footprint of 10B sequential integers by referencing them as indexes in a boolean array. In other words, I need to create an array of 10,000,000,000 elements, but that's well into the "Long" range. When I try to reference an array index greater than sys.maxint the array blows up:

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

Anything I can do? I can't seem to find anyone on the net having this problem... Presumably the answer is "python can't handle arrays bigger than 2B."

Answer 1

From googling around some , e.g. PEP 353 (assuming I'm understanding it) and this exchange it looks like the real issue is probably platform/system dependent. Do you have enough memory to handle 10,000,000,000 entries?

Answer 2

10B booleans (1.25MB of memory, assuming Python is sane)

I think you have your arithmetic wrong -- stored supercompactly, 10B booleans would be 1.25 GIGA, _not__ MEGA, bytes.

A list takes at least 4 bytes per item, so you'd need 40GB to do it the way you want.

You can store an array (see the array module in the standard library) in much less memory than that, so it might possibly fit.

Answer 3

With a 32-bit address space, any language is going to be struggling to be able to address such an array. Then there's the problem of how much real memory you have on your computer.

If you want 10B array elements, each element representing either true or false, use an array.array('I', ...) ...

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

Then you can set and clear bits using the usual masking and shifting operations.

Alternative:

If only a small number of elements are true, or only a small number of elements are false, you could use a set for the best memory saving, or a dict for programming convenience.

Answer 4

A dense bit vector is plausible but it won't be optimal unless you know you won't have more than about 10**10 elements, all clustered near each other, with a reasonably randomized distribution. If you have a different distribution, then a different structure will be better.

For instance, if you know that in that range, [0,10**10), only a few members are present, use a set(), or if the reverse is true, with nearly every element present except for a fraction, use a negated set, ie element not in mySet.

If the elements tend to cluster around small ranges, you could use a run length encoding, something like [xrange(0,10),xrange(10,15),xrange(15,100)], which you lookup into by bisecting until you find a matching range, and if the index is even, then the element is in the set. inserts and removals involve shuffling the ranges a bit.

If your distribution really is dense, but you need a little more than what fits in memory (seems to be typical in practice) then you can manage memory by using mmap and wrapping the mapped file with an adaptor that uses a similar mechanism to the suggested array('I') solution already suggested.

To get an idea of just how compressible you can possibly get, try building a plain file with a reasonable corpus of data in packed form and then apply a general compression algorithm (such as gzip) to see how much reduction you see. If there is much reduction, then you can probably use some sort of space optimization in your code as well.

Answer 5

The bitarray package looks like it might be another useful option.

Answer 6

Another option for very large bit arrays would be to use bitstring. It uses a bytearray (or array.array on older Python versions) to store the data but its interface is just an array of bits. For your case you could use:

>>> 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

I think it's preferable to doing all the bit masking and shifting yourself!