list() zużywa więcej pamięci niż rozumienie list

Question

Tak więc bawiłem się z obiektami list i znalazłem trochę dziwnej rzeczy, że jeśli list zostanie utworzony z list(), to zużywa więcej pamięci niż rozumienia list? Używam Python 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 docs:

Listy mogą być wykonane na kilka sposobów:

• Korzystanie parę nawiasów kwadratowych do oznaczenia pustą listę : []
• Za pomocą nawiasów kwadratowych, rozdzielając elementy przecinkami: [a], [a, b, c]
• Korzystanie z listy ze zrozumieniem: [x for x in iterable]
• Korzystanie z konstruktora typu: list() lub list(iterable)

Ale wydaje się, że za pomocą list() wykorzystuje więcej pamięci.

I tak jak list jest większy, różnica wzrasta.

Dlaczego tak się dzieje?

Aktualizacja # 1

testu Pythona 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

testu Pythona 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 

Answer 1

Myślę, że widzisz o ver-alokacji desenie to sample from the source:

/* 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); 

---

Drukowanie rozmiary listowych o długości 0-88 można zobaczyć wzór pasuje:

# 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 jest (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)) 

---

Nadmiar alokacji jest wykonywany ze względu na wydajność, dzięki czemu listy mogą rosnąć, nie przydzielając więcej pamięci przy każdym wzroście (lepsza wydajność: amortized).

Prawdopodobną przyczyną różnicy w korzystaniu ze sprawdzania listy jest to, że zrozumienie listy nie może deterministycznie obliczyć rozmiaru wygenerowanej listy, ale może to zrobić list().Oznacza to, że ze zrozumieniem będzie stale rosła lista, ponieważ wypełnia ją przy użyciu nadmiernej alokacji, aż do jej ostatecznego wypełnienia.

Jest możliwe, że nie zwiększy to nadmiernie alokowanego bufora z nieużywanymi przydzielonymi węzłami po jego zakończeniu (w rzeczywistości, w większości przypadków nie będzie to oznaczać, że pokona to cel nadmiernej alokacji).

list(), może jednak dodać bufor bez względu na rozmiar listy, ponieważ wcześniej zna ostateczną wielkość listy.

---

Innym podkład dowody, także od źródła, jest to, że widzimy list comprehensions invoking LIST_APPEND, co wskazuje użycie list.resize, co z kolei wskazuje na spożywanie bufor wstępnego przydziału, nie wiedząc, ile z tego zostanie wypełniona. Jest to zgodne z zachowaniem, które widzisz.

---

Podsumowując, list() będzie wstępnie przeznaczyć więcej węzłów w zależności od wielkości listy

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

Lista rozumienie nie zna rozmiaru listy więc używa dołączyć operacje, jak rośnie, niszczących bufor pre-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 

Answer 2

Dziękuję wszystkim za pomoc w zrozumieniu tego wspaniałego Pythona.

Nie chcę kwestionować tego ogromnego (dlatego zamieszczam odpowiedź), chcę tylko pokazać i podzielić się moimi przemyśleniami.

Jako @ReutSharabani odnotowano poprawnie: "list() deterministically określa rozmiar listy". Możesz go zobaczyć na tym wykresie.

Kiedy append lub używając listowych zawsze masz jakieś granice, które rozciąga się po osiągnięciu pewnego punktu. I z list() masz prawie takie same granice, ale one są pływające.

UPDATE

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

Podsumowując: list() preallocates pamięci zależy od wielkości listy, lista rozumienie nie może zrobić (żąda więcej pamięci, kiedy to potrzebne, jak .append()). To dlatego list() przechowywać więcej pamięci.

Jeszcze jeden wykres pokazujący, że list() przypisuje wcześniejszą pamięć. Tak więc zielona linia pokazuje list(range(830)) dołączanie elementu po elemencie i przez chwilę pamięć się nie zmienia.

UPDATE 2

Jak zauważył @Barmar w komentarzach poniżej, list() musi mi szybciej niż listowego, więc pobiegł timeit() z number=1000 o długości list z 4**0 do 4**10 i wyników to