[Python-Dev] Complexity documentation request

[Dimitrios Apostolou]

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