В стандартной поставке Python есть один полезный инструмент в библиотеке collections, это класс deque.
он очень похож на простой список но он намного быстрее работает в некоторых случаях.
Например для обработки элементов в начале списка у него есть дополнительные методы: extendleft(), appendleft() и popleft().

Запустим пару тестов!!! 🚀

>>> from collections import deque
>>> import time
>>> 
>>> st = time.perf_counter()
>>> for _ in range(1000):
>>>     l1 = deque()
>>>     for i in range(5000):
>>>         l1.append(i)
>>> en = round(time.perf_counter()-st, 3)
>>> print(f'Test deque: {en}sec')
>>> 
>>> st = time.perf_counter()
>>> for _ in range(1000):
>>>     l2 = list()
>>>     for i in range(5000):
>>>         l2.append(i)
>>> en = round(time.perf_counter()-st, 3)
>>> print(f'Test  list: {en}sec')
Test deque: 0.452sec
Test  list: 0.436sec

Добавление в конец списка работает примерно одинаково. Теперь попробуем вставлять элемент в начало массива.

>>> st = time.perf_counter()
>>> for _ in range(1000):
>>>     l1 = deque()
>>>     for i in range(5000):
>>>         l1.appendleft(i)
>>> en = round(time.perf_counter()-st, 3)
>>> print(f'Test deque: {en}sec')
>>> 
>>> st = time.perf_counter()
>>> for _ in range(1000):
>>>     l2 = list()
>>>     for i in range(5000):
>>>         l2.insert(0, i)
>>> en = round(time.perf_counter()-st, 3)
>>> print(f'Test  list: {en}sec')
Test deque: 0.435sec
Test  list: 6.347sec

Прирост производительности почти в 15 раз! 😲

Тестим функцию pop() (опустим код теста для краткости)

Test deque: 0.48sec
Test  list: 0.529sec

Теперь pop(0) для list и popleft() для deque

Test deque: 0.476sec
Test  list: 3.101sec

Быстрей примерно в 6.5 раз.

Почему так быстро? Дело в том что deque это некий аналог такого типа данных как "linked list data structure", в Python это занывается "двусвязные списки" (doubly-linked lists). Это список, но не в привычном представлении, а с особой оптимизированной структурой. При создании такого массива данные никуда не переносятся а только линкуются оттуда где были.
Да, это похоже на Python-лист, но линковка происходит иначе. Вместо того чтобы собирать некий стек ссылок и назвать его списком, в doubly-linked list каждый элемент просто ссылается на следующий.
Такая структура позволяет значительно ускорить, создание списка, изменение с любой стороны.

Где это может пригодиться? Конечно же в двусторонних очередях (double-ended queue). То есть когда мы добавляем элементы в начало а забираем с конца, или наоборот.
Минус такого подхода в просадке производительности для произвольного доступа к элементам в середине очереди.

Полный код тестов 🌎
______________
Реальное описание несколько сложней, я постарался передать основную суть.

#libs #tricks