list () wykorzystuje nieco więcej pamięci niż rozumienie list

79

Więc bawiłem się listobiektami i znalazłem małą dziwną rzecz, która jeśli listzostanie utworzona za pomocą list()tego, zużywa więcej pamięci niż rozumienie listy? Używam Pythona 3.5.2

In [1]: import sys
In [2]: a = list(range(100))
In [3]: sys.getsizeof(a)
Out[3]: 1008
In [4]: b = [i for i in range(100)]
In [5]: sys.getsizeof(b)
Out[5]: 912
In [6]: type(a) == type(b)
Out[6]: True
In [7]: a == b
Out[7]: True
In [8]: sys.getsizeof(list(b))
Out[8]: 1008

Z dokumentów :

Listy można konstruować na kilka sposobów:

  • Użycie pary nawiasów kwadratowych do oznaczenia pustej listy: []
  • Używanie nawiasów kwadratowych, oddzielając elementy przecinkami: [a],[a, b, c]
  • Korzystanie ze zrozumienia list: [x for x in iterable]
  • Korzystanie z konstruktora typu: list()lublist(iterable)

Ale wydaje się, że używanie list()go zużywa więcej pamięci.

Im więcej listjest większe, tym różnica rośnie.

Różnica w pamięci

Dlaczego tak się dzieje?

AKTUALIZACJA # 1

Przetestuj z Pythonem 3.6.0b2:

Python 3.6.0b2 (default, Oct 11 2016, 11:52:53) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(range(100)))
1008
>>> sys.getsizeof([i for i in range(100)])
912

AKTUALIZACJA # 2

Przetestuj z Pythonem 2.7.12:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(xrange(100)))
1016
>>> sys.getsizeof([i for i in xrange(100)])
920
vishes_shell
źródło
3
To bardzo interesujące pytanie. Potrafię odtworzyć to zjawisko w Pythonie 3.4.3. Jeszcze bardziej interesujące: w Pythonie 2.7.5 sys.getsizeof(list(range(100)))to 1016, getsizeof(range(100))to 872 i getsizeof([i for i in range(100)])to 920. Wszystkie mają ten typ list.
Sven Festersen
Interesujące jest to, że ta różnica występuje również w Pythonie 2.7.10 (chociaż rzeczywiste liczby są inne niż w Pythonie 3). Również tam w 3.5 i 3.6b.
cdarke
Otrzymuję te same liczby dla Pythona 2.7.6 co @SvenFestersen, również podczas używania xrange.
RemcoGerlich
2
Możliwe wyjaśnienie tutaj: stackoverflow.com/questions/7247298/size-of-list-in-memory . Jeśli jedna z metod tworzy listę przy użyciu append(), może wystąpić nadmierna alokacja pamięci. Myślę, że jedynym sposobem, aby naprawdę to wyjaśnić, jest przyjrzenie się źródłom Pythona.
Sven Festersen
Tylko 10% więcej (tak naprawdę nigdzie tego nie mówisz). Przeformułowałbym tytuł na „nieco więcej”.
smci

Odpowiedzi:

61

Myślę, że widzisz wzorce nadmiernej alokacji. Oto przykład ze źródła :


Po wydrukowaniu rozmiarów składów list o długościach 0-88 możesz zobaczyć dopasowania wzorców:

# create comprehensions for sizes 0-88
comprehensions = [sys.getsizeof([1 for _ in range(l)]) for l in range(90)]

# only take those that resulted in growth compared to previous length
steps = zip(comprehensions, comprehensions[1:])
growths = [x for x in list(enumerate(steps)) if x[1][0] != x[1][1]]

# print the results:
for growth in growths:
    print(growth)

Wyniki (format to (list length, (old total size, new total size))):

(0, (64, 96)) 
(4, (96, 128))
(8, (128, 192))
(16, (192, 264))
(25, (264, 344))
(35, (344, 432))
(46, (432, 528))
(58, (528, 640))
(72, (640, 768))
(88, (768, 912))

Nadmierna alokacja jest wykonywana ze względu na wydajność, co pozwala listom rosnąć bez przydzielania większej ilości pamięci przy każdym wzroście (lepsza amortyzowana wydajność).

Prawdopodobnym powodem różnicy w używaniu funkcji rozumienia list jest to, że funkcja rozumienia list nie może deterministycznie obliczyć rozmiaru wygenerowanej listy, ale list()może. Oznacza to, że rozumienie będzie stale powiększać listę w miarę jej wypełniania z nadmierną alokacją, aż w końcu ją zapełni.

Jest możliwe, że po jego zakończeniu bufor nadmiernej alokacji nie zwiększy się o nieużywane przydzielone węzły (w rzeczywistości w większości przypadków nie spowoduje to przekroczenia celu nadmiernej alokacji).

list()jednak może dodać trochę bufora bez względu na rozmiar listy, ponieważ zna z wyprzedzeniem ostateczny rozmiar listy.


Innym potwierdzającym dowodem, również ze źródła, jest to, że widzimy wywoływanie wyrażeń listowychLIST_APPEND , co wskazuje na użycie list.resize, co z kolei wskazuje na zużycie buforu wstępnej alokacji bez wiedzy, jaka część zostanie zapełniona. Jest to zgodne z zachowaniem, które widzisz.


Podsumowując, list()wstępnie przydzieli więcej węzłów w zależności od rozmiaru listy

>>> sys.getsizeof(list([1,2,3]))
60
>>> sys.getsizeof(list([1,2,3,4]))
64

Funkcja rozumienia listy nie zna rozmiaru listy, więc używa operacji dołączania w miarę jej powiększania, co wyczerpuje bufor wstępnej alokacji:

# one item before filling pre-allocation buffer completely
>>> sys.getsizeof([i for i in [1,2,3]]) 
52
# fills pre-allocation buffer completely
# note that size did not change, we still have buffered unused nodes
>>> sys.getsizeof([i for i in [1,2,3,4]]) 
52
# grows pre-allocation buffer
>>> sys.getsizeof([i for i in [1,2,3,4,5]])
68
Reut Sharabani
źródło
4
Ale dlaczego nadmierna alokacja miałaby mieć miejsce w przypadku jednego, a drugiego nie?
cdarke
To konkretnie pochodzi z list.resize. Nie jestem ekspertem w poruszaniu się po źródle, ale jeśli jedno wywołuje zmianę rozmiaru, a drugie nie - może to wyjaśniać różnicę.
Reut Sharabani
6
Python 3.5.2 tutaj. Spróbuj wydrukować w pętli rozmiary list od 0 do 35. Dla listy, którą widzę 64, 96, 104, 112, 120, 128, 136, 144, 160, 192, 200, 208, 216, 224, 232, 240, 256, 264, 272, 280, 288, 296, 304, 312, 328, 336, 344, 352, 360, 368, 376, 384, 400, 408, 416i dla zrozumienia 64, 96, 96, 96, 96, 128, 128, 128, 128, 192, 192, 192, 192, 192, 192, 192, 192, 264, 264, 264, 264, 264, 264, 264, 264, 264, 344, 344, 344, 344, 344, 344, 344, 344, 344. Z wyjątkiem tego, że rozumienie jest tym, który wydaje się wstępnie alokować pamięć, jako algorytm, który używa więcej pamięci RAM dla pewnych rozmiarów.
tavo
Spodziewałbym się tego samego. Wkrótce będę mógł dokładniej się temu przyjrzeć. Dobre komentarze.
Reut Sharabani
4
w rzeczywistości list()deterministycznie określa rozmiar listy, czego nie można zrobić po zrozumieniu listy. Sugeruje to, że zrozumienie listy nie zawsze „wyzwala” „ostatni” wzrost listy. To może mieć sens.
Reut Sharabani
30

Dziękuję wszystkim za pomoc w zrozumieniu tego niesamowitego Pythona.

Nie chcę zadawać tak masowych pytań (dlatego piszę odpowiedź), chcę tylko pokazać i podzielić się swoimi przemyśleniami.

Jak @ReutSharabani poprawnie zauważył: „list () deterministycznie określa rozmiar listy”. Możesz to zobaczyć na tym wykresie.

wykres rozmiarów

Kiedy ty appendlub używasz rozumienia list, zawsze masz jakieś granice, które rozszerzają się, gdy osiągasz jakiś punkt. A z list()tobą masz prawie takie same granice, ale płyną.

AKTUALIZACJA

Więc dzięki @ReutSharabani , @tavo , @SvenFestersen

Podsumowując: list()wstępnie alokuje pamięć w zależności od rozmiaru listy, nie można tego zrobić po zrozumieniu listy (żąda więcej pamięci, gdy jest to potrzebne, np .append().). Dlatego list()przechowuj więcej pamięci.

Jeszcze jeden wykres, który pokazuje list()wstępnie przydzieloną pamięć. Tak więc zielona linia pokazuje list(range(830))dołączanie elementu po elemencie i przez chwilę pamięć się nie zmienia.

list () wstępnie przydziela pamięć

AKTUALIZACJA 2

Jak @Barmar zauważył w komentarzach poniżej, list()muszę być szybszy niż zrozumienie listy, więc uruchomiłem timeit()z number=1000długością listod 4**0do, 4**10a wyniki są

pomiary czasu

vishes_shell
źródło
1
Odpowiedź, dlaczego czerwona linia jest nad niebieską, jest taka, że ​​kiedy listkonstruktor może określić rozmiar nowej listy na podstawie swojego argumentu, nadal będzie wstępnie przydzielał taką samą ilość miejsca, jak gdyby ostatni element właśnie tam dotarł i nie było na niego wystarczająco dużo miejsca. Przynajmniej to ma dla mnie sens.
tavo
@tavo wydaje mi się to samo, po chwili chcę to pokazać na wykresie.
vishes_shell
2
Tak więc, chociaż listy składane zajmują mniej pamięci, prawdopodobnie są znacznie wolniejsze z powodu wszystkich zmian rozmiaru. Będą one często musiały skopiować szkielet listy do nowego obszaru pamięci.
Barmar
@Barmar właściwie mogę przeprowadzić pomiary czasu z rangeobiektem (to mogłoby być zabawne).
vishes_shell
Dzięki temu Twoje wykresy będą jeszcze ładniejsze. :)
Barmar