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

[Marcus Alanen]

On Mon, 14 Apr 2003 21:21:02 GMT, Alex Martelli <aleax at aleax.it> wrote:
>It basically seems to me that you're basing your expectations
>of Python docs, and those of C docs, on very different, unfair
>standards -- i.e., perhaps subconsciously, singling Python and
>its docs out for criticism by standards you don't apply to C...

ok, you are right, I was being unfair.

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

>Wrong, actually.  E.g., what happens when you loop doing alist.append
>N times depends NOT just on alist being "a vector/array", but also,
>and crucially so!!!, on the overallocation strategy (size vs capacity 
>in std:: vector terms).  If you think that strategy is "obvious
>from that one single sentence" you're sorely mistaken -- as is shown
>by the fact that Python's strategy in that regard has historically
>changed reasonably recently (almost nobody noticed, except a few
>big-O purists who sleep easier at night knowing append IS now
>amortized O(1) in theory, too, not just in practice;-0).  And what

ok, that's correct as well, I generalized far too much. Curiously,
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.

>> - programming is about meeting requirements
>> - those requirements usually involve correctness to a certain
>> degree, _but_ also memory usage, speed, user interface functionality,
>> error handling, modularity, documentation, extendability.
>order in which you list the "also" requirements is rather weird
>with respect to most code a typical application programmers
>develops in the course of his or her career;-).

Just scramble the order to suit your or the typical application
programmer's tastes. ;)

>Still, this discussion helped me -- thanks.  Basically, you're
>saying you found the Python docs you used to be no better than
>those for other languages, or, at least, not better by enough
>to satisfy your specific interests -- an early focus on HOW
>things are being done rather than on WHAT EXACTLY is being done,
>implementation rather than interface, so to speak.  So, from
>my current, incomplete understanding, I think this is a rather
>"niche", marginal issue.

I didn't mean to start any crusade to change Python docs. If
you consider it a niche, that's just fine with me.

Marcus