Complexity of standard Python data structures (Re: Speed of string += string)
aleax at aleax.it
Thu Apr 17 17:34:34 CEST 2003
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...
More information about the Python-list