Сравнение производительности python: deque vs

В документах python я вижу, что deque - это специальная коллекция, оптимизированная для ввода/добавления элементов с левой или с правой стороны. Например. документация говорит:

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

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

Я решил сделать некоторые сравнения с помощью ipython. Может ли кто-нибудь объяснить мне, что я сделал неправильно здесь:

In [31]: %timeit range(1, 10000).pop(0)
 10000 loops, best of 3: 114 us per loop

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop

In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop

Ответ 1

Could anyone explain me what I did wrong here

Да, в вашем времени преобладает время создания списка или deque. Время, чтобы сделать поп, незначительно в сравнении.

Вместо этого вы должны изолировать то, что вы пытаетесь проверить (скорость поп-музыки) со времени установки:

In [1]: from collections import deque

In [2]: s = range(1000)

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

Тем не менее, реальные различия между deques и list в плане производительности:

У Deques есть O (1) скорость для appendleft() и popleft(), в то время как списки имеют O (n) производительность для вставки (0, значение) и pop (0).
Производительность списка append поражается и промахивается, потому что она использует realloc() под капотом. В результате он имеет тенденцию к чрезмерно оптимистичным таймингам в простом коде (потому что realloc не должен перемещать данные) и действительно медленные тайминги в реальном коде (поскольку фрагментация вынуждает realloc перемещать все данные). Напротив, производительность приложения deque совместима, поскольку она никогда не перераспределяет и никогда не перемещает данные.

Ответ 2

Для чего это стоит:

> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop

> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop

> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop

> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop

Как вы можете видеть, там, где он действительно сияет, находится в appendleft vs insert.

Ответ 3

Я бы порекомендовал вам обратиться https://wiki.python.org/moin/TimeComplexity

Списки Python и deque имеют схожую сложность для большинства операций (push, pop и т.д.)