Speed of string += string

Carl Banks imbosol-1050195048 at aerojockey.com
Sun Apr 13 03:05:11 CEST 2003

Roy Smith wrote:
> As another example, I can guess that Python dictionaries work like STL 
> maps on the inside, but that would be just a guess.

And, it turns out, a poor one.

>  Is inserting an 
> element logN?  


> Is keys() linear?

Yes, but unlike STL map, the keys aren't sorted.  If you want sorted
keys, you'd have to also perform an O(N log N) sort.

> Is del on an element logN?


>  Is 
> has_key() logN?


> Those would be my guesses.  But they're just guesses.

STL map is a binary tree.  Python dict's are hash tables.  I think
getting a sorted list of keys is the only order-of-magnitude advantage
a binary tree has over a hash.


More information about the Python-list mailing list