Reducing memory used by a large dict

Question

I need to create an in memory object that has keys that are a 9 digit integer and a boolean value associated with each key. I've been using a dict as in the simplified example below:

#!/usr/bin/python
from __future__ import print_function
import sys

myDict = {}
for n in range(56000):
        myDict[n] = True

print('Count:',len(myDict),' Size:', sys.getsizeof(myDict))

I need to be able to look up and retrieve the boolean value associated with each key. The problem is the size of the dict. Using Python 2.7 on a 64 bit Linux system and the above example, the size of the dict is 3.1 megabytes according to sys.getsizeof(). (about 56 bytes per entry to store 9 digits plus a boolean value)

I need to store the boolean state of (approx) 55.000 entries in the dict. Each dict key is a 9 digit integer. I've tried using the integer and str(theInteger) as keys with no change in the size of the dict.

Is there some other sort of data structure or methodology I should be using to conserve memory with such a large data set?

Answer 1

If you look up your boolean with an integer key, and the range of keys starts with 0 and is continuous, there's really no reason not to use a list:

my_list = []
for n in range(56000):
        my_list[n] = True

or better:

my_list = [True for n in range(5600])

If that is not enough, try the array module and use one byte per bool:

import array
my_array = array.array("b", (True for n in range(56000)))

And if that is not good enough, try the bitarray module on PyPi.

Another idea is to use a set: Say you have many more False than True, simply have a set:

my_true_numbers = {0, 2323, 23452} # just the True ones

and check with

value = number in my_true_numbers

If you have more True than False, do it the other way round.

Answer 2

The accepted answer of Python: Reducing memory usage of dictionary has the conclusion that there it not much you can do and i agree with it. The overall memory overhead of a dictionary is small but the number of key-value pairs of your example raises the memory footprint.

There might one think possible: If the keys are always linear you could create a list of booleans directly or better use bitarray. The keys would then be implicit. But if this is only in your example the case you can't do much.