Speed of string += string

[Carl Banks]

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?  

Constant.

> 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?

Constant.

>  Is 
> has_key() logN?

Constant.


> 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.


-- 
CARL BANKS