Timing Difference: insert vs. append & reverse

[Bryan Olson]

Tim Peters wrote:

 > [Bryan Olson, on complicating the list object again, and 2.4's deque 
type]
 >
 >>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
one.


-- 
--Bryan