Недавно я начал исследовать, как различные структуры данных реализованы в Python, чтобы сделать мой код более эффективным. Изучая, как работают списки и двухсторонние очереди, я обнаружил, что могу получить преимущества, когда хочу сдвигать и отменять сдвиг, сокращая время от O (n) в списках до O (1) в двухсторонних (списки, реализованные как массивы фиксированной длины, которые имеют копироваться полностью каждый раз, когда что-то вставляется спереди и т. д.). То, что я не могу найти, - это особенности реализации двухсторонней очереди и особенности ее недостатков по сравнению со списками. Может ли кто-нибудь просветить меня по этим двум вопросам?
85
.append()
и.pop()
амортизируется в O (1) (перераспределение и копирование происходит, но очень редко и только до достижения макс. Размер стека будет когда-либо иметь).deque
- определенно правильный путь.deque
s в CPython тоже не обрабатывают потокобезопасность; они просто извлекают выгоду из того, что GIL делает их операции атомарными (и на самом деле,append
иpop
с конца alist
имеет такую же защиту). На практике, если вы используете только стек, какlist
иdeque
эффективно идентичную производительность в CPython; распределение блоков происходит чащеdeque
(но не простой связанный список; вы будете только выделять / освобождать каждый раз, когда вы пересекаете границу из 64 членов в реализации CPython), но отсутствие огромных прерывистых копий компенсирует.Проверить
collections.deque
. Из документов:Как и сказано, использование 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
источник
list
добавления немного быстрее, чемdeque
добавления.deque
же, как иlist
.list
pop
s были медленнее, чемdeque
s (вероятно, из-заlist
более высокой стоимости периодического изменения размера по мере его сжатия, гдеdeque
просто освобождаются блоки обратно в свободный список или небольшой пул объектов), поэтому при выборе структуры данных для Для стека (также известного как очередь LIFO) производительность «пустой-полный-пустой» выглядит немного лучшеdeque
(в среднем 6365K операций в секунду дляappend
/ поpop
сравнениюlist
с 5578K операций в секунду). Я подозреваюdeque
, что в реальном мире делаdeque
обстоят немного лучше, поскольку свободный список означает, что рост в первый раз обходится дороже, чем рост после сокращения.deque
самом деле не будет содержатьfree
до 16 блоков (для всего модуля, а не для каждогоdeque
), вместо этого помещая их в дешевый массив доступных блоков для повторного использования. Таким образом, при выращиванииdeque
в первый раз он всегда должен вытягивать новые блокиmalloc
(делая егоappend
более дорогим), но если он постоянно немного расширяется, затем немного сжимается, и взад и вперед, он обычно не включаетmalloc
/free
в все до тех пор, пока длина остается примерно в диапазоне 1024 элементов (16 блоков в свободном списке, 64 слота на блок).Я подозреваю, что запись в документации по
deque
объектам содержит большую часть того, что вам нужно знать. Известные цитаты:Но...
Мне пришлось бы взглянуть на источник, чтобы определить, является ли реализация связанным списком или чем-то еще, но мне кажется, что a
deque
имеет примерно те же характеристики, что и двусвязный список.источник
В дополнение ко всем другим полезным ответам, вот еще некоторая информация, сравнивающая временную сложность (Big-Oh) различных операций со списками, деками, наборами и словарями Python. Это должно помочь в выборе правильной структуры данных для конкретной проблемы.
источник
Хотя я не совсем уверен, как это реализовано в 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, но использует ту же логику.
источник