Więc bawiłem się list
obiektami i znalazłem małą dziwną rzecz, która jeśli list
zostanie 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 list
jest większe, tym różnica rośnie.
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
python
list
list-comprehension
cpython
python-internals
vishes_shell
źródło
źródło
sys.getsizeof(list(range(100)))
to 1016,getsizeof(range(100))
to 872 igetsizeof([i for i in range(100)])
to 920. Wszystkie mają ten typlist
.xrange
.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.Odpowiedzi:
Myślę, że widzisz wzorce nadmiernej alokacji. Oto przykład ze źródła :
/* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
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ń listowych
LIST_APPEND
, co wskazuje na użycielist.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
źródło
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ę.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, 416
i dla zrozumienia64, 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.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.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.
Kiedy ty
append
lub używasz rozumienia list, zawsze masz jakieś granice, które rozszerzają się, gdy osiągasz jakiś punkt. A zlist()
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()
.). Dlategolist()
przechowuj więcej pamięci.Jeszcze jeden wykres, który pokazuje
list()
wstępnie przydzieloną pamięć. Tak więc zielona linia pokazujelist(range(830))
dołączanie elementu po elemencie i przez chwilę pamięć się nie zmienia.AKTUALIZACJA 2
Jak @Barmar zauważył w komentarzach poniżej,
list()
muszę być szybszy niż zrozumienie listy, więc uruchomiłemtimeit()
znumber=1000
długościąlist
od4**0
do,4**10
a wyniki sąźródło
list
konstruktor 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.range
obiektem (to mogłoby być zabawne).