Как использовать python deque?

[

Python’s deque: реализация эффективных очередей и стеков

Python Tricks Dictionary Merge

Если вы часто работаете с списками в Python, то, вероятно, знаете, что они не работают достаточно быстро, когда вам нужно удалять элементы и добавлять их в начало списка. Модуль collections в Python предоставляет класс под названием deque, который специально разработан для обеспечения быстрого и памяти-эффективного способа добавления и удаления элементов с обоих концов структуры данных.

deque в Python - низкоуровневый и высокооптимизированный двусторонний массив, который полезен для реализации элегантных, эффективных и питонических очередей и стеков - наиболее распространенных типов данных, похожих на список, в вычислительной технике.

В этом учебнике вы узнаете:

Как создать и использовать deque в вашем коде на Python
Как эффективно добавлять и удалять элементы с обоих концов deque
Как использовать deque для создания эффективных очередей и стеков
Когда стоит использовать deque вместо list

Для лучшего понимания этих тем вам следует знать основы работы со списками на Python. Также будет полезно иметь общее представление о очередях и стеках.

Наконец, вы напишете несколько примеров, которые помогут вам разобраться в некоторых общих случаях использования deque, который является одним из самых мощных типов данных в Python.

Начало работы с `deque` в Python

Добавление элементов и удаление их с правого конца списка в Python обычно являются эффективными операциями. Если использовать обозначение Большая О нотация для описания временной сложности, можно сказать, что их сложность - O(1). Однако, когда Python должен перераспределить память для увеличения размера списка для добавления новых элементов, эти операции могут замедлиться и стать O(n).

Кроме того, добавление и удаление элементов с левого конца списка в Python известно как неэффективные операции со скоростью O(n).

Поскольку списки на Python предоставляют обе эти операции с помощью .append() и .pop(), они могут быть использованы как стеки и очереди. Однако проблемы производительности, которые вы видели ранее, могут существенно повлиять на общую производительность ваших приложений.

deque в Python был первым типом данных, добавленным в модуль collections в Python 2.4.

Создание и использование `deque`

Чтобы использовать deque в Python, вам нужно импортировать его из модуля collections:

from collections import deque

После этого вы можете создать экземпляр deque, передав ему итерируемый объект:

mydeque = deque([1, 2, 3, 4])

Теперь у вас есть deque с элементами [1, 2, 3, 4].

Добавление и удаление элементов

Чтобы добавить элемент в deque справа, вы можете использовать метод .append():

mydeque.append(5)

Теперь у вас есть deque с элементами [1, 2, 3, 4, 5].

Чтобы добавить элемент в deque слева, вы можете использовать метод .appendleft():

mydeque.appendleft(0)

Теперь у вас есть deque с элементами [0, 1, 2, 3, 4, 5].

Чтобы удалить элемент справа из deque и вернуть его значение, вы можете использовать метод .pop():

value = mydeque.pop()
print(value)  # 5

Теперь у вас есть deque с элементами [0, 1, 2, 3, 4].

Чтобы удалить элемент слева из deque и вернуть его значение, вы можете использовать метод .popleft():

value = mydeque.popleft()
print(value)  # 0

Теперь у вас есть deque с элементами [1, 2, 3, 4].

Доступ к элементам

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

value = mydeque[0]
print(value)  # 1

value = mydeque[-1]
print(value)  # 4

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

subdeque = mydeque[1:3]
print(subdeque)  # deque([2, 3])

Построение эффективных очередей с помощью `deque`

deque в Python особенно полезен при создании эффективных очередей. Вы можете использовать его для реализации FIFO (First-In, First-Out) или LIFO (Last-In, First-Out) поведения.

FIFO очередь

queue = deque()

# добавление элементов в очередь
queue.append(1)
queue.append(2)
queue.append(3)

# удаление элементов из очереди
value = queue.popleft()
print(value)  # 1

value = queue.popleft()
print(value)  # 2

value = queue.popleft()
print(value)  # 3

LIFO стек

stack = deque()

# добавление элементов в стек
stack.append(1)
stack.append(2)
stack.append(3)

# удаление элементов из стека
value = stack.pop()
print(value)  # 3

value = stack.pop()
print(value)  # 2

value = stack.pop()
print(value)  # 1

Заметка: для очереди и стека внутри deque можно использовать только методы .append() и .popleft() или .append() и .pop(), соответственно. Вы не должны использовать .appendleft() или .popleft() для стека и .append() или .pop() для очереди.

Обнаружение других возможностей `deque`

deque в Python предлагает еще несколько полезных функций, которые могут быть применены в различных ситуациях.

Ограничение максимального количества элементов: `maxlen`

Вы можете ограничить максимальное количество элементов в deque, указав параметр maxlen при его создании:

mydeque = deque(maxlen=3)

Теперь у вас есть deque, который может хранить не более 3 элементов. Если вы добавите больше элементов, самый старый элемент будет удален из deque:

mydeque.append(1)
mydeque.append(2)
mydeque.append(3)
print(mydeque)  # deque([1, 2, 3])

mydeque.append(4)
print(mydeque)  # deque([2, 3, 4])

Поворот элементов: `.rotate()`

Вы можете повернуть элементы в deque вправо или влево с помощью метода .rotate():

mydeque = deque([1, 2, 3, 4, 5])
mydeque.rotate(2)
print(mydeque)  # deque([4, 5, 1, 2, 3])

mydeque.rotate(-1)
print(mydeque)  # deque([5, 1, 2, 3, 4])

Добавление нескольких элементов одновременно: `.extendleft()`

Метод .extendleft() позволяет добавить несколько элементов в deque слева:

mydeque = deque([2, 3, 4])
mydeque.extendleft([1, 0])
print(mydeque)  # deque([0, 1, 2, 3, 4])

Использование функций, подобных спискам, в `deque`

Благодаря гибкости deque в Python, вы можете использовать его с функциями, подобными спискам.

`len()` и `in`

mydeque = deque([1, 2, 3])
print(len(mydeque))  # 3

print(2 in mydeque)  # True
print(4 in mydeque)  # False

Использование срезов

mydeque = deque([0, 1, 2, 3, 4, 5])
subdeque = mydeque[1:4]
print(subdeque)  # deque([1, 2, 3])

Преобразование в `list`

mydeque = deque([1, 2, 3])
mylist = list(mydeque)
print(mylist)  # [1, 2, 3]

Применение `deque` в Python

Теперь рассмотрим несколько распространенных сценариев использования deque, чтобы увидеть, как он может быть полезен в реальных проектах.

Сохранение истории страниц

Очередь deque в Python может быть полезна для хранения истории просматриваемых страниц веб-сайта. Вы можете добавлять новые страницы в конец deque и удалять старые страницы при достижении определенного размера:

from collections import deque

MAX_PAGE_HISTORY = 5

page_history = deque(maxlen=MAX_PAGE_HISTORY)

def visit_page(page):
    page_history.append(page)
    # остальная логика обработки посещения страницы

def display_page_history():
    for page in page_history:
        print(page)

visit_page('home')
visit_page('about')
visit_page('contact')
visit_page('products')
visit_page('faq')
visit_page('login')

display_page_history()

Обмен данными между потоками

Если у вас есть множество потоков, которые должны обмениваться данными, deque может быть полезным инструментом. Вы можете использовать один deque в качестве буфера данных для потоков, добавляя данные в одном потоке и извлекая их в другом:

from collections import deque
import threading

data_buffer = deque()

def producer():
    for i in range(10):
        data_buffer.append(i)
        # остальная логика производителя

def consumer():
    while True:
        if len(data_buffer) > 0:
            data = data_buffer.popleft()
            # остальная логика потребителя

producer_thread = threading.Thread(target=producer)
consumer_thread = threading.Thread(target=consumer)

producer_thread.start()
consumer_thread.start()

Эмуляция команды “tail”

deque также может быть использован для эмуляции команды tail в Unix. Вы можете организовать deque в виде кольцевого буфера, который содержит последние N строк в файле:

from collections import deque

def tail(filepath, n):
    with open(filepath, 'r') as f:
        # создаем кольцевый буфер
        history = deque(maxlen=n)

        # читаем файл и добавляем каждую строку в буфер
        for line in f:
            history.append(line)

        # выводим строки из буфера
        for line in history:
            print(line, end='')

tail('log.txt', 10)

Заключение

deque в Python - это мощный и эффективный инструмент для работы с очередями и стеками. Он предлагает удобные методы для добавления, удаления и доступа к элементам с обоих концов. Кроме того, deque имеет дополнительные функции, такие как ограничение максимального количества элементов, поворот элементов и добавление нескольких элементов одновременно. Он также обладает функциональностью, подобной спискам, что делает его удобным для использования с другими функциями Python.

Если вам нужно реализовать эффективные очереди и стеки, рассмотрите использование deque вместо обычных списков. Это позволит улучшить производительность и упростить ваш код.

Как использовать python deque?

Python’s deque: реализация эффективных очередей и стеков

Начало работы с deque в Python

Создание и использование deque

Добавление и удаление элементов

Доступ к элементам

Построение эффективных очередей с помощью deque

FIFO очередь

LIFO стек

Обнаружение других возможностей deque

Ограничение максимального количества элементов: maxlen

Поворот элементов: .rotate()

Добавление нескольких элементов одновременно: .extendleft()

Использование функций, подобных спискам, в deque

len() и in