Когда речь заходит о хранении данных упорядоченной последовательности, многим в первую очередь приходит в голову мысль о списках. Пожалуй, списки считают самой популярной контейнерной структурой данных и часто используют для хранения данных любого типа, в том числе целых чисел, строк или пользовательских экземпляров. Изменяемость списков — одна из главных причин этой популярности: элементы списка можно добавлять и удалять.
В некоторых приложениях необходима обработка данных по методу 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 бонусных рублей.
