Large Dictionaries

Roy Smith roy at panix.com
Mon May 15 19:24:36 CEST 2006


Aahz <aahz at pythoncraft.com> wrote:
> Don't forget that adding keys requires resizing the dict, which is a
> moderately expensive operation.

My guess would be that each resize grows the table by a constant
factor, which IIRC, works out to amortized O(n).  It's not as good as
creating the dict the right size in the first place, but it's really
not that bad.  Somewhat more troubling is that it can lead to memory
fragmentation problems.

I don't understand why Python doesn't have a way to give a size hint
when creating a dict.  It seems so obvious to be able to say "d = dict
(size=10*1000*1000)" if you know beforehand that's how many keys
you're going to add.

Looking at the docs, I'm astounded to discover that you can indeed do
exactly that, but you get {size:10000000}.  I am befuddled as to why
people thought creating a dict by keyword would be a useful thing to
do, but left out (and, indeed, eliminated the chance to add the syntax
later) the obviously useful ability to hint at the size.  I suppose we
could still add:

d = {}
d.reserve (10*1000*1000)



More information about the Python-list mailing list