list() utilise légèrement plus de mémoire que list comprehension

Question

Donc je jouais avec list objets et j'ai trouvé une petite chose étrange que si list est créé avec list() utilise-t-il plus de mémoire que la compréhension de liste ? J'utilise 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

De la docs :

Les listes peuvent être construites de plusieurs façons :

• Utilisation d'une paire de crochets pour désigner la liste vide : []
• En utilisant des crochets, en séparant les éléments par des virgules : [a] , [a, b, c]
• Utilisation d'une liste de compréhension : [x for x in iterable]
• Utilisation du constructeur de type : list() ou list(iterable)

Mais il semble que l'utilisation list() il utilise plus de mémoire.

Et autant list est plus grand, l'écart augmente.

Pourquoi cela se produit-il ?

UPDATE #1

Testé avec Python 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

UPDATE #2

Testé avec Python 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

Je pense que vous voyez des modèles de sur-allocation, c'est un échantillon de la 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);

---

En imprimant les tailles des compréhensions de listes de longueurs 0-88, vous pouvez voir les correspondances de motifs :

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

Résultats (le format est (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))

---

La surallocation est faite pour des raisons de performance permettant aux listes de croître sans allouer plus de mémoire à chaque croissance (meilleure amorti performance).

Une raison probable de la différence avec l'utilisation de la compréhension de liste est que cette dernière ne peut pas calculer de manière déterministe la taille de la liste générée, mais list() peut. Cela signifie que les comprehensions vont continuellement faire croître la liste au fur et à mesure qu'elles la remplissent en utilisant la sur-allocation jusqu'à ce qu'elle soit finalement remplie.

Il est possible que le tampon de surallocation ne soit pas rempli de nœuds alloués inutilisés une fois qu'il est terminé (en fait, dans la plupart des cas, il ne le sera pas, cela irait à l'encontre de l'objectif de surallocation).

list() Cependant, il peut ajouter un tampon, quelle que soit la taille de la liste, puisqu'il connaît à l'avance la taille finale de la liste.

---

Une autre preuve de soutien, provenant également de la source, est que nous voyons liste des compréhensions invoquant LIST_APPEND qui indique l'utilisation de list.resize ce qui indique que l'on consomme la mémoire tampon de pré-affectation sans savoir quelle proportion de celle-ci sera remplie. Ceci est cohérent avec le comportement que vous observez.

---

Pour conclure, list() pré-allouera plus de nœuds en fonction de la taille de la liste

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

La compréhension de liste ne connaît pas la taille de la liste, elle utilise donc des opérations d'ajout au fur et à mesure de sa croissance, épuisant le tampon de pré-affectation :

# 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

Merci à tous de m'avoir aidé à comprendre ce formidable Python.

Je ne veux pas rendre la question aussi massive (c'est pourquoi je poste la réponse), je veux juste montrer et partager mes pensées.

Comme @ReutSharabani a noté correctement : "list() détermine de façon déterministe la taille de la liste". Vous pouvez le voir sur ce graphique.

Quand vous append ou en utilisant la compréhension de liste, vous avez toujours une sorte de limite qui s'étend lorsque vous atteignez un certain point. Et avec list() vous avez presque les mêmes limites, mais elles sont flottantes.

UPDATE

Donc, grâce à @ReutSharabani , @tavo , @SvenFestersen

Pour résumer : list() préalloue la mémoire en fonction de la taille de la liste, la compréhension de liste ne peut pas faire cela (elle demande plus de mémoire quand elle en a besoin, comme .append() ). C'est pourquoi list() stocker plus de mémoire.

Un autre graphique, qui montre list() préallouer la mémoire. La ligne verte montre donc list(range(830)) en ajoutant élément par élément et pendant un moment la mémoire ne change pas.

MISE À JOUR 2

Comme l'a noté @Barmar dans les commentaires ci-dessous, list() doit être plus rapide que la compréhension de liste, donc j'ai lancé timeit() avec number=1000 pour la longueur de list de 4**0 à 4**10 et les résultats sont