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 _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
