Complexity of standard Python data structures

[Michael Hudson]

marcus at infa.abo.fi (Marcus Alanen) writes:

> >Note that it's not true that Python's list is really a vector/array -- the
> >language doesn't define its implementation, and doesn't want to.  It is true
> 
> Hmm. So the Python language is more about specifying _what_ will
> happen, instead of _how_, with no concern for actual speed or memory?

I'm afraid your line of questioning slightly confuses me.  The Python
language is not specified, in any precise sense of the word, anywhere.
For one thing, it's evolving.  If some super new implementation of
hash tables appeared[1] that had somewhat different algorithmic
behaviour but were considered superior, they might well turn up in
Python 2.5 (say) and *if* the closest thing Python has to a spec (the
language reference) described the algorithmic nature of various
operations (which it doesn't) it would then be changed.

On the other hand, you can take it as read that the Python developers
will make a good faith effort to ensure that each new version of
Python is actually an improvement over its predecessors.

What kind of answers are you expecting to such a question?

Cheers,
M.

[1] Please ignore the unlikelyness of this...

-- 
  > say-hi-to-the-flying-pink-elephants-for-me-ly y'rs,
  No way, the flying pink elephants are carrying MACHINE GUNS!
  Aiiee!!  Time for a kinder, gentler hallucinogen...
                               -- Barry Warsaw & Greg Ward, python-dev