Timing Difference: insert vs. append & reverse

John Keeling johnfkeeling at yahoo.com
Wed Aug 4 16:10:25 CEST 2004


Clarification...

Duncan Booth <duncan.booth at invalid.invalid> wrote in message 
> > True, but an array implementation can easily support amortized 
> > constant-time insert/delete at *either* end (without breaking 
> > constant-time indexing).  The same trick of keeping extra space 
> > at the tail end can work at the head; it requires keeping one 
> > additional offset to show where the occupied cells start.
> > 
> 
> If the OP had said he expected insert and append to be the same speed I 
> might buy that, but he expected insert to be faster than append.

Actually, I never said that ... I said "I would have expected the
insert operation to be faster than the combined append & reverse
operations."  The  object of my test code was to fill out a list in
the reverse order to which I had the list items available.
I would have expected:
tmp2 =[]
for indx in xrange(10000):
    tmp2.insert(0, indx)

to be faster than

tmp1 =[]
for indx in xrange(10000):
    tmp1.append(indx)
tmp1.reverse()

because the insert case does not require the reverse operation. This
would be the case if the insert operated at (approximately) the same
speed as the append, rather then the insert (at position 0) being
16-17 times slower than the append. I guess I somewhat expected it to
be as Bryan Olson stated:"an array implementation can easily support
amortized constant-time insert/delete at *either* end (without
breaking constant-time indexing)."

John



More information about the Python-list mailing list