1

I was making a simple function to rearrange a list with very large no of elements say 100,000 or probably 1 million. Here is the code of the function

    def Rearrange():
        global list1
        list1.append(list1[0])
        list1.pop(0)

Basically, this just function just appends the first elements of the list at the last and deletes the first element.
When I included the #2 line of the function the time taken to run the function was around 0.002 seconds for a 100,000 size of the list, while if we comment out that line leaving the function with only the upper statement, the time taken was around 5.2 * 10^-6 seconds. How do you explain this large difference?

devnull
  • 118,548
  • 33
  • 236
  • 227
Pratik Singhal
  • 6,283
  • 10
  • 55
  • 97

3 Answers3

6

From the Python documentation:

It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends.

So the reason for the timings you see is that pop(0) on a list of 100,000 elements requires copying 99,999 pointers.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
4

The append can just add the new element at the end, but with the pop, all existing elements have to be moved one step towards the start of the list.

What you are looking for is a deque, which ensures that both pop and append are O(1) -- see http://docs.python.org/3.3/library/collections.html#collections.deque .

And yes, Python lists really do that, see this line from that link:

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

RemcoGerlich
  • 30,470
  • 6
  • 61
  • 79
1

Python lists are implemented as dynamic-sized arrays. Therefore, adding an item into the array is cheap, there's usually some extra place after. For instance (just a demonstrative example, the exact behavior not guaranteed) : 

l = range(0, 8)
# 0 1 2 3 4 5 6 7 x x x x x x
l.append(8)
# 0 1 2 3 4 5 6 7 8 x x x x x, 1 modification

For popping the first element, the whole array needs to be copied : 

l.pop(0)
# 1 2 3 4 5 6 7 8 x x x x x x, 8 modifications!

That makes the difference.

Danstahr
  • 4,190
  • 22
  • 38
  • There is no `add` method in python lists. Did you mean `append`? – thefourtheye Nov 18 '13 at 14:14
  • 2
    Since when are lists implemented as associative arrays? – Tim Nov 18 '13 at 14:16
  • Since Python exists AFAIK. See the documentation of the usual implemetations or http://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented – Danstahr Nov 18 '13 at 14:21
  • 1
    @Danstahr: an associative array (aka a dictonary) is very different to a "c array" (ie a contiguous block of memory, which is how lists are implemented in CPython). – Tim Nov 18 '13 at 14:39
  • @Tim : You're absolutely right, for unknown reasons I totally messed up the terminology I usually use without any problems. Of course I meant the dynamic-length arrays. – Danstahr Nov 18 '13 at 14:52