Timing Difference: insert vs. append & reverse

Bryan Olson fakeaddress at nowhere.org
Thu Aug 5 04:41:25 CEST 2004

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.


More information about the Python-list mailing list