[Python] How can I store `id`s in Python without paying the 28-byte-per-int price?

My Python code stores millions of ids in various data structures, in order to implement a classic algorithm. The run time is good. But the memory usage is awful.

These ids are ints. I assume that since Python ints start at 28 bytes and grow, there's a huge price there. Since they're just opaque ids, not actually mathematical object, I could get by with just 4 bytes for them.

What is a good way to store ids in Python that won't use the full 28 bytes? I need to put them as both keys and values to dicts?

(Note: The common solution of using something like numpy won't work here, because it's not a contiguous array. It's keys and values into a dict, and dicts of dicts, etc.)

I'm also amenable to other Python interpreters that are less memory hungry for ints.

Continue reading...