Timing Difference: insert vs. append & reverse

Bryan Olson fakeaddress at nowhere.org
Fri Aug 6 10:35:20 CEST 2004

Tim Peters wrote:

 > [Bryan Olson, on complicating the list object again, and 2.4's deque 
 >>But it breaks (efficient) indexing.  Since we can have it all
 >>like Perl, why not?
 > As I said, the best Perl can do is O(1) amortized.

In fact, as both of us said.

 > If you follow the link you gave last time and read to the bottom
 > following the other links, you'll find that Perl lists had
 > quadratic-time behavior under the steady-state queue pattern for a
 > long time.  That was eventually fixed -- or so they say.  Small
 > details are both tricky and vital.

Agreed.  But those Perl wizards, misguided as they may be, are
pretty sharp.

 > 2.4's deque implementation is
 > obviously immune to "bad" patterns, steady-state queue or otherwise.
 > Most immediately damning, adding another member to the list struct (to
 > keep track of the "low bound") would increase the size of every list
 > object by 8 bytes, on 32-bit boxes.  Python lists are easy to spell,
 > use and access, and some Python apps use millions of small lists.
 > They wouldn't appreciate the RAM hit for a mostly-useless feature.
 > Most Perl programmers seem to be so confused by Perl lists that they
 > only use them when they have to, to shift function arguments in and
 > out <0.6 wink>.

We must know different Perl programmers.

 > That's a use case for lists Python doesn't have at
 > all.
 > You can pursue it if you want to, but with the 2.4 deque type I have
 > no interest in messing more with the list type.

I'm talking about facilities and their implementations, not
people.  True, when I pointed out that Perl nails this one, I
was kinda' thinking the comparison might motivate Pythoners to
pursue the same enhancement.  It was certainly *not* meant to
deride anyone who contributed to implementing Python.

Is Tim the superior Pythoner?  Duh.  Does Python rock?  Sure.
Is saving four-or-eight bytes more or less valuable than
providing efficient insert at both ends?  With all due respect
to Python and the people who implemented it, Perl kicks on this


More information about the Python-list mailing list