Complexity of standard Python data structures

[Chris Jones]

Tim Peters <tim.one at comcast.net> writes:

> [Tim]
> > Note that it's not true that Python's list is really a vector/array --
> > thelanguage doesn't define its implementation, and doesn't want to.
> 
> [Marcus Alanen]
> > Hmm.  So the Python language is more about specifying _what_ will
> > happen, instead of _how_, with no concern for actual speed or memory?
> 
> The Python language reference manual, and the Python standard library
> reference manual, are like that, and that's par for the course for language
> specs:  they specify syntax ("how is it spelled?") and semantics ("what does
> it mean?").  Everything else falls under pragmatics, often called "quality
> of implementation" issues.  The STL is close to unique, outside the
> real-time world, in making promises related to performance.  For the other
> side, I spent the first 15 years of my career working largely on optimizing
> Fortran compilers and runtime libraries:  no user base was more concerned
> about speed than Fortran's, yet the Fortran standard didn't breathe a word
> about how fast or slow any construct or standard function might be, could
> be, or should be.  Similarly, the IEEE-754 standard for floating-point
> arithmetic doesn't say anthing about speed either.  Standards bodies are
> generally loathe to constrain implementations.
> 
> Of course the Python language itself is distinct from (albeit related to)
> its implementations.  People working on implementations are typically quite
> concerned about speed and memory.  The pragmatic tradeoffs can (and do) vary
> across implementations, though (same as for C, C++, Fortran, Java, etc).

People wanting to program should nail a copy of this posting above their
keyboard.