Timing Difference: insert vs. append & reverse

[Duncan Booth]

johnfkeeling at yahoo.com (John Keeling) wrote in 
news:35b736b9.0408020330.53b24ed3 at posting.google.com:

> I tried the test program below. My interest is to examine timing
> differences between insert vs. append & reverse for a list. My results
> on my XP Python 2.3.4 are as follows:
> time_reverse  0.889999389648
> time_insert  15.7750005722
> Over multiple runs ... the time taken to insert at the head of a list,
> vs. the time taken to append to a list and then reverse it is
> typically 16 or 17 times longer.
> I would have expected the insert operation to be faster than the
> combined append & reverse operations. Is this behaviour surprising, or
> is there a good reason why there is this large performance difference?

A list is implemented by an array of pointers to the objects it contains.

Every time you call 'insert(0, indx)', all of the pointers already in the 
list have to be moved up once position before the new one can be inserted 
at the beginning.

When you call 'append(indx)' the pointers only have to be copied if there 
isn't enough space in the currently allocated block for the new element. If 
there is space then there is no need to copy the existing elements, just 
put the new element on the end and update the length field. Whenever a new 
block does have to be allocated that particular append will be no faster 
than an insert, but some extra space will be allocated just in case you do 
wish to extend the list further.

If you expected insert to be faster, perhaps you thought that Python used a 
linked-list implementation. It doesn't do this, because in practice (for 
most applications) a list based implementation gives better performance.