Как реализованы deques в Python и когда они хуже списков?

85

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

Эли
источник

Ответы:

74

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

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

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

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

JAB
источник
3
Обратите внимание , что если вы просто нужно добавить и поп на одном конце (стек), списки должны работать лучше , как .append()и .pop()амортизируется в O (1) (перераспределение и копирование происходит, но очень редко и только до достижения макс. Размер стека будет когда-либо иметь).
@delnan: Но если вам нужна очередь, то что-то вроде deque- определенно правильный путь.
JAB
@delnan: Как ты себя представляешь? .append () и .pop () амортизируются O (1) для списков, но не являются фактическими O (1) для deques, и копии никогда не нужны.
Eli
1
@Eli: Списки не имеют отношения к потокобезопасности (ну, это не встроено в их внутреннее устройство), и многие умные люди их настраивали в течение долгого времени.
3
@delnan: На самом деле deques в CPython тоже не обрабатывают потокобезопасность; они просто извлекают выгоду из того, что GIL делает их операции атомарными (и на самом деле, appendи popс конца a listимеет такую ​​же защиту). На практике, если вы используете только стек, как listи dequeэффективно идентичную производительность в CPython; распределение блоков происходит чаще deque(но не простой связанный список; вы будете только выделять / освобождать каждый раз, когда вы пересекаете границу из 64 членов в реализации CPython), но отсутствие огромных прерывистых копий компенсирует.
ShadowRanger
51

Проверить collections.deque. Из документов:

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

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

Как и сказано, использование pop (0) или insert (0, v) влечет за собой большие штрафы для объектов списка. Вы не можете использовать операции среза / индекса в a 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
зикай
источник
3
Ха, только что заметил, что вы не можете выполнять нарезку с помощью дека, хотя вы можете выполнять индексацию. Интересно.
JAB
1
+1 за тайминги - интересно, что listдобавления немного быстрее, чем dequeдобавления.
senderle 06
1
@zeekay: Это довольно странно, учитывая, что поиск индекса определенного элемента обычно требует итерации по элементам коллекции в любом случае, и что вы можете индексировать его так dequeже, как и list.
JAB
1
@senderle: Конечно, list pops были медленнее, чем deques (вероятно, из-за listболее высокой стоимости периодического изменения размера по мере его сжатия, где dequeпросто освобождаются блоки обратно в свободный список или небольшой пул объектов), поэтому при выборе структуры данных для Для стека (также известного как очередь LIFO) производительность «пустой-полный-пустой» выглядит немного лучше deque(в среднем 6365K операций в секунду для append/ по popсравнению listс 5578K операций в секунду). Я подозреваю deque, что в реальном мире дела dequeобстоят немного лучше, поскольку свободный список означает, что рост в первый раз обходится дороже, чем рост после сокращения.
ShadowRanger
1
Чтобы прояснить мою ссылку на фрилист: CPython на dequeсамом деле не будет содержать freeдо 16 блоков (для всего модуля, а не для каждого deque), вместо этого помещая их в дешевый массив доступных блоков для повторного использования. Таким образом, при выращивании dequeв первый раз он всегда должен вытягивать новые блоки malloc(делая его appendболее дорогим), но если он постоянно немного расширяется, затем немного сжимается, и взад и вперед, он обычно не включает malloc/ freeв все до тех пор, пока длина остается примерно в диапазоне 1024 элементов (16 блоков в свободном списке, 64 слота на блок).
ShadowRanger
17

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

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

Но...

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

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

отправитель
источник
11

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

PythonJin
источник
-3

Хотя я не совсем уверен, как это реализовано в Python, здесь я написал реализацию очередей, используя только массивы. Он имеет ту же сложность, что и очереди Python.

class ArrayQueue:
""" Implements a queue data structure """

def __init__(self, capacity):
    """ Initialize the queue """

    self.data = [None] * capacity
    self.size = 0
    self.front = 0

def __len__(self):
    """ return the length of the queue """

    return self.size

def isEmpty(self):
    """ return True if the queue is Empty """

    return self.data == 0

def printQueue(self):
    """ Prints the queue """

    print self.data 

def first(self):
    """ Return the first element of the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    else:
        return self.data[0]

def enqueue(self, e):
    """ Enqueues the element e in the queue """

    if self.size == len(self.data):
        self.resize(2 * len(self.data))
    avail = (self.front + self.size) % len(self.data) 
    self.data[avail] = e
    self.size += 1

def resize(self, num):
    """ Resize the queue """

    old = self.data
    self.data = [None] * num
    walk = self.front
    for k in range(self.size):
        self.data[k] = old[walk]
        walk = (1+walk)%len(old)
    self.front = 0

def dequeue(self):
    """ Removes and returns an element from the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    answer = self.data[self.front]
    self.data[self.front] = None 
    self.front = (self.front + 1) % len(self.data)
    self.size -= 1
    return answer

class Empty(Exception):
""" Implements a new exception to be used when stacks are empty """

pass

И здесь вы можете протестировать это с помощью некоторого кода:

def main():
""" Tests the queue """ 

Q = ArrayQueue(5)
for i in range(10):
    Q.enqueue(i)
Q.printQueue()    
for i in range(10):
    Q.dequeue()
Q.printQueue()    


if __name__ == '__main__':
    main()

Он не будет работать так быстро, как реализация C, но использует ту же логику.

Реваншист
источник
1
Не изобретайте колесо!
Abhijit Sarkar
Вопрос заключался в том , как реализована двухсторонняя программа Python. Он не просил альтернативной реализации.
Gino Mempin