Преимущества двухсторонней очереди collections.deque() над списком

Опубликован: 27.01.2024 62

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

Двусторонняя очередь deque() модуля collections является усовершенствованным типом списка, поддерживающим поточно-ориентированные и оптимизированные по скорости и памяти добавления и извлечения элементов с любой стороны списка.

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

Синтаксис: collections.deque([iterable [, maxlen]])

• iterable – итерируемая последовательность (список, кортеж и т.п.);
• maxlen – максимальное количество хранимых элементов в объекте deque().

Если аргумент maxlen не указан или равен None, количество хранимых записей в объекте deque() может увеличиваться до произвольной длины. При добавлении новых элементов, когда заполнение объекта deque() становится больше значения maxlen, избыточное количество элементов удаляется с противоположного конца контейнера.

Основные преимущеста deque() перед списком:

• возможность быстрой и эффективной по памяти O(1) вставки элементов в начало списка;
• фиксация максимальной длины списка свойством Deque.maxlen();
• организация вращения элементов контейнера на n шагов вправо или влево с помощью свойства Deque.rotate().

from collections import deque

dq = deque(range(10))    # создание объекта deque()
for num in dq:
    print(num, end=' ')
0 1 2 3 4 5 6 7 8 9

dq.append('десять')     # добавление элемента в конец объекта deque()
print(dq)
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'десять'])

dq.appendleft('минус один')    # добавление элемента в начало объекта deque()
print(dq)
deque(['минус один', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'десять'])

dq.rotate(1)    # смещение элементов объекта deque() на 1 шаг вправо
print(dq)
deque(['десять', 'минус один', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

dq.rotate(-1)    # смещение элементов объекта deque() на 1 шаг влево
print(dq)
deque(['минус один', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'десять'])

Особенности объекта deque(), о которых следует помнить:

• deque() изменяемая структура данных;
• deque() может хранить несколько типов данных, например, целые числа, кортежи, массивы и т.д.;
• deque() поддерживает индексацию, но не поддерживает операции нарезки;
• deque() не поддерживает сортировку на месте;
• deque() поддерживает общие встроенные функции и операции ( in, sorted(), len(), reverse() и т.д.).

Примеры использования объекта deque().

Получение последних n строк файла с использованием свойства Deque.maxlen():

from collections import deque

def get_last_strings(filename, n=10):
    "Возвращает последние 'n' строк файла"
    with open(filename, 'r') as f:
        return deque(f, n)

get_last_strings('test.csv', n=5)

Объект deque() можно также использовать для вычислений "скользящего среднего" при анализе временных рядов данных, что позволяет сглаживать краткосрочные колебания временных рядов.

from collections import deque
import itertools

def moving_average(iterable, n=3):
    "moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0"
    it = iter(iterable)
    d = deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s/n

gen = moving_average([40, 30, 50, 46, 39, 44])
print(next(gen))
40.0
print(next(gen))
42.0
print(next(gen))
45.0
print(next(gen))
43.0

В приведенном примере создается функция - генератор moving_average() для вычисления скользящего среднего временного ряда числовых значений со скользящим окном n = 3. Затем в генератор передается список числовых значений [40, 30, 50, 46, 39, 44], который возвращает последовательно результат вычисления скользящего среднего трех значений списка 40.0 42.0 45.0 43.0.

Очередь (FIFO).

Еще одним примером использования deque() может быть эффективная реализация структуры данных по принципу очереди (FIFO): "первый вошел - первый вышел".

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

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
1 
print(queue) 
deque([2, 3])

# для проверки наличия элементов в очереди используется оператор not
if not queue: 
   print("Очередь пуста") 
else: 
   print("Очередь не пустая")  

Стек (LIFO).

Как и очереди, стеки являются еще одним примером эффективного использования структуры данных deque(). В отличие от очередей, стеки работают по принципу (LIFO): "последний вошел - первый вышел".

Для использования deque() в качестве стека можно добавлять элементы в стек с помощью метода append(), а удалять элементы из стека с помощью метода pop(). Таким образом, последний элемент в стеке будет первым элементом на выходе.

from collections import deque

my_stack = deque()     # создание стека
my_stack.append(5)    # добавление в стек значения 5
my_stack.append(2)    # добавление в стек значения 2

x = my_stack.pop()    # извлечение из стека значения 2
print(x)
2
y = my_stack.pop()    # извлечение из стека значения 5
print(y)
5
x * y
10

Похожие посты

Использование collections.namedtuple() для создания неизменяемого словаря

Преимущества использования словаря collections.defaultdict()

Количество одинаковых элементов в списке (кортеже) или строке

Методы преобразования списка в строку и обратно

Комментариев нет.