[Python-Dev] Document performance requirements? (original) (raw)

Armin Rigo arigo at tunes.org
Mon Jul 24 14:56:40 CEST 2006

Hi Giovanni,

On Sun, Jul 23, 2006 at 03:30:50PM +0200, Giovanni Bajo wrote:

I'm not sure big-O tells the whole truth. For instance, do we want to allow an implementation to use a hash table as underlying type for a list? It would match big-O requirements, but would still be slower than a plain array because of higher overhead of implementation (higher constant factor).

A big-O difference can make the difference between a program that takes 0.5 seconds or 2 hours to run. This is more important than a constant factor difference, which different implementations are bound to exhibit anyway.

And if this is allowed, I would like to find in CPython tutorials and documentations a simple statement like: "to implement the list and match its requirements, CPython choose a simple array as underlying data structure".

Yes, the big-O notes don't have to be too technical: the docs should tell people to think about Python lists as simple arrays, and the O requirements follow naturally.

A bientot,

Armin

More information about the Python-Dev mailing list