Efektywność korzystania z listy Pythona jako kolejki

Question

Współpracownik napisał niedawno program, w którym użył listy w Pythonie jako kolejki. Innymi słowy, użył .append(x), gdy potrzebował wstawić przedmioty i .pop(0), gdy trzeba było usunąć przedmioty.

Wiem, że Python ma collections.deque i staram się dowiedzieć, czy spędzić mój (ograniczony) czas na przepisanie tego kodu, aby go użyć. Zakładając, że wykonujemy miliony załączeń i popów, ale nigdy nie będzie ich więcej niż kilka tysięcy, czy użycie listy będzie stanowić problem?

W szczególności, czy podstawowa tablica używana przez implementację listy w języku Python będzie nadal rosnąć w nieskończoność, mając miliony punktów, mimo że lista zawiera tylko tysiąc rzeczy, czy też Python ostatecznie wykona numer realloc i zwolni część tej pamięci?

Answer 1

Nie zabraknie pamięci przy użyciu implementacji list, ale wydajność będzie niska. Od the docs:

Choć list obiekty podobne podparcie operacje, są zoptymalizowane dla szybkich operacji stałej długości i ponosić koszty O (n) ruchu pamięć pop(0) i insert(0, v) operacji które zmieniają zarówno wielkość i pozycja reprezentujących dane reprezentacji .

Używanie numeru deque będzie więc znacznie szybsze.

Answer 2

Brzmi to jak odrobina badań empirycznych może być najlepszą rzeczą do zrobienia w tym miejscu - problemy drugiego rzędu mogą sprawić, że jedno podejście będzie lepsze w praktyce, nawet jeśli nie jest ono lepsze w teorii.

Answer 3

Każdy krok .pop(0) wykonuje N kroków, ponieważ lista musi zostać zreorganizowana. Wymagana pamięć nie będzie rosła w nieskończoność i będzie tylko tak duża, jak wymaga tego przechowywany przedmiot.

Polecam użycie deque, aby uzyskać O (1) dołączyć i pop od przodu.

Answer 4

Niektóre odpowiedzi twierdził „10x” przewagę prędkości dla deque vs lista używane-as-FIFO, gdy oba mają 1000 wpisów, ale to trochę w przelicytować:

$ python -mtimeit -s'q=range(1000)' 'q.append(23); q.pop(0)' 
1000000 loops, best of 3: 1.24 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(1000))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.573 usec per loop 

python -mtimeit jest twoim przyjacielem - naprawdę użyteczne i proste podejście do mikro-benchmarkingu! Dzięki niemu można też oczywiście trywialnie zbadać skuteczność w wielce mniejszych przypadkach:

$ python -mtimeit -s'q=range(100)' 'q.append(23); q.pop(0)' 
1000000 loops, best of 3: 0.972 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(100))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.576 usec per loop 

(nie bardzo różni się za 12 zamiast 100 pozycji BTW), w wielce większych:

$ python -mtimeit -s'q=range(10000)' 'q.append(23); q.pop(0)' 
100000 loops, best of 3: 5.81 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(10000))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.574 usec per loop 

Widać, że twierdzenie o skuteczności O (1) dla deque jest uzasadnione, podczas gdy lista jest ponad dwukrotnie wolniejsza od 1000 elementów, rzędu wielkości około 10 000. Możesz także zauważyć, że nawet w takich przypadkach tracisz tylko 5 mikrosekund na parę append/pop i decydujesz, jak duże są te straty (choć jeśli to wszystko, co robisz z tym kontenerem, deque nie ma wad, więc równie dobrze może się zmienić, nawet jeśli 5 usec więcej lub mniej nie spowoduje istotnej różnicy).

Answer 5

Z Beazley's Python Essential Reference, Fourth Edition, str. 194:

Niektóre moduły biblioteczne dostarczyć nowe typy że przewyższają Zabudowy na pewnych zadań. Na przykład: collections.deque type zapewnia podobną funkcjonalność do listy, ale została wysoce zoptymalizowana pod kątem wstawiania elementów na obu końcach w postaci . Z kolei lista jest tylko wydajna podczas dołączania elementów na końcu. Jeśli wstawiasz elementy z przodu, wszystkie elementy muszą być przesunięte o , aby zrobić miejsce. Wymagany czas to , ponieważ lista staje się coraz większa. Wystarczy dać wyobrażenie o różnicy, tutaj jest miarą czas wkładając jeden milion pozycji z przodu listy i deque:

I następuje ten przykładowy kod:

>>> from timeit import timeit 
>>> timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=1000000) 
0.13162776274638258 
>>> timeit('s.insert(0,37)', 's = []', number=1000000) 
932.07849908298408 

Czasy są z mojego komputera.

---

2012-07-01 Aktualizacja

>>> from timeit import timeit 
>>> n = 1024 * 1024 
>>> while n > 1: 
...  print '-' * 30, n 
...  timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=n) 
...  timeit('s.insert(0,37)', 's = []', number=n) 
...  n >>= 1 
... 
------------------------------ 1048576 
0.1239769458770752 
799.2552740573883 
------------------------------ 524288 
0.06924104690551758 
148.9747350215912 
------------------------------ 262144 
0.029170989990234375 
35.077512979507446 
------------------------------ 131072 
0.013737916946411133 
9.134140014648438 
------------------------------ 65536 
0.006711006164550781 
1.8818109035491943 
------------------------------ 32768 
0.00327301025390625 
0.48307204246520996 
------------------------------ 16384 
0.0016388893127441406 
0.11021995544433594 
------------------------------ 8192 
0.0008249282836914062 
0.028419017791748047 
------------------------------ 4096 
0.00044918060302734375 
0.00740504264831543 
------------------------------ 2048 
0.00021195411682128906 
0.0021741390228271484 
------------------------------ 1024 
0.00011205673217773438 
0.0006101131439208984 
------------------------------ 512 
6.198883056640625e-05 
0.00021386146545410156 
------------------------------ 256 
2.9087066650390625e-05 
8.797645568847656e-05 
------------------------------ 128 
1.5974044799804688e-05 
3.600120544433594e-05 
------------------------------ 64 
8.821487426757812e-06 
1.9073486328125e-05 
------------------------------ 32 
5.0067901611328125e-06 
1.0013580322265625e-05 
------------------------------ 16 
3.0994415283203125e-06 
5.9604644775390625e-06 
------------------------------ 8 
3.0994415283203125e-06 
5.0067901611328125e-06 
------------------------------ 4 
3.0994415283203125e-06 
4.0531158447265625e-06 
------------------------------ 2 
2.1457672119140625e-06 
2.86102294921875e-06