deque.popleft() i list.pop (0). Czy jest różnica w wydajności?

Question

deque.popleft() i list.pop(0) wydają się zwracać ten sam wynik. Czy istnieje między nimi różnica w wydajności i dlaczego?

Answer 1

deque.popleft() jest szybszy niż list.pop (0), ponieważ deque został zoptymalizowany do wykonania popleft() w przybliżeniu w O (1), podczas gdy list.pop (0) pobiera O (n) (patrz deque objects).

Komentarze i kod w _collectionsmodule.c dla deque i listobject.c dla listy zawierają informacje na temat implementacji, aby wyjaśnić różnice w wydajności. Mianowicie, że obiekt deque "składa się z podwójnie połączonej listy", która efektywnie optymalizuje dodatki i wyskakuje na obu końcach, podczas gdy obiekty listy nie są nawet pojedynczymi połączonymi listami, ale tablicami C (wskaźników do elementów (patrz Python 2.7 listobject.h#l22 i Python 3.5 listobject.h#l23) , co czyni je przydatnymi do szybkiego losowego dostępu elementów, ale wymaga czasu (n) na przesunięcie wszystkich elementów po usunięciu pierwszego.

Dla Pythona 2.7 i 3.5, adresy URL tych plików kodu źródłowego są:

1. https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c

2. https://hg.python.org/cpython/file/2.7/Objects/listobject.c

3. https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

4. https://hg.python.org/cpython/file/3.5/Objects/listobject.c

Używanie% timeit, różnica w wydajności między deque.popleft() i list.pop (0) wynosi około 4, gdy zarówno deque i lista mają te same 52 elementy i rosną do ponad 1000 razy, gdy ich długości to 10 ** 8. Wyniki testu podano poniżej.

import string 
from collections import deque 

%timeit d = deque(string.letters); d.popleft() 
1000000 loops, best of 3: 1.46 µs per loop 

%timeit d = deque(string.letters) 
1000000 loops, best of 3: 1.4 µs per loop 

%timeit l = list(string.letters); l.pop(0) 
1000000 loops, best of 3: 1.47 µs per loop 

%timeit l = list(string.letters); 
1000000 loops, best of 3: 1.22 µs per loop 

d = deque(range(100000000)) 

%timeit d.popleft() 
10000000 loops, best of 3: 90.5 ns per loop 

l = range(100000000) 

%timeit l.pop(0) 
10 loops, best of 3: 93.4 ms per loop 

Answer 2

Tak, a to znaczące, jeśli masz długą listę lub deque. Wszystkie elementy na liście są umieszczane w pamięci, dlatego jeśli usuniesz dowolny element, wszystkie kolejne elementy muszą zostać przesunięte o jedną pozycję w lewo - dlatego czas wymagany do usunięcia lub wstawienia elementu na początku listy jest proporcjonalny do długość listy. Z drugiej strony, deque jest specjalnie skonstruowany, aby umożliwić szybkie wstawianie lub usuwanie przy końcu (zwykle przez umożliwienie "pustych" miejsc pamięci na początku zakleszczenia, lub zawinięcie wokół, tak aby koniec segmentu pamięci zajmowane przez kapłankę mogą zawierać elementy, które faktycznie są uważane za znajdujące się na początku deque).

porównać skuteczność tych dwóch fragmentów:

d = deque([0] * 1000000) 
while d: 
    d.popleft() 
    if len(d) % 100 == 0: 
     print(len(d)) 

lst = [0] * 1000000 
while lst: 
    lst.pop(0) 
    if len(lst) % 100 == 0: 
     print(len(lst)) 

Answer 3

Czy istnieje różnica wydajności?

Tak. deque.popleft() jest O(1) - stała operacja czasowa. Podczas gdy list.pop(0) jest O(n) - liniowa operacja czasu: im większa lista, tym dłużej trwa.

Dlaczego?

Implementacja listy CPython opiera się na tablicach. pop(0) usuwa pierwszy element z listy i wymaga przesunięcia w lewo elementów len(lst) - 1, aby wypełnić lukę.

Wdrożenie wykorzystuje podwójnie połączoną listę. Bez względu na to, jak duża jest deque, deque.popleft() wymaga stałej (ograniczonej powyżej) liczby operacji.