Timing Difference: insert vs. append & reverse

[Tim Peters]

[Bryan Olson]
> Hmmm ... let me clarify what I'm selling:  We can make lists
> perform efficiently as double-ended queues without breaking
> anything or perceptibly hurting anyone's efficiency.  Until this
> thread, 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).