Complexity of standard Python data structures

Tim Peters at
Mon Apr 14 23:11:46 CEST 2003

> 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).

More information about the Python-list mailing list