Speed of string += string
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?
> 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