Hello again, Guido van Rossum wrote:
Well, there you have hit the nail on the head -- should we document the actual or the guaranteed O() expression? I think this is a can of worms better left unopened. At best we should include some hints to
I will open this can and say that average case complexity is the most important. For example sorting O(nlogn) and dict lookup O(1). But because worst case is important too, it would be nice (but not necessary) if there was an extra column on the table with that information, or blank if not applicable.
clarify that random access to list and tuple elements is constant time in CPython, and that dicts and sets are implemented using a hash table with open hashing -- readers can draw their own conclusions from that.
Notes are nice and already exist at random places in the *huge* documentation archive. But I still believe that the best place for this are the already existing tables in the docs (I pointed them at my initial post). One should trivially be able to find this information. On the other hand notes could be added for various oddities according to experience. For example that for sets up to 10(?) elements, a list would probably be better because of the hashing overhead.
What other implementations do should be up to them -- it becomes a Quality of Implementation issue.
I agree that CPython docs should document CPython behaviour. This would be the most helpful for someone writing a program in CPython. People who use other implementations should consult the appropriate docs. Implementors with worst algorithms should try to reach CPython efficiency.
Regarding the OP's need for this kind of information (deciding between the various standard data types), I would recommend a different approach -- pick the data type that produces the shortest code. In all likelihood it's also the most efficient.
Hmmm, the first thing that comes to mind is prepending an item in a list which is small and seems nice, but is O(n) I think! And besides that, for someone who *cares* about his code good looks is not enough... Thanks for your answers, Dimitris