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

[Alex Martelli]

Marcus Alanen wrote:
   ...
> On the other hand, given the amount of questions regarding big-O
> notation & string += string at the moment on c.l.p, perhaps there
> should be a note -- a "warning" sounds a bit extreme?  Also in the docs
> of C functions, of course!  Sometimes, unix man pages have usage
> examples. Perhaps there should be "anti-usage" examples as well?  :)

Yes, I have changed my mind -- partly thanks to your arguments,
partly because of somebody else (a CS professor) who posted to 
c.l.py trying to understand Python's "lists" after reading the
tutorial -- it seems we wasted quite a bit of his time because
of his assumptions that "list" means "list"... a short footnote
in the tutorial might well help.  Darn -- now I wish I had put
just such a footnote in the Nutshell's Chapter 4 too, rather than 
just mentioning list performance behavior in chapter 17 -- oh well, 
perhaps I can send in a small errata...;-).

> people do seem to start explaining the python list as e.g. "a C++
> vector", or "a contiguous array of heterogeneous elements". I do
> understand that Python people don't want to make any guarantees,
> although describing some implementation might make it easier
> for people to learn (or migrate to) Python.

Yes, I now agree with you -- particularly in the tutorial, it
would help more people than it would hinder.  Thanks for helping
me see the light about this, btw.  Now we'll see if I can maybe
convince the docs' maintainer, and thus get that tiny fix into 
Python's docs in time for 2.3 beta...

An early _focus_ on implementation and performance vs functionality
issues would be too much, but a tiny little mint, oops I mean
footnote, surely _that_ couldn't hurt...


Alex