[Python] Case where the execution time differs between the built-in list and deque

• If you find any mistakes, please do not hesitate to contact us (even if you request editing).

list type and deque type

Let's look at the behavior of Python's built-in types, list and deque.

Below is the code that creates a list and queue of a certain length and retrieves the elements with. Execute with a length of 10,000, 100,000, and 1 million in order.

import time
from collections import deque


for count in [10000, 100000, 1000000]:
    #Object initialization
    l = ['a'] * count
    q = deque(l)

    #list type operation
    time1 = time.time()
    while len(l) > 0:
        l.pop(0)

    #Operation of deque type
    time2 = time.time()
    while len(q) > 0:
        q.popleft()
    time3 = time.time()

    print('count:', count)
    print(f'list  finished: {time2 - time1} sec.')
    print(f'deque finished: {time3 - time2} sec.')
    print()

The operations to extract the first element and the last element are list type and deque type, respectively, with the following functions.

from collections import deque

#Initialization
l = [1, 2, 3]
q = deque(l)

#Operation to retrieve the first element
l.pop(0)  # => 1
d.popleft()  # => 1

#Operation to retrieve the trailing element
l.pop(-1)  # => 3
d.pop()  # => 3

Execution result

The following results were obtained in the execution environment at hand.

count: 10000
list  finished: 0.006018161773681641 sec.
deque finished: 0.0003972053527832031 sec.

count: 100000
list  finished: 0.9306132793426514 sec.
deque finished: 0.003919839859008789 sec.

count: 1000000
list  finished: 133.8608682155609 sec.
deque finished: 0.04343390464782715 sec.

In the case of 1 million cases, the list type operation took more than 2 minutes.

Why this happens

Quote the relevant part from the official documentation. You can do things like ʻappend and pop` on deque objects, but it mentions how they differ from those on list objects.

A similar operation can be achieved with a list object, but it is specialized for fast fixed-length operations, such as pop (0) and insert (0) that change both the size and position of the internal data representation format. Operations such as, v) require the cost of O (n) to move memory.

On the other hand, the deque object costs only ʻO (1) `.

Summary

Lists are not suitable for data structures whose data length changes frequently.

By the way, the code (list.pop (-1)) that retrieves data not for the first element (list.pop (0)) but for the last element is as follows. In this case, the processing time of ʻO (1)` does not depend on the length of the list, so there is almost no difference in execution time.

• Enter # here in the difference from the above.

import time
from collections import deque


for count in [10000, 100000, 1000000]:
    #Object initialization
    l = ['a'] * count
    q = deque(l)

    #list type operation
    time1 = time.time()
    while len(l) > 0:
        l.pop(-1)  # here1

    #Operation of deque type
    time2 = time.time()
    while len(q) > 0:
        q.pop()  # here2
    time3 = time.time()

    print('count:', count)
    print(f'list  finished: {time2 - time1} sec.')
    print(f'deque finished: {time3 - time2} sec.')
    print()

↓ Execution result

count: 10000
list  finished: 0.0006232261657714844 sec.
deque finished: 0.0005576610565185547 sec.

count: 100000
list  finished: 0.005739688873291016 sec.
deque finished: 0.004764080047607422 sec.

count: 1000000
list  finished: 0.05780482292175293 sec.
deque finished: 0.05013251304626465 sec.