Библиотека Python разработчика | Книги по питону: “Иногда в программе нужна очередь — контейнер, куда элементы добавляютс…”

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


In : lst = [1, 2, 3]
In : lst.pop()
Out: 3
In : lst
Out: [1, 2]
In : lst[:0] = [4]  # push
In : lst
Out: [4, 1, 2]

Однако list выглядит не очень удобно (взгляните на этот "push") и работает неэффективно.


In : lst = [0] * 10_000_000

In : %timeit lst[:0] = [1]
9.5 ms ± 111 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In : %timeit lst.pop()
84.3 ns ± 4.01 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Как видно, операция pop() в 100 раз быстрее, чем вставка в начало списка. Это связано с тем, как устроен list в Python: легко добавлять и удалять элементы с конца, но удаление/добавление в начало требует создания нового списка.

Для очередей лучше использовать collections.deque. Он специально для этого создан:


In : from collections import deque
In : d = deque([1] * 100_000_000)
In : %timeit d.popleft()
65 ns ± 0.436 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

📲 Мы в MAX

👉@BookPython