Python memory consumption: dict VS list of tuples
dictionary, list, memory, python, tuples
Solution
Your `list` of `tuple`s adds an extra layer. You have 3 layers of items:
- The outer list of length 1 million, so 1 million pointers
- 1 million 2-slot tuples, so 2 million pointers
- 2 million references to 1 million integer values
while your `dict` only holds:
- The dict (including 1 million cached hashes) with 2 million pointers + extra space to grow the table
- 2 million references to 1 million integer values
It's those 1 million tuples plus the list to hold the references to them that take up more memory than the 1 million cached hashes. There are some 50% more pointers involved here, easily accounting for the 50% more memory use you see.
There is another downside to your list of tuples: lookup time. To find a matching key in the dict, there is a O(1) complexity cost. To do the same in the list of tuples, you have to potentially scan the whole list for a O(n) cost. Don't use a list of tuples if you need to map keys to values.
Problem
There are plenty of questions and discussion about memory consumption of different python data types. Yet few of them (if any) come to a very specific scenario. When you want to store LOTS of key-value data in memory, which data structure is more memory-efficient, a dict or a list of tuples? At beginning I thought dict is more powerful than list of tuples and that power must come with some price, and actually an empty dict DOES occupy more memory than an empty list or tuple (see In-memory size of a Python structure), so I thought using `[(key1, value1), (key2, value2), ...]` would be more memory-efficient than `{key1: value1, key2: value2, ...}`. Looks like I was wrong. Just fire up the following code snippet, and see the mem consumption reported by your OS. I am using Windows XP so that task manager tells me, a large dict eats up "only" 40MB Ram and 40MB VIRTURAL Ram, but a list of tuples eats up 60MB Ram and 60MB Virtual ram. How could that be? ``` from sys import getsizeof as g raw_input('ready, press ENTER') i = 1000000 #p = [(x, x) for x in xrange(i)] # Will print 4,348,736 40,348,736 p = dict((x, x) for x in xrange(i)) # Will print 25,165,964 37,165,964 print g(p), g(p) + sum(g(x) for x in p) raw_input("Check your process's memory consumption now, press ENTER to exit") ``` Update: Thanks for some of the comments below. I wanna clarify: I'm talking about memory-efficiency. And no, in this case no need to worry about key-value lookup efficiency, let's just assume my algorithm will consume them one by one via iterator.