Deque vs List

Hi Pythonistas!

Today, we are looking at the performance change of the list and deque. Both the list and deque are the collection of items. But their implementation is different. The list is implemented using a dynamic array but the deque is implemented using a doubly-linked list.

Let us check some common scenarios and performance.

Append item to right and pop from right

import collections

def using_list_right_insert_and_pop():
    a = list(range(100))
    for i in range(100):
        a.append(i)
        a.pop()
    return a

def using_deque_right_insert_and_pop():
    a = collections.deque(range(100))
    for i in range(100):
        a.append(i)
        a.pop()
    return a

time_taken = timeit.timeit(using_list_right_insert_and_pop, number=1000_000)
print("Time taken for the function using_list_right_insert_and_pop: ", time_taken)

time_taken = timeit.timeit(using_deque_right_insert_and_pop, number=1000_000)
print("Time taken for the function using_deque_right_insert_and_pop: ", time_taken)

Output

Time taken for the function using_list_right_insert_and_pop:  5.7768117420000635
Time taken for the function using_deque_right_insert_and_pop:  5.951653588999761

Append the item to the left and pop from left

def using_list_left_insert_and_pop():
    a = list(range(100))
    for i in range(100):
        a.insert(0, i)
        a.pop(0)
    return a

def using_deque_left_insert_and_pop():
    a = collections.deque(range(100))
    for i in range(100):
        a.appendleft(1)
        a.popleft()
    return a

time_taken = timeit.timeit(using_list_left_insert_and_pop, number=1000_000)
print("Time taken for the function using_list_left_insert_and_pop: ", time_taken)

time_taken = timeit.timeit(using_deque_left_insert_and_pop, number=1000_000)
print("Time taken for the function using_deque_left_insert_and_pop: ", time_taken)

Output

Time taken for the function using_list_left_insert_and_pop:  17.491684911999982
Time taken for the function using_deque_left_insert_and_pop:  7.157664188000126

Insert to middle and remove from the middle

def using_list_middle_insert_and_pop():
    a = list(range(100))
    for i in range(100):
        a.insert(50, i)
        a.pop(50)
    return a

def using_deque_middle_insert_and_pop():
    a = collections.deque(range(100))
    for i in range(100):
        a.insert(50, i)
        del a[50]
    return a

time_taken = timeit.timeit(using_list_middle_insert_and_pop, number=1000_000)
print("Time taken for the function using_list_middle_insert_and_pop: ", time_taken)

time_taken = timeit.timeit(using_deque_middle_insert_and_pop, number=1000_000)
print("Time taken for the function using_deque_middle_insert_and_pop: ", time_taken)

Output

Time taken for the function using_list_middle_insert_and_pop:  13.721274969999286
Time taken for the function using_deque_middle_insert_and_pop:  23.367453831000603

Random Access

def using_list_random_access():
    a = list(range(100))
    for _ in range(10):
        index = random.randint(0, 99)
        b = a[index]

def using_deque_random_access():
    a = collections.deque(range(100))
    for _ in range(10):
        index = random.randint(0, 99)
        b = a[index]

time_taken = timeit.timeit(using_list_random_access, number=1000_000)
print("Time taken for the function using_list_random_access: ", time_taken)

time_taken = timeit.timeit(using_deque_random_access, number=1000_000)
print("Time taken for the function using_deque_random_access: ", time_taken)

Output

Time taken for the function using_list_random_access:  5.40886193499864

Time taken for the function using_deque_random_access:  6.293440265000754

Tip

We can see that list is best for inserting and accessing items randomly and deque is best for the appending especially to the left. So use this list and deque according to the operation that performs mostly on the data

Hope you have learned something from this post. Please share your valuable feedback and topics at afsal@parseltongue.co.in 

Happy coding!