list.pop(0) vs. collections.dequeue

[Alf P. Steinbach]

* Steven D'Aprano:
> On Sat, 23 Jan 2010 09:57:04 -0500, Roy Smith wrote:
> 
>> In article <hje979$kc9$1 at news.eternal-september.org>,
>>  "Alf P. Steinbach" <alfps at start.no> wrote:
>>
>>> But it would IMHO have been better if it wasn't called "list", which
>>> brings in the wrong associations for someone used to other languages.
>> +1.
>>
>> When I first started using Python (back in the 1.4 days), I assumed a
>> list was a singly-linked list.
> 
> Why would you do that? I can think of at least eight different 
> implementations of the abstract list data structure:
> 
> constant-size array
> variable-size array
> variable-size array with amortised O(1) appends
> singly-linked list
> singly-linked list with CDR coding
> doubly-linked list
> skip list
> indexable skip list
> 
> One can reasonably disregard constant-sized arrays as a possibility, 
> given that Python lists aren't fixed size (pity the poor Pascal and 
> Fortran coders who are stuck with static arrays!), but the rest are all 
> reasonable possibilities.

A linked list implementation would yield O(n) indexing. A great many loops in 
e.g. Python libraries code now having linear time would then get quadratic time, 
O(n^2). Those libraries would then be effectively unusable without extensive 
rewriting: one version for ordinary Python and one for 'list-as-list' Pythons...

Thus, the linked list implementations are IMO *not* reasonable.

And the reason is precisely the implied complexity guarantees, especially on 
indexing  --  which could reasonably be O(log n), but not worse than that.


> Why assume one specific implementation in the 
> absence of documentation promising certain performance characteristics?
> 
> 
>> Oddly enough, I was going to write in the above paragraph, "like a C++
>> STL list", until I happened to glance at the STL docs and refreshed my
>> memory that an STL list is doubly-linked.  Which just goes to show that
>> making assumptions based on names is a bad idea.
> 
> Exactly :)
> 
> 
> 
>> So, we're right back to my statement earlier in this thread that the
>> docs are deficient in that they describe behavior with no hint about
>> cost. Given that, it should be no surprise that users make incorrect
>> assumptions about cost.
> 
> There are quite a few problems with having the documentation specify cost:
> 
> (1) Who is going to do it? Any volunteers?

This problem must have been addressed at each time the documentation for some 
version of Python was written or updated.


> (2) Big-oh notation can be misleading, especially for naive users, or 
> those whose intuition for what's fast has been shaped by other languages. 
> Big-oh doesn't tell you whether something is fast or slow, only how it 
> scales -- and sometimes not even then.

It's how things scale that are of interest. :-)

Big-oh tells you an upper asymptotic limit.

That's sufficient for e.g. the C++ standard  --  which, by the way, constitutes 
a concrete example of the practicality of specifying complexity.


> (3) Having documented a particular performance, that discourages 
> implementation changes. Any would-be patch or new implementation not only 
> has to consider that the functional behaviour doesn't change, but that 
> the performance doesn't either.
> 
> In practice the Python developers are unlikely to make an implementation 
> change which leads to radically worse performance, particularly for 
> critical types like list and dict. But in other cases, they might choose 
> to change big-oh behaviour, and not wish to be tied down by documentation 
> of the cost of operations.

Say that there was an O(log n) documented worst complexity for 'list' indexing. 
Above you have described it as "reasonable" to break that, having O(n) 
complexity... But in light of my comments on that, and especially thinking a bit 
about maintainance of two or more! versions of various libraries, don't you 
agree that it would be Just Bad(TM)?


> (4) How much detail is necessary? What about degenerate cases? E.g. dict 
> lookup in CPython is typically O(1) amortised, but if all the keys hash 
> to the same value, it falls to O(N).

 From N1745, the Technical Report 1 on C++ library extensions (will be part of 
the C++0x standard), table 21 specifying general requirements of unordered 
associative containers:

expression:      b.find(k)
return type:     iterator;
assertion:       Returns an iterator pointing to an element with key equivalent
                  to k, or b.end() if no such element exists.
complexity:      Average case O(1), worst case O(b.size()).


> (5) Should the language guarantee such degenerate behaviour? Who decides 
> which costs are guaranteed and which are not?

I think the C++ standard (the latest draft of C++0x is freely available as PDF 
from the commitee pages) provides good guidance in this regard. :-)


> (6) Such performance guarantees should be implementation specific, not 
> language specific. CPython is only one implementation of the language out 
> of many.

Disagree Very Strongly. An implementation may offer stricter guarantees. But 
what matters regarding e.g. avoiding having to maintain two or three or umpteen 
versions of a library, is the set of language level complexity guarantees.


Cheers,

- Alf