Deque от Python: внедрение эффективных очередей и стеков

>>> from collections import deque

>>> # Create an empty deque
>>> deque()
deque([])

>>> # Use different iterables to create deques
>>> deque((1, 2, 3, 4))
deque([1, 2, 3, 4])

>>> deque([1, 2, 3, 4])
deque([1, 2, 3, 4])

>>> deque(range(1, 5))
deque([1, 2, 3, 4])

>>> deque("abcd")
deque(['a', 'b', 'c', 'd'])

>>> numbers = {"one": 1, "two": 2, "three": 3, "four": 4}
>>> deque(numbers.keys())
deque(['one', 'two', 'three', 'four'])

>>> deque(numbers.values())
deque([1, 2, 3, 4])

>>> deque(numbers.items())
deque([('one', 1), ('two', 2), ('three', 3), ('four', 4)])


Если вы создадите экземпляр deque без указания iterable в качестве аргумента, то получите пустое значение deque. Если вы предоставляете и вводите iterable, то deque инициализирует новый экземпляр данными из него. Инициализация выполняется слева направо с использованием deque.append().
Инициализатор deque принимает следующие два необязательных аргумента:

iterable содержит повторяющийся элемент, который предоставляет данные инициализации.
maxlen содержит целое число , которое определяет максимальную длину строки.

Как упоминалось ранее, если вы не укажете iterable, то получите пустой запрос deque. Если вы укажете значение в maxlen,, то в вашем deque будет храниться только maxlen элементов.
Наконец, вы также можете использовать неупорядоченные повторяющиеся элементы, такие как наборы, для инициализации ваших значений. В таких случаях у вас не будет заранее определенного порядка для товаров в окончательной заявке.
Эффективное отображение и добавление элементов
Самое важное различие между deque и list заключается в том, что первый позволяет выполнять эффективные операции добавления и извлечения на обоих концах последовательности. Класс deque реализует специальные методы .popleft() и .appendleft(), которые работают непосредственно с левым концом последовательности:

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4])
>>> numbers.popleft()
1
>>> numbers.popleft()
2
>>> numbers
deque([3, 4])

>>> numbers.appendleft(2)
>>> numbers.appendleft(1)
>>> numbers
deque([1, 2, 3, 4])


Здесь вы используете .popleft() и .appendleft() для удаления и добавления значений, соответственно, в левый конец numbers. Эти методы специфичны для разработки deque, и вы не найдете их в list.
Точно так же, как list, deque также предоставляет .append() и .pop() методы для работы с правым концом последовательности. Однако .pop() ведет себя по-другому:

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4])
>>> numbers.pop()
4

>>> numbers.pop(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: pop() takes no arguments (1 given)


Здесь .pop() удаляет и возвращает последнее значение в deque. Метод не принимает индекс в качестве аргумента, поэтому вы не можете использовать его для удаления произвольных элементов из ваших deques. Вы можете использовать его только для удаления и возврата самого правого элемента.
Как вы узнали ранее, deque реализован в виде двусвязного списка. Таким образом, каждый элемент в данном списке содержит ссылку (указатель) на следующий и предыдущий элементы в последовательности.
Двусвязные списки упрощают добавление и удаление элементов с обоих концов. Это возможно, потому что обновлять нужно только указатели. В результате обе операции имеют одинаковую производительность, O(1). Они также предсказуемы с точки зрения производительности, поскольку нет необходимости перераспределять память и перемещать существующие элементы для добавления новых.
Добавление и удаление элементов из левого конца обычного списка Python требует перемещения всех элементов, что в конечном итоге является операцией O(n). Кроме того, для добавления элементов в правый конец списка часто требуется, чтобы Python перераспределил память и скопировал текущие элементы в новую ячейку памяти. После этого он может добавлять новые элементы. Этот процесс занимает больше времени, и операция добавления изменяется с O(1) на O(n).
Рассмотрим следующие тесты производительности для добавления элементов в левый конец последовательности, deque против list:

# time_append.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = []
a_deque = deque()

def average_time(func, times):
    total = 0.0
    for i in range(times):
        start = perf_counter()
        func(i)
        total += (perf_counter() - start) * 1e9
    return total / times

list_time = average_time(lambda i: a_list.insert(0, i), TIMES)
deque_time = average_time(lambda i: a_deque.appendleft(i), TIMES)
gain = list_time / deque_time

print(f"list.insert()      {list_time:.6} ns")
print(f"deque.appendleft() {deque_time:.6} ns  ({gain:.6}x faster)")


В этом скрипте average_time() вычисляет среднее время, которое занимает выполнение функции (func) из заданного числа times. Если вы запустите скрипт из командной строки, то получите следующий результат:

$ python time_append.py
list.insert()      3735.08 ns
deque.appendleft() 238.889 ns  (15.6352x faster)


В этом конкретном примере .appendleft() на deque выполняется в несколько раз быстрее, чем .insert() на list. Обратите внимание, что deque.appendleft() равно O(1), что означает, что время выполнения постоянно. Однако list.insert() в левом конце списка находится O(n), что означает, что время выполнения зависит от количества обрабатываемых элементов.
В этом примере, если вы увеличите значение TIMES, то вы получите более длительные измерения времени для list.insert(), но стабильные (постоянные) результаты для deque.appendleft(). Если вы хотите попробовать аналогичный тест производительности при выполнении pop-операций как для deques, так и для списков, то вы можете расширить приведенный ниже блок упражнений и сравнить свои результаты с результатами реального Python после того, как закончите.


В качестве упражнения вы можете изменить приведенный выше сценарий, установив время выполнения операций deque.popleft() против list.pop(0) и оценив их производительность.


Вот скрипт, который проверяет производительность операций deque.popleft() и list.pop(0):

# time_pop.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)

def average_time(func, times):
    total = 0.0
    for _ in range(times):
        start = perf_counter()
        func()
        total += (perf_counter() - start) * 1e9
    return total / times

list_time = average_time(lambda: a_list.pop(0), TIMES)
deque_time = average_time(lambda: a_deque.popleft(), TIMES)
gain = list_time / deque_time

print(f"list.pop(0)     {list_time:.6} ns")
print(f"deque.popleft() {deque_time:.6} ns  ({gain:.6}x faster)")


Если вы запустите этот скрипт на своем компьютере, то получите результат, аналогичный следующему:

list.pop(0)     2002.08 ns
deque.popleft() 326.454 ns  (6.13282x faster)


Опять же, deque работает быстрее, чем list, когда дело доходит до удаления элементов из левого конца базовой последовательности. Попробуйте изменить значение TIMES и посмотрите, что произойдет!
Тип данных deque был разработан таким образом, чтобы гарантировать эффективность операций добавления и извлечения в любом конце последовательности. Он идеально подходит для решения задач, требующих реализации структур данных очереди и стека в Python.
Доступ к случайным элементам в deque
 Функция deque в Python возвращает изменяемые последовательности, которые работают аналогично спискам. Помимо того, что deques позволяет эффективно добавлять и извлекать элементы с их концов, они предоставляют группу методов, похожих на списки, и другие операции, похожие на последовательности, для работы с элементами в произвольных местах. Вот некоторые из них:



Option
Description




.insert(i, value)
Insert an item value into a deque at index i.


.remove(value)
Remove the first occurrence of value, raising ValueError if the value doesn’t exist.


a_deque[i]
Retrieve the item at index i from a deque.


del a_deque[i]
Remove the item at index i from a deque.



Вы можете использовать эти методы и приемчики для работы с элементами, расположенными в любом положении внутри объекта deque. Вот как это сделать:

>>> from collections import deque

>>> letters = deque("abde")

>>> letters.insert(2, "c")
>>> letters
deque(['a', 'b', 'c', 'd', 'e'])

>>> letters.remove("d")
>>> letters
deque(['a', 'b', 'c', 'e'])

>>> letters[1]
'b'

>>> del letters[2]
>>> letters
deque(['a', 'b', 'e'])


Здесь вы сначала вставляете "c" в letters в позиции 2. Затем вы удаляете "d" из списка, используя .remove(). Ссылки также позволяют индексировать для доступа к элементам, которые вы используете здесь для доступа к "b" по индексу 1. Наконец, вы можете использовать ключевое слово del , чтобы удалить все существующие элементы из списка. Обратите внимание, что .remove() позволяет удалять элементы по значению, в то время как del удаляет элементы по индексу.
Несмотря на то, что объекты deque поддерживают индексацию, они не поддерживают нарезку. Другими словами, вы не можете извлечь  фрагмент из существующего deque, используя синтаксис фрагментов, [start:stop:step], как это было бы с обычным списком :

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4, 5])

>>> numbers[1:3]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'


Разделители поддерживают индексацию, но, что интересно, они не поддерживают нарезку. При попытке получить фрагмент из разделителя, вы получаете TypeError. В общем случае выполнение разбивки на части связанного списка было бы неэффективным, поэтому эта операция недоступна.
До сих пор вы видели, что deque очень похож на list. Однако, в то время как list основан на массивах , deque основан на двусвязном списке.
За deque реализацией в виде двусвязного списка скрыты издержки: доступ, вставка и удаление произвольных элементов не являются эффективными операциями. Чтобы выполнить их, интерпретатор должен выполнить итерацию по списку, пока не доберется до нужного элемента. Таким образом, это O(n) вместо O(1) операций.
Вот скрипт, который показывает, как ведут себя деки и списки, когда дело доходит до работы с произвольными элементами:

# time_random_access.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)

def average_time(func, times):
    total = 0.0
    for _ in range(times):
        start = perf_counter()
        func()
        total += (perf_counter() - start) * 1e6
    return total / times

def time_it(sequence):
    middle = len(sequence) // 2
    sequence.insert(middle, "middle")
    sequence[middle]
    sequence.remove("middle")
    del sequence[middle]

list_time = average_time(lambda: time_it(a_list), TIMES)
deque_time = average_time(lambda: time_it(a_deque), TIMES)
gain = deque_time / list_time

print(f"list  {list_time:.6} μs ({gain:.6}x faster)")
print(f"deque {deque_time:.6} μs")


Этот скрипт выполняет вставку, удаление и доступ к элементам в середине строки и списка. Если вы запустите скрипт, то получите результат, который выглядит следующим образом:

$ python time_random_access.py
list  63.8658 μs (1.44517x faster)
deque 92.2968 μs


Списки не являются структурами данных с произвольным доступом, как списки. Поэтому доступ к элементам из середины списка менее эффективен, чем выполнение того же действия со списком. Главный вывод здесь заключается в том, что определения не всегда более эффективны, чем списки.
 deque В Python оптимизирован для операций с любым концом последовательности, поэтому в этом отношении он неизменно лучше списков. С другой стороны, списки лучше подходят для операций с произвольным доступом и фиксированной длиной. Вот некоторые различия между deques и lists с точки зрения производительности:



Operation
deque
list




Accessing arbitrary items through indexing
O(n)
O(1)


Popping and appending items on the left end
O(1)
O(n)


Popping and appending items on the right end
O(1)
O(1) + reallocation


Inserting and deleting items in the middle
O(n)
O(n)



В случае списков, .append() снижает производительность из-за перераспределения памяти, когда интерпретатору необходимо увеличить список, чтобы принимать новые элементы. Эта операция требует копирования всех текущих элементов в новую ячейку памяти, что существенно влияет на производительность.
Это краткое изложение может помочь вам выбрать подходящий тип данных для конкретной задачи. Однако, прежде чем переходить от списков к декодированию, обязательно профилируйте свой код. У обоих есть свои сильные стороны в работе.
Построение эффективных очередей С помощью deque
Как вы уже узнали, deque реализована в виде двусторонней очереди, которая представляет собой обобщение стеков и очередей. В этом разделе вы узнаете, как использовать deque для реализации вашей собственной очереди абстрактных типов данных (ADT) на низком уровне элегантным, эффективным и основанным на Python способом.
 Примечание: В стандартной библиотеке Python вы найдете queue. Этот модуль реализует очереди с несколькими производителями и несколькими потребителями, которые позволяют безопасно обмениваться информацией между несколькими потоками.
Если вы работаете с очередями, то предпочитайте использовать эти высокоуровневые абстракции, а не deque, если только вы не реализуете свою собственную структуру данных.
Очереди - это коллекции элементов. Вы можете изменять очереди, добавляя элементы с одного конца и удаляя элементы с противоположного конца.
Очереди управляют своими элементами в режиме Первый вход/первый выход. ( FIFO) мода. Они работают как конвейер, в который вы помещаете новые элементы на одном конце конвейера и извлекаете старые элементы с другого конца. Добавление элемента в один конец очереди называется операцией постановка в очередь. Удаление элемента с другого конца называется Удалением из очереди.
Чтобы лучше понять очереди, возьмите в качестве примера свой любимый ресторан. В ресторане есть очередь из людей, ожидающих, когда им закажут еду. Как правило, в конце очереди стоит тот, кто приходит последним. Человек, стоящий в начале очереди, покинет ее, как только освободится столик.
Вот как вы можете эмулировать процесс, используя простой объект deque:

>>> from collections import deque

>>> customers = deque()

>>> # People arriving
>>> customers.append("Jane")
>>> customers.append("John")
>>> customers.append("Linda")

>>> customers
deque(['Jane', 'John', 'Linda'])

>>> # People getting tables
>>> customers.popleft()
'Jane'
>>> customers.popleft()
'John'
>>> customers.popleft()
'Linda'

>>> # No people in the queue
>>> customers.popleft()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque


Здесь вы сначала создаете пустой объект deque, который представляет очередь людей, прибывающих в ресторан. Чтобы поместить пользователя в очередь, вы используете .append(),, который добавляет отдельные элементы в правый конец. Чтобы удалить пользователя из очереди, вы используете .popleft(),, который удаляет и возвращает отдельные элементы в левой части списка.
Круто! Ваше моделирование очереди работает! Однако, поскольку deque является обобщением, его API не соответствует типичному API очереди. Например, вместо .enqueue() у вас есть .append(). У вас также есть .popleft() вместо .dequeue(). Кроме того, deque предоставляет несколько других операций, которые могут не соответствовать вашим конкретным потребностям.
Хорошей новостью является то, что вы можете создавать пользовательские классы очередей с нужной вам функциональностью и ничем иным. Для этого вы можете использовать deque для хранения данных и обеспечения желаемой функциональности в ваших пользовательских очередях. Вы можете рассматривать это как реализацию шаблона проектирования адаптера , в котором   вы преобразуете интерфейс deque во что-то, что больше похоже на интерфейс очереди.
Например, предположим, что вам нужен пользовательский абстрактный тип данных очереди, который предоставляет только следующие функции:

Размещение элементов в очереди
Удаление элементов из очереди
Возвращает длину очереди
Поддерживает проверку членства
Поддерживает обычную и обратную итерацию
Предоставление удобного для пользователя строкового представления

В этом случае вы можете написать класс Queue, который выглядит следующим образом:

# custom_queue.py

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        try:
            return self._items.popleft()
        except IndexError:
            raise IndexError("dequeue from an empty queue") from None

    def __len__(self):
        return len(self._items)

    def __contains__(self, item):
        return item in self._items

    def __iter__(self):
        yield from self._items

    def __reversed__(self):
        yield from reversed(self._items)

    def __repr__(self):
        return f"Queue({list(self._items)})"


Здесь ._items содержит deque объект, который позволяет хранить элементы в очереди и манипулировать ими. Queue реализует .enqueue() с помощью deque.append() чтобы добавить элементы в конец очереди. Он также реализует .dequeue() с помощью deque.popleft() для эффективного удаления элементов из начала очереди.
Специальные методы  поддерживают   следующие функции:



Method
Support




.__len__()
Length with len()


.__contains__()
Membership tests with in


.__iter__()
Normal iteration


.__reversed__()
Reverse iteration


.__repr__()
String representation



В идеале, .__repr__() должна возвращать строку, представляющую допустимое выражение Python. Это выражение позволит вам однозначно воссоздать объект с тем же значением.
Однако в приведенном выше примере цель состоит в том, чтобы использовать возвращаемое методом значение  для корректного   отображения объекта в интерактивной оболочке. Вы можете создать возможность создавать экземпляры Queue из этого конкретного строкового представления, приняв итерацию инициализации в качестве аргумента для .__init__() и создавая экземпляры на его основе.
С этими последними дополнениями ваш класс Queue завершен. Чтобы использовать этот класс в своем коде, вы можете сделать что-то вроде следующего:

>>> from custom_queue import Queue

>>> numbers = Queue()
>>> numbers
Queue([])

>>> # Enqueue items
>>> for number in range(1, 5):
...     numbers.enqueue(number)
...
>>> numbers
Queue([1, 2, 3, 4])

>>> # Support len()
>>> len(numbers)
4

>>> # Support membership tests
>>> 2 in numbers
True
>>> 10 in numbers
False

>>> # Normal iteration
>>> for number in numbers:
...     print(f"Number: {number}")
...
Number: 1
Number: 2
Number: 3
Number: 4


В качестве упражнения вы можете протестировать оставшиеся функции и реализовать другие возможности, такие как поддержка тестов на равенство, удаление случайных элементов и доступ к ним и многое другое. Попробуйте!
Изучение других возможностей deque
В дополнение к функциям, которые вы уже видели, deque также предоставляет другие методы и атрибуты, характерные для их внутренней структуры. Они добавляют новые полезные функции к этому универсальному типу данных.
В этом разделе вы узнаете о других методах и атрибутах, предоставляемых deques, о том, как они работают и как их использовать в вашем коде.
Ограничение максимального количества элементов: maxlen
Одной из наиболее полезных функций deque является возможность указать максимальную длину заданного значения, используя аргумент maxlen, когда вы создание экземпляра класса.
Если вы укажете значение maxlen, то в вашем deque будет храниться только maxlen элементов. В этом случае у вас есть  ограниченный вывод. Как только ограниченный список заполняется указанным количеством элементов, добавление нового элемента на обоих концах автоматически удаляет элемент на противоположном конце:

>>> from collections import deque

>>> four_numbers = deque([0, 1, 2, 3, 4], maxlen=4) # Discard 0
>>> four_numbers
deque([1, 2, 3, 4], maxlen=4)

>>> four_numbers.append(5)  # Automatically remove 1
>>> four_numbers
deque([2, 3, 4, 5], maxlen=4)

>>> four_numbers.append(6)  # Automatically remove 2
>>> four_numbers
deque([3, 4, 5, 6], maxlen=4)

>>> four_numbers.appendleft(2) # Automatically remove 6
>>> four_numbers
deque([2, 3, 4, 5], maxlen=4)

>>> four_numbers.appendleft(1)  # Automatically remove 5
>>> four_numbers
deque([1, 2, 3, 4], maxlen=4)

>>> four_numbers.maxlen
4


Если количество элементов во входной итерируемой переменной больше, чем maxlen, то deque отбрасывает крайние левые элементы (0 в примере). Как только список заполнится, добавление элемента на любом конце автоматически приведет к удалению элемента на другом конце.
Обратите внимание, что если вы не укажете значение maxlen, то по умолчанию оно будет равно None,, и количество элементов может увеличиться до произвольного числа .
Возможность ограничить максимальное количество элементов позволяет использовать deques для отслеживания последних элементов в заданной последовательности объектов или событий. Например, вы можете отслеживать последние пять транзакций по банковскому счету, последние десять открытых текстовых файлов в редакторе, последние пять страниц в браузере и многое другое.
Обратите внимание, что maxlen доступен в качестве атрибута только для чтения в ваших deques, что позволяет вам проверить, заполнен ли deques, как в deque.maxlen == len(deque).
Наконец, вы можете установить для maxlen любое положительное целое число, представляющее максимальное количество элементов, которые вы хотите сохранить в определенном хранилище. Если вы введете отрицательное значение в maxlen, то получите ValueError.
Вращение элементов: .rotate()
Еще одной интересной особенностью deques является возможность поворачивать их элементы, вызывая .rotate() для непустого deques. Этот метод принимает целое число n в качестве аргумента и поворачивает элементы на n шагов вправо. Другими словами, он перемещает n элементов с правого конца на левый по кругу.
Значение по умолчанию для n равно 1. Если вы укажете отрицательное значение для n, то поворот будет влево:

>>> from collections import deque

>>> ordinals = deque(["first", "second", "third"])

>>> # Rotate items to the right
>>> ordinals.rotate()
>>> ordinals
deque(['third', 'first', 'second'])

>>> ordinals.rotate(2)
>>> ordinals
deque(['first', 'second', 'third'])

>>> # Rotate items to the left
>>> ordinals.rotate(-2)
>>> ordinals
deque(['third', 'first', 'second'])

>>> ordinals.rotate(-1)
>>> ordinals
deque(['first', 'second', 'third'])


В этих примерах вы поворачиваете ordinals несколько раз, используя .rotate() с разными значениями n. Если вы вызываете .rotate() без аргумента, то он использует значение по умолчанию n и поворачивает позицию deque 1 вправо. Вызов метода с отрицательным значением n позволяет поворачивать элементы влево.
Добавление сразу нескольких элементов: .extendleft()
Как и в обычных списках, в deques есть метод .extend(), который позволяет добавлять несколько элементов в правый конец списка, используя iterable в качестве аргумента. Кроме того, в deque есть метод с именем extendleft(),, который принимает iterable в качестве аргумента и добавляет свои элементы в левый конец целевого deque за один раз:

>>> from collections import deque

>>> numbers = deque([1, 2])

>>> # Extend to the right
>>> numbers.extend([3, 4, 5])
>>> numbers
deque([1, 2, 3, 4, 5])

>>> # Extend to the left
>>> numbers.extendleft([-1, -2, -3, -4, -5])
>>> numbers
deque([-5, -4, -3, -2, -1, 1, 2, 3, 4, 5])


Вызов .extendleft() с помощью iterable расширяет целевой диапазон влево. Внутри .extendleft() выполняется серия отдельных .appendleft() операций, которые обрабатывают вводимые данные, повторяющиеся слева направо. В результате элементы добавляются в обратном порядке в левый конец целевого списка.
Используя функции, подобные последовательности, в deque
Поскольку deques являются изменяемыми последовательностями, они реализуют почти все методы и операции, которые являются общими для последовательностей и изменяемых последовательностей. К настоящему времени вы узнали о некоторых из этих методов и операций, таких как .insert(), индексация, тесты на членство и многое другое.
Вот несколько примеров других действий, которые вы можете выполнить с объектами deque:

>>> from collections import deque

>>> numbers = deque([1, 2, 2, 3, 4, 4, 5])

>>> # Concatenation
>>> numbers + deque([6, 7, 8])
deque([1, 2, 2, 3, 4, 4, 5, 6, 7, 8])

>>> # Repetition
>>> numbers * 2
deque([1, 2, 2, 3, 4, 4, 5, 1, 2, 2, 3, 4, 4, 5])

>>> # Common sequence methods
>>> numbers = deque([1, 2, 2, 3, 4, 4, 5])
>>> numbers.index(2)
1
>>> numbers.count(4)
2

>>> # Common mutable sequence methods
>>> numbers.reverse()
>>> numbers
deque([5, 4, 4, 3, 2, 2, 1])

>>> numbers.clear()
>>> numbers
deque([])


Вы можете использовать оператор сложения  (+) для объединения двух существующих значений. С другой стороны, оператор умножения (*) возвращает новое значение, эквивалентное повторению исходного значения столько раз, сколько вы хотите.
Что касается других методов определения последовательности, то в следующей таблице приведена краткая информация:



Method
Description




.clear()
Remove all the elements from a deque.


.copy()
Create a shallow copy of a deque.


.count(value)
Count the number times value appears in a deque.


.index(value)
Return the position of value in the deque.


.reverse()
Reverse the elements of the deque in place and then return None.



Здесь .index() также может принимать два необязательных аргумента: start и stop. Они позволяют ограничить поиск теми элементами, которые находятся в start и перед stop или после них. Метод выдает запрос ValueError если value не отображается в имеющемся списке.
В отличие от списков, в deques нет метода .sort() для сортировки последовательности на месте. Это связано с тем, что сортировка связанного списка была бы неэффективной операцией. Если вам когда-нибудь понадобится отсортировать данные, вы все равно можете использовать sorted().
Приведение в действие deque из Python
Вы можете использовать deques в большом количестве вариантов использования, например, для реализации очередей, стеков и циклических буферов. Вы также можете использовать их для ведения журнала отмен и повторов, постановки в очередь входящих запросов к веб-службе , ведения   списка недавно открытых файлов и веб-сайтов, безопасного обмена данными между несколькими потоками и многого другого.
В следующих разделах вы создадите несколько небольших примеров, которые помогут вам лучше понять, как использовать deques в вашем коде.
Ведение истории страниц
Наличие maxlen для ограничения максимального количества элементов делает deque подходящим для решения нескольких задач. Например, предположим, что вы создаете приложение, которое  собирает данные из поисковых систем и сайтов социальных сетей. В какой-то момент вам потребуется отслеживать три последних сайта, с которых ваше приложение запрашивало данные.
Чтобы решить эту проблему, вы можете использовать deque с maxlen из 3:

>>> from collections import deque

>>> sites = (
...     "google.com",
...     "yahoo.com",
...     "bing.com"
... )

>>> pages = deque(maxlen=3)
>>> pages.maxlen
3

>>> for site in sites:
...     pages.appendleft(site)
...

>>> pages
deque(['bing.com', 'yahoo.com', 'google.com'], maxlen=3)

>>> pages.appendleft("facebook.com")
>>> pages
deque(['facebook.com', 'bing.com', 'yahoo.com'], maxlen=3)

>>> pages.appendleft("twitter.com")
>>> pages
deque(['twitter.com', 'facebook.com', 'bing.com'], maxlen=3)


В этом примере pages содержит список трех последних сайтов, которые посетило ваше приложение. Как только pages заполнится, добавление нового сайта в конец списка автоматически приведет к удалению сайта в противоположном конце. Таким образом, в вашем списке будут обновлены три последних сайта, которые вы использовали.
Обратите внимание, что вы можете установить значение maxlen в любое положительное целое число, представляющее количество элементов, которые будут храниться в имеющемся хранилище. Например, если вы хотите сохранить список из десяти сайтов, то вы можете установить для maxlen значение 10.
Обмен данными между Потоками
Python deque также полезен при написании многопоточных приложений, как описано Раймондом Хеттингером, разработчик ядра Python и создатель deque и модуля collections:

Операции deque .append(), .appendleft(), .pop(), .popleft(), и len(d) в CPython являются потокобезопасными. (Источник)

Благодаря этому вы можете безопасно добавлять и удалять данные с обоих концов deque одновременно из отдельных потоков без риска повреждения данных или других связанных с этим проблем.
Чтобы попробовать, как deque работает в многопоточном приложении, запустите свой любимый  редактор кода, создайте новый скрипт с именем threads.py и добавьте следующий код к нему:

# threads.py

import logging
import random
import threading
import time
from collections import deque

logging.basicConfig(level=logging.INFO, format="%(message)s")

def wait_seconds(mins, maxs):
    time.sleep(mins + random.random() * (maxs - mins))

def produce(queue, size):
    while True:
        if len(queue) < size:
            value = random.randint(0, 9)
            queue.append(value)
            logging.info("Produced: %d -> %s", value, str(queue))
        else:
            logging.info("Queue is saturated")
        wait_seconds(0.1, 0.5)

def consume(queue):
    while True:
        try:
            value = queue.popleft()
        except IndexError:
            logging.info("Queue is empty")
        else:
            logging.info("Consumed: %d -> %s", value, str(queue))
        wait_seconds(0.2, 0.7)

logging.info("Starting Threads...\n")
logging.info("Press Ctrl+C to interrupt the execution\n")

shared_queue = deque()

threading.Thread(target=produce, args=(shared_queue, 10)).start()
threading.Thread(target=consume, args=(shared_queue,)).start()


Здесь produce() принимает queue и size в качестве аргументов. Затем он использует random.randint() в цикле while для непрерывного создания случайных чисел и сохраните их в  глобальном  списке под названием shared_queue. Поскольку добавление элементов в deque является потокобезопасной операцией, вам не нужно использовать блокировку для защиты общих данных от других потоков.
Вспомогательная функция wait_seconds() имитирует, что и produce(), и consume() представляют собой длительные операции. Он возвращает случайное значение времени ожидания в заданном диапазоне секунд, mins и maxs.
В consume() вы вызываете .popleft() внутри цикла для систематического извлечения и удаления данных из shared_queue. Вы завершаете вызов .popleft() в инструкции try ... except для обработки тех случаев, когда общая очередь пуста.
Обратите внимание, что, хотя вы определили shared_queue в глобальном  пространстве имен, вы получаете к нему доступ через локальные переменные внутри produce() и consume(). Прямой доступ к глобальной переменной был бы более проблематичным и определенно не лучшим решением.
Последние две строки скрипта создают и запускают отдельные потоки для одновременного выполнения produce() и consume(). Если вы запустите скрипт из командной строки, то получите результат, похожий на следующий:

$ python threads.py
Starting Threads...

Press Ctrl+C to interrupt the execution

Produced: 1 -> deque([1])
Consumed: 1 -> deque([])
Queue is empty
Produced: 3 -> deque([3])
Produced: 0 -> deque([3, 0])
Consumed: 3 -> deque([0])
Consumed: 0 -> deque([])
Produced: 1 -> deque([1])
Produced: 0 -> deque([1, 0])
  ...


Поток-производитель добавляет числа в правый конец общего списка, в то время как поток-потребитель использует числа из левого конца. Чтобы прервать выполнение скрипта, вы можете нажать Ctrl+C на клавиатуре.
Наконец, вы можете немного поиграть с временным интервалом внутри produce() и consume(). Измените передаваемые значения на wait_seconds() и посмотрите, как ведет себя программа, когда производитель работает медленнее, чем потребитель, и наоборот.
Эмуляция команды tail
Последний пример, который вы закодируете здесь, эмулирует tail команду, которая доступна в Unix и Unix-подобные операционные системы. Команда принимает путь к файлу в командной строке и выводит последние десять строк этого файла в стандартный системный вывод. Вы можете настроить количество строк, которое вам нужно tail для печати, с помощью опции -n, --lines.
Вот небольшая функция Python, которая эмулирует основную функциональность tail:

>>> from collections import deque

>>> def tail(filename, lines=10):
...     try:
...         with open(filename) as file:
...             return deque(file, lines)
...     except OSError as error:
...         print(f'Opening file "{filename}" failed with error: {error}')
...


Здесь вы определяете tail(). Первый аргумент, filename, содержит путь к целевому файлу в виде строки. Второй аргумент, lines, представляет количество строк, которые вы хотите извлечь из конца целевого файла. Обратите внимание, что lines по умолчанию имеет значение 10 для имитации поведения по умолчанию tail.
 Примечание: Первоначальная идея для этого примера взята из документации по Python на deque. Ознакомьтесь с разделом, посвященным deque рецептам, для получения дополнительных примеров.
Значение deque в выделенной строке может содержать только то количество элементов, которое вы передаете в lines. Это гарантирует, что вы получите желаемое количество строк из конца входного файла.
Как вы видели ранее, когда вы создаете ограниченный deque и инициализируете его с помощью iterable, он содержит больше элементов, чем разрешено (maxlen), конструктор deque отбрасывает все крайние левые элементы во входных данных. Из-за этого вы в конечном итоге получаете последние maxlen строки целевого файла.
Заключение
 Очереди и стеки обычно используются абстрактные типы данных в программировании. Обычно для них требуются эффективные операции pop и append на обоих концах базовой структуры данных. Модуль Python collections предоставляет тип данных под названием deque, который специально разработан для быстрого и экономичного использования памяти операций добавления и извлечения данных с обеих сторон.
С помощью deque вы можете создавать свои собственные очереди и стеки на низком уровне элегантным, эффективным и основанным на Python способом.
 В этом руководстве вы узнали, как:

Создайте и используйте Python deque в своем коде
Эффективно добавлять и  извлекать элементов из обоих концов последовательности с помощью deque
Используйте deque для создания эффективных очередей и стеков в Python
Решите, когда использовать deque вместо list

В этом руководстве вы также написали несколько примеров, которые помогли вам приблизиться к некоторым распространенным вариантам использования deque в Python.
<статус завершения article-slug="python-deque" class="btn-group mb-0" data-api-article-bookmark-url="/api/v1/articles/python-deque/bookmark/" url статуса завершения data-api-article-url="/api/v1/articles/python-deque/завершение_статуса/">



<кнопка поделиться bluesky-text="Интересная статья на #Python от @realpython.com :" email-body="Ознакомьтесь с этой статьей о Python:%0A%0apython's deque: внедрение эффективных очередей и стеков" email-subject="Статья о Python для вас" twitter-text="Интересная статья #Python статья от @realpython:" url="https://realpython.com/python-deque /" url-title="Deque в Python: реализация эффективных очередей и стеков">


                







                 Back to Top