32

I'm putting around 4 million different keys into a Python dictionary. Creating this dictionary takes about 15 minutes and consumes about 4GB of memory on my machine. After the dictionary is fully created, querying the dictionary is fast.

I suspect that dictionary creation is so resource consuming because the dictionary is very often rehashed (as it grows enormously). Is is possible to create a dictionary in Python with some initial size or bucket number?

My dictionary points from a number to an object.

class MyObject:
    def __init__(self):
        # some fields...

d = {}
d[i] = MyObject()  # 4M times on different key...
Boris Verkhovskiy
  • 14,854
  • 11
  • 100
  • 103
tkokoszka
  • 11,647
  • 10
  • 30
  • 25
  • Very similar to http://stackoverflow.com/questions/311775/python-create-a-list-dict-with-initial-capacity – ire_and_curses Aug 19 '09 at 09:13
  • Can you let us know the source / format of your keys, so we can improve the anwsers ? – Bite code Aug 19 '09 at 09:39
  • At the end I learn that my performance problem was NOT coming from dict initialization. Using __slots__ solved the problems, see: http://stackoverflow.com/questions/1336791/dictionary-vs-object-which-is-more-efficient-and-why – tkokoszka Jun 29 '11 at 12:50
  • u should use a database and pull data from the db into a cache as needed – Coder May 19 '21 at 17:45

6 Answers6

44

With performance issues it's always best to measure. Here are some timings:

 d = {}
 for i in xrange(4000000):
     d[i] = None
 # 722ms

 d = dict(itertools.izip(xrange(4000000), itertools.repeat(None)))
 # 634ms

 dict.fromkeys(xrange(4000000))
 # 558ms

 s = set(xrange(4000000))
 dict.fromkeys(s)
 # Not including set construction 353ms

The last option doesn't do any resizing, it just copies the hashes from the set and increments references. As you can see, the resizing isn't taking a lot of time. It's probably your object creation that is slow.

Ants Aasma
  • 53,288
  • 15
  • 90
  • 97
  • It does not matter how I initialize the dictionary, filling it with data always takes a lot of time. Looks like indeed all time is spend on object creation. Thanks! – tkokoszka Aug 19 '09 at 10:32
11

I tried :

a = dict.fromkeys((range(4000000)))

It creates a dictionary with 4 000 000 entries in about 3 seconds. After that, setting values are really fast. So I guess dict.fromkey is definitly the way to go.

Bite code
  • 578,959
  • 113
  • 301
  • 329
  • 5
    +1 for mentioning dict.fromkeys(). Howevery, using range() to specify keys means that you end up with a dict of sequential keys. If that's what is required, why not just use a list? a = [None]*4000000 – Shawn Chin Aug 19 '09 at 09:53
  • 1
    That was not direct solution, just a demonstration that you could use fromkeys to pre-generate the dict in a very sort time. – Bite code Aug 19 '09 at 11:47
  • 3
    In line with the point @ShawnChin raises, what if you don't want numbers 1...4M as keys? Or in more general terms, what if you don't know your keys in advance, but you just know that they are in millions? – posdef Mar 10 '16 at 11:29
7

If you know C, you can take a look at dictobject.c and the Notes on Optimizing Dictionaries. There you'll notice the parameter PyDict_MINSIZE:

PyDict_MINSIZE. Currently set to 8.

This parameter is defined in dictobject.h. So you could change it when compiling Python but this probably is a bad idea.

Ninjakannon
  • 3,751
  • 7
  • 53
  • 76
4

You can try to separate key hashing from the content filling with dict.fromkeys classmethod. It'll create a dict of a known size with all values defaulting to either None or a value of your choice. After that you could iterate over it to fill with the values. It'll help you to time the actual hashing of all keys. Not sure if you'd be able significantly increase the speed though.

Pablo Fernandez
  • 279,434
  • 135
  • 377
  • 622
SilentGhost
  • 307,395
  • 66
  • 306
  • 293
2

If your datas need/can be stored on disc perhaps you can store your datas in a BSDDB database or use Cpickle to load/store your dictionnary

chub
  • 767
  • 6
  • 11
1

Do you initialize all keys with new "empty" instances of the same type? Is it not possible to write a defaultdict or something that will create the object when it is accessed?

u0b34a0f6ae
  • 48,117
  • 14
  • 92
  • 101