python: porównanie deque vs lista

Question

W dokumentach Pythona widzę, że Deque jest specjalną kolekcją wysoce zoptymalizowaną do wyskakiwania/dodawania przedmiotów z lewej lub prawej strony. Na przykład. Dokumentacja mówi:

Deques są uogólnieniem stosów i kolejek (nazwa wymawiane „deck” i jest skrótem od „double-ended kolejce”). Deques obsługuje wątek bezpieczny, obsługuje pamięć i wyskakuje ze strony , z mniej więcej taką samą wydajnością O (1) w kierunku .

Choć lista obiektów wspierać podobne operacje, są zoptymalizowane dla operacji szybko stałej długości i ponosić o koszty (n) ruch pamięć dla pop (0) i wkładki (0, v) operacji, które zmieniają zarówno wielkość i pozycja reprezentacji danych podstawowych.

Postanowiłem dokonać pewnych porównań przy użyciu ipython. Czy ktoś może wyjaśnić mi, co zrobiłem źle tutaj:

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 

Answer 1

co to jest warte:

> 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 

Jak widać, gdzie jest naprawdę błyszczy w appendleft vs insert.

Answer 2

Could anyone explain me what I did wrong here

Tak, timing jest zdominowany przez czas, aby utworzyć listę lub deque. Czas na wykonanie pop jest nieznaczny w porównaniu.

Zamiast tego należy odizolować rzeczą, którą próbujesz testu (prędkość pop) od chwili instalacji:

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 

Powiedział, że realne różnice między deques i wykazu w zakresie wydajności są:

• Deques mieć o (1), prędkość appendleft() i popleft() gdy wykazy mieć o (n) wydajność wkładki (0, wartość) i pop (0).

• Wydajność dołączania list jest trafiona, ponieważ używa pod maską realloc(). W efekcie ma on zbyt optymistyczny czas w prostym kodzie (ponieważ realloc nie musi przenosić danych) i naprawdę spowalnia czasy w kodzie rzeczywistym (ponieważ fragmentacja wymusza ponowne przesuwanie w celu przeniesienia wszystkich danych). W przeciwieństwie do tego, wydajność dodawania deque jest spójna, ponieważ nigdy się nie przenosi i nigdy nie przenosi danych.