Когда речь заходит о хранении данных упорядоченной последовательности, многим в первую очередь приходит в голову мысль о списках. Пожалуй, списки считают самой популярной контейнерной структурой данных и часто используют для хранения данных любого типа, в том числе целых чисел, строк или пользовательских экземпляров. Изменяемость списков — одна из главных причин этой популярности: элементы списка можно добавлять и удалять.

В некоторых приложениях необходима обработка данных по методу FIFO (first-in, first-out). Он подразумевает, что элементы, добавленные в последовательность первыми (first-in), будут первыми из неë удалены (first-out). Эту задачу можно решить и с помощью объекта «список», и с помощью двухсторонних очередей. Но для этой цели двухсторонние очереди удобнее списков благодаря особенностям их реализации. 

Команда VK Cloud перевела статью о том, как именно использовать двухсторонние очереди вместо списков и какие преимущества это даст.

FIFO и списки

Допустим, мы создаëм для предприятия систему онлайн-чатов с клиентами. В рабочее время клиенты заходят на сайт, и нам нужно с помощью списка отслеживать, в каком порядке зарегистрировавшиеся клиенты выстраиваются в последовательность. Тот, кто вошëл на сайт первым, должен раньше остальных попасть к только что освободившемуся сотруднику службы поддержки. Следующий фрагмент кода показывает вариант реализации с использованием списков:

clients = list()

def check_in(client):
    clients.append(client)
    print(f"in: New client {client} joined the queue.")
        
def connect_to_associate(associate):
    if clients:
        client_to_connect = clients.pop(0)
        print(f"out: Remove client {client_to_connect}, connecting to {associate}.")
    else:
        print("No more clients are waiting.")

Для размещения данных мы используем объект «список» (clients). Когда клиент заходит в систему, мы добавляем его в конец списка ожидания. Как только сотрудник освобождается, мы удаляем первого клиента из списка, вызывая pop(0). Этот метод не только возвращает первый элемент в списке, но и удаляет его из списка.

В этом случае нам обязательно нужно проверить, есть ли у clients какие-то элементы, потому что, если вызвать pop() для пустого списка, мы получим IndexError. Давайте сымитируем реальный сценарий с использованием этих двух функций:

check_in("John")
check_in("Sam")
connect_to_associate("Emily")
check_in("Danny")
connect_to_associate("Zoe")
connect_to_associate("Jack")
connect_to_associate("Aaron")

# print out the following lines:
in: New client John joined the queue.
in: New client Sam joined the queue.
out: Remove client John, connecting to Emily.
in: New client Danny joined the queue.
out: Remove client Sam, connecting to Zoe.
out: Remove client Danny, connecting to Jack.
No more clients are waiting.

Удаление элемента в начале объекта «список» имеет важное значение. На самом деле Python перемещает каждый элемент в списке, чтобы откорректировать занятость первого элемента в памяти. Это дорогостоящая операция со значительной временной сложностью O(n). Так что имеет смысл рассмотреть альтернативное решение — двухсторонние очереди.

FIFO и двухсторонние очереди

Тип данных deque — это двухсторонняя очередь. Из-за этой «двухсторонности» в ней можно вставлять и удалять элементы с обеих сторон, что и делает еë идеальным типом данных для системы управления клиентскими чатами.

Давайте сравним эту функцию у списка и двухсторонней очереди. Рассмотрим упрощëнный вариант, в котором акцент специально сделан на удалении первого элемента очереди ожидания:

from collections import deque
from timeit import timeit

def time_fifo_testing(n):
    integer_l = list(range(n))
    integer_d = deque(range(n))
    t_l = timeit(lambda: integer_l.pop(0), number=n)
    t_d = timeit(lambda: integer_d.popleft(), number=n)
    return f"{n: <9} list: {t_l:.6e} | deque: {t_d:.6e}"

Тип данных deque доступен через модуль collections. Чтобы сравнить их эффективность, мы используем функцию timeit, которая может вычислять среднюю длительность выполнения для определëнной операции. Аналогично методу pop для списков в двухсторонних очередях первый элемент с левой стороны типа данных deque удаляется с помощью метода popleft.

С этой настройкой функции можно выполнить сравнение несколько раз — для разного количества элементов.

numbers = (100, 1000, 10000, 100000)
for number in numbers:
    print(time_fifo_testing(number))
   
    
100       list: 2.186300e-05 | deque: 1.461700e-05
1000      list: 2.353830e-04 | deque: 1.465280e-04
10000     list: 1.561046e-02 | deque: 1.386711e-03
100000    list: 1.741322e+00 | deque: 1.344412e-02

В этом банальном примере преимущество производительности двухсторонних очередей по сравнению со списками кажется не столь уж заметным. Но для
корпоративных приложений даже небольшая экономия может принести существенный результат. 

Важно и то, что использование типа данных deque не сопряжено с какими-то дополнительными сложностями, так как двухсторонняя очередь входит в состав стандартной библиотеки. Так почему бы не порадовать себя повышением производительности, если всë, что для этого нужно, — обратиться к встроенному типу данных?

Вот модифицированная версия прототипа приложения:

from collections import deque

clients = deque()

def check_in(client):
    clients.append(client)
    print(f"in: New client {client} joined the queue.")

def connect_to_associate(associate):
    if clients:
        client_to_connect = clients.popleft()
        print(f"out: Remove client {client_to_connect}, connecting to {associate}.")
    else:
        print("No more clients are waiting.")

Как видите, при этой реализации меняется модель данных и метод (т.е. popleft) для вызова первого элемента последовательности.

Заключение

Мы рассмотрели двухстороннюю очередь в качестве альтернативной модели данных, способной заменить списки, если в приложении нужен акцент на использовании метода FIFO.

Поскольку deque представляет собой двухстороннюю структуру последовательности данных, она предназначена для операций, в которых элементы добавляются или удаляются с обеих сторон.
Так что при выборе модели данных не обязательно ограничиваться только списками или другими распространëнными типами данных. Когда у бизнеса возникает конкретный запрос, например на использование метода FIFO, нужно рассматривать и альтернативные модели данных.

Команда VK Cloud развивает собственные Big Data-решения. Вы можете их протестировать — для этого мы начисляем новым пользователям 3 000 бонусных рублей.