Блог

Недавно я занялся исследованием того, как различные структуры данных реализованы в Python, чтобы сделать мой код более эффективным. Исследуя, как работают списки и deques, я обнаружил, что могу получить преимущества, когда хочу сдвигать и отменять смещение, сокращая время с O (n) в списках до O (1) в deques (списки реализуются в виде массивов фиксированной длины, которые приходится полностью копировать каждый раз, когда что-то вставляется спереди, и т.д.). Чего я, похоже, не могу найти, так это специфики реализации deque и специфики его недостатков в списках. Может кто-нибудь просветить меня по этим двум вопросам?

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

A dequeobject состоит из двусвязного списка block узлов.

Итак, deque это (дважды) связанный список, как предполагает другой ответ.

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

Ознакомьтесь collections.deque . Из документов:

Deques поддерживают потокобезопасные, экономящие память добавления и всплывающие окна с любой стороны deque с примерно одинаковой производительностью O (1) в любом направлении.

Хотя объекты списка поддерживают аналогичные операции, они оптимизированы для быстрых операций с фиксированной длиной и требуют затрат на перемещение памяти O (n) для операций pop (0) и insert (0, v), которые изменяют как размер, так и положение базового представления данных.

Как и сказано, использование pop (0) или insert (0, v) влечет за собой большие штрафы для объектов списка. Вы не можете использовать операции срезания / индексирования на deque , но вы можете использовать popleft / appendleft , для которых эти операции deque оптимизированы. Вот простой тест, демонстрирующий это:

 import time
from collections import deque

num = 100000

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)
  

Результаты на моей машине:

 Completed deque/append in 0.02 seconds: 5582877.2 ops/sec
Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec
Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec
Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec
Completed list/append in 0.01 seconds: 6761407.6 ops/sec
Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec
Completed list/pop in 0.02 seconds: 4394057.9 ops/sec
Completed list/popleft in 3.23 seconds: 30983.3 ops/sec
  

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

Deques поддерживают потокобезопасные, экономящие память добавления и всплывающие окна с обеих сторон deque с примерно одинаковой производительностью O (1) в любом направлении.

Но…

Индексированный доступ равен O (1) на обоих концах, но замедляется до O (n) в середине. Для быстрого произвольного доступа вместо этого используйте списки.

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

В дополнение ко всем другим полезным ответам, здесь приведена дополнительная информация, сравнивающая временную сложность (Big-Oh) различных операций над списками Python, deques, наборами и словарями. Это должно помочь в выборе правильной структуры данных для конкретной проблемы.