Timing Difference: insert vs. append & reverse

[Bryan Olson]

Tim Peters wrote:

 > [Bryan Olson]
 >>[...] I hadn't realized that Python's lists are much slower
 >>than Perl's in important cases:
 >>
 >> http://perlmonks.thepen.com/17890.html
 >>
 >>Would this be a PEP-size change, or just a small fix?
 >
 > "Futile" is closer -- it's been debated to death repeatedly.  Python
 > 2.4 adds a deque type instead, with O(1) insert/remove at both ends,
 > regardless of access pattern.  That's O(1) per operation (not just
 > amortized O(1) -- the deque type never needs to move entries).

But it breaks (efficient) indexing.  Since we can have it all
like Perl, why not?

Googling up "dequeue" together with "O(1)" in comp.lang.python,
(and with the misspelling "deque" which returns more results) I
see some discussion, but very little reason against the
enhancement.  One post by Tim Peters suggests difficulty of
implementation as a major reason.


-- 
--Bryan