[Python-Dev] Complexity documentation request

[Guido van Rossum]

On Sun, Mar 9, 2008 at 11:50 AM, Greg Ewing <greg.ewing at canterbury.ac.nz> wrote:
> Aahz wrote:
>  > * Other Python implementations (Jython, PyPy, IronPython) may not be
>  > able to provide the same type implementations
>  >
>  > * Algorithmic information does sometimes change between versions, and
>  > keeping the docs updated is not trivial
>
>  Still, I think there are some general expectations one
>  should be able to have of any implementation, e.g. that
>  accessing a list item is roughly O(1), and not O(n) as
>  it would be if they were implemented as linked lists.
>
>  Dict access should probably be documented as no worse
>  than O(log n) to allow for tree implementations.

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
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.
What other implementations do should be up to them -- it becomes a
Quality of Implementation issue.

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.

-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)