Complexity of standard Python data structures (Re: Speed of string += string)

[Greg Ewing (using news.cis.dfn.de)]

Marcus Alanen wrote:
> As an example of "unfinished" interfaces: there is no list.clear()
> function, even though dict.clear() exists.

I don't think you need one, because it would be
equivalent to

   del lst[:]

and probably slower as well.

> either Python is doing something very very odd to get
> both methods fast, or then a list is really just a vector and
> list.insert() is O(N) --- something which I would've expected a
> "warning" about.

Giving "warnings" about that sort of thing might scare
people more than is warranted. While technically it's true
that list.insert is O(N) in CPython, you need a very large
list before this becomes apparent, because the data shuffling
is done by such a tight C loop that most of the time it's
practically instantaneous compared to all the machinations
the intepreter is going through to get to each of your
list.insert calls. So, *most* of the time, it's *effectively*
O(1).

I'm not saying that the O() behaviours of these things should
be kept a secret or anything. But you need to interpret them
in the context of how Python works generally. With a C++
mindset, someone might see that list.insert is O(N) and think
"Omigosh! It's O(N)! I can't possibly use that, it'll be far
too slow!" when, in fact, it would be a lot *faster* to use
it instead of coming up with some fancier solution that has
what looks like a better O() behaviour...

-- 
Greg Ewing, Computer Science Dept,
University of Canterbury,	
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg