На этом шаге мы рассмотрим использование collections.deque для решения этой задачи.

Задача

    Вы хотите хранить ограниченную историю из нескольких последних элементов, полученных в ходе итерации или какого-то другого процесса обработки данных.

Решение

    Задача хранения ограниченной истории - отличный повод применить collections.deque. Например, следующий фрагмент кода производит простое сопоставление текста с последовательностью строк, а при совпадении выдает совпавшие строки вместе с N предыдущими строками контекста:

from collections import deque


def search(lines, pattern, history=5):
    previous_lines = deque(maxlen=history)
    for line in lines:
        if pattern in line:
            yield line, previous_lines
        previous_lines.append(line)


# Пример использования
if __name__ == '__main__':
    with open('somefile.txt') as f:
        for line, prevlines in search(f, 'python', 5):
            for pline in prevlines:
                print(pline, end='')
            print(line, end='')
            print('-' * 20)

Обсуждение

    При написании программы для поиска элементов обычно используют функцию-генератор, содержащую yield (как и показано в вышеприведенном примере). Это отделяет процесс поиска от кода, который использует результаты.

    Использование deque(maxlen=N) создает очередь фиксированной длины. Когда новые элементы добавлены и очередь заполнена, самый старый элемент автоматически удаляется. Пример:

>>> q = deque(maxlen=3)
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3], maxlen=3)
>>> q.append(4)
>>> q
deque([2, 3, 4], maxlen=3)
>>> q.append(5)
>>> q
deque([3, 4, 5], maxlen=3)

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

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

>>> q = deque()
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3])
>>> q.appendleft(4)
>>> q
deque([4, 1, 2, 3]) 
>>> q.pop()
3
>>> q
deque([4, 1, 2])
>>> q.popleft()
4
>>> q
deque([1, 2])
>>>  

    Добавление или удаление элементов в любой из концов очереди имеет сложность O(1). А вот вставка или удаление элемента в начале списка имеет сложность O(N).

    На следующем шаге мы рассмотрим поиск N максимальных и минимальных элементов.

Предыдущий шаг Содержание Следующий шаг