Timing Difference: insert vs. append & reverse
duncan.booth at invalid.invalid
Mon Aug 2 13:52:56 CEST 2004
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.
More information about the Python-list