Take the 2-minute tour ×


  • Python 2.6
  • Ubuntu x64

I have a set of unique integers with values between 1 and 50 million. New integers are added at random e.g. numberset.add(random.randint(1, 50000000)). I need to be able to quickly add new integers and quickly check if an integer is already present.


After a while, the set grows too large for my low memory system and I experience MemoryErrors.


How can I achieve this while using less memory? What's the fastest way to do this using the disk without reconfiguring the system e.g. swapfiles? Should I use a database file like sqlite? Is there a library that will compress the integers in memory?

share|improve this question
32/64 bit? How many in the set when it errors? –  leppie Nov 9 '10 at 9:40
Ubuntu x86_64 GNU/Linux. ~2 million. It's lack of system memory, not a bug. –  2371 Nov 9 '10 at 9:46
You seem to have a set (numberset.add(..)) but you refer to a list twice -- please edit your question to resolve the ambiguity. What Python version? –  John Machin Nov 9 '10 at 9:55
I've updated the question. –  2371 Nov 9 '10 at 10:05
No need to be rude John. A "list" doesn't have to mean a datatype. Emil: The checking is a separate task. –  2371 Nov 9 '10 at 10:48

6 Answers 6

up vote 5 down vote accepted

You can avoid dependencies on 3rd-party bit-array modules by writing your own -- the functionality required is rather minimal:

import array

BITS_PER_ITEM = array.array('I').itemsize * 8

def make_bit_array(num_bits, initially=0):
    num_items = (num_bits + BITS_PER_ITEM - 1) // BITS_PER_ITEM
    return array.array('I', [initially]) * num_items

def set_bit(bit_array, offset):
    item_index = offset // BITS_PER_ITEM
    bit_index = offset % BITS_PER_ITEM
    bit_array[item_index] |= 1 << bit_index

def clear_bit(bit_array, offset):
    item_index = offset // BITS_PER_ITEM
    bit_index = offset % BITS_PER_ITEM
    bit_array[item_index] &= ~(1 << bit_index)

def get_bit(bit_array, offset):
    item_index = offset // BITS_PER_ITEM
    bit_index = offset % BITS_PER_ITEM
    return (bit_array[item_index] >> bit_index) & 1
share|improve this answer
Thanks, I wanted to see a solution that used the disk so the maximum number of items is much greater and I can probably extend this to achieve that. –  2371 Nov 9 '10 at 12:13
You could also avoid importing array by using the built-in bytearray (Python 2.6+) which is a more natural fit to the problem. Also might I suggest item_index, bit_index = divmod(offset, BITSPERITEM) –  Scott Griffiths Nov 9 '10 at 12:39
Nitpick: BITS_PER_ITEM would be better. –  FogleBird Nov 9 '10 at 14:20
@Scott Griffiths: Thanks for the mention of bytearray; I support a module that will run on 2.1 to 2.7 and tend to go for solutions that people stuck on antique Pythons can use. My solution as it stands will work on 2.2+. Using divmod would remove the dependency on the // operator and extend its usability back to 1.5 at least. However as the OP noted, divmod is slower (involves a function call) and I was never brave enough to suggest that Python would benefit from /% and //% operators :-) –  John Machin Nov 9 '10 at 20:01
@Foglebird: You're not wrong. –  John Machin Nov 9 '10 at 20:02

Use a bit-array.This will reduce the need for huge space requirement.

Realted SO Question:

share|improve this answer
+1 - nice to discover some modules I didn't know –  Michał Niklas Nov 9 '10 at 9:52

Use an array of bits as flags for each integer - the memory needed will be only 50 million bits (about 6 MB). There are a few modules that can help. This example uses bitstring, another option is bitarray:

from bitstring import BitArray
i = BitArray(50000000) # initialise 50 million zero bits
for x in xrange(100):
    v = random.randint(1, 50000000)
    if not i[v]: # Test if it's already present
        i.set(1, v) # Set a single bit

Setting and checking bits is very fast and it uses very little memory.

share|improve this answer
Great job on this module and the documentation. Thanks for the example code. –  2371 Nov 9 '10 at 11:13

Try to use array module.

share|improve this answer
Thanks, with this type I can have 10x as many items but it's not a perfect solution. –  2371 Nov 9 '10 at 9:58

If integers are unique then use bits. Example: binary 01011111 means that there are: 1, 3, 4, 5, 6 and 7. This way every bit is used to check if its integer index is used (value 1) or not (value 0).

It was described in one chapter of "Programming Pearls" by Jon Bentley (look for "The file contains at most ten million records; each record is a seven-digit integer.")

It seems that there is bitarray module mentioned by Emil that works this way.

share|improve this answer

Depending on your requirements, you might also consider a bloom filter. It is a memory-efficient data structure for testing if an element is in a set. The catch is that it it can give false-positives, though it will never give false-negatives.

share|improve this answer

Your Answer


