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

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.