[Python-Dev] Document performance requirements?

[Nick Coghlan]

Neal Becker wrote:
> On Friday 21 July 2006 7:49 am, Nick Coghlan wrote:
>> Neal Becker wrote:
>>> For a recent project I needed to select a container.  There are plenty of
>>> python data structures to choose from.  It seems that information on
>>> performance is missing (or not easy to find).
>>>
>>> I think Python should include performance in the documentation of common
>>> data structures to help users select the appropriate types.  Something in
>>> the style of c++ STL.
>> Do you mean absolute performance, or do you mean algorithmic order
>> guarantees? I thought the latter were already documented. . .
>>
> 
> The latter.  Where are they documented?

Just because I think something, it doesn't mean it's true :)

The only reference I can actually find is the one in the collections module 
docs pointing out that collections.deque permits O(1) insertions and removals 
at the beginning of the sequence, as well as at the end (whereas lists are 
O(n) for operations at the beginning due to the resulting memory copying).

However, I'm also struggling to think of a case other than list vs deque where 
the choice of a builtin or standard library data structure would be dictated 
by big-O() concerns.

list vs array.array is based on memory efficiency
list vs deque is based on whether or not you need O(1) push/pop at both ends
list vs set is based on whether or not ordering matters
set vs dict is based on whether or not you need to map keys to values

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://www.boredomandlaziness.org