Pourquoi les n-uplets prennent-ils moins de place en mémoire que les listes?

Question

A tuple prend moins d’espace mémoire en Python:

 >>> a = (1,2,3)
>>> a.__sizeof__()
48
 

alors que list s prend plus d’espace mémoire:

 >>> b = [1,2,3]
>>> b.__sizeof__()
64
 

Que se passe-t-il en interne sur la gestion de la mémoire Python?

Answer 1

Je suppose que vous êtes à l'aide Disponible et avec 64bits (j'ai les mêmes résultats sur mon Disponible 2.7 64 bits). Il pourrait y avoir des différences dans d'autres implémentations de Python ou si vous avez un 32bit Python.

Indépendamment de la mise en œuvre, lists sont de taille variable, tout tuples sont de taille fixe.

Donc, tuples peuvent stocker les éléments directement à l'intérieur de la structure, des listes d'autre part besoin d'une couche d'indirection (il stocke un pointeur vers les éléments). Cette couche d'indirection est un pointeur, sur les systèmes 64 bits que 64 bits, donc 8bytes.

Mais il y a autre chose que lists: Ils ont plus de-allouer. Sinon, list.append serait un O(n) opération toujours à en faire amorti O(1) (beaucoup plus rapide!!!) il alloue. Mais maintenant, c'est de garder une trace de la alloués taille et le rempli de taille (tuples seulement besoin de stocker une seule taille, car alloué et rempli de taille sont toujours identiques). Cela signifie que chaque liste a pour enregistrer un autre "taille" qui sur les systèmes 64 bits est un 64 bits entier, de nouveau de 8 octets.

Donc, lists besoin d'au moins 16 octets de plus de mémoire que d' tuples. Pourquoi je dis "au moins"? En raison de la sur-allocation. Sur-allocation signifie qu'il alloue plus d'espace que nécessaire. Toutefois, le montant des plus-allocation dépend de "comment" vous créez la liste et l'ajout/la suppression de l'histoire:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers re-allocation (with over-allocation), because the original list is full
>>> l.__sizeof__()
96

>>> l = []
>>> l.__sizeof__()
40
>>> l.append(1)  # re-allocation with over-allocation
>>> l.__sizeof__()
72
>>> l.append(2)  # no re-alloc
>>> l.append(3)  # no re-alloc
>>> l.__sizeof__()
72
>>> l.append(4)  # still has room, so no over-allocation needed (yet)
>>> l.__sizeof__()
72

Images

J'ai décidé de créer des images pour accompagner l'explication ci-dessus. Peut-être ceux-ci sont utiles

C'est la façon dont il (schématiquement) est stocké en mémoire dans votre exemple. J'ai mis en évidence les différences avec le rouge (main libre) cycles:

C'est en fait juste une approximation, car int des objets sont également des objets Python et Disponible même réutilise les petits entiers, probablement représentation plus précise (bien que pas aussi lisible) des objets de mémoire serait:

Liens utiles:

• tuple struct dans Disponible référentiel pour Python 2.7
• list struct dans Disponible référentiel pour Python 2.7
• int struct dans Disponible référentiel pour Python 2.7

Notez que __sizeof__ n'a pas vraiment de retour de la "bonne" taille de! Il retourne uniquement la taille des valeurs stockées. Toutefois, lorsque vous utilisez sys.getsizeof le résultat est différent:

>>> import sys
>>> l = [1,2,3]
>>> t = (1, 2, 3)
>>> sys.getsizeof(l)
88
>>> sys.getsizeof(t)
72

Il y a 24 "extra" octets. Ce sont des vrais, c'est le garbage collector généraux qui n'est pas comptabilisée dans l' __sizeof__ méthode. C'est parce que vous êtes généralement pas censé utiliser les méthodes magiques directement - utiliser les fonctions qui savent comment les traiter, dans ce cas: sys.getsizeof (ce qui ajoute de la GC généraux de la valeur retournée par __sizeof__).

Answer 2

Je vais le prendre plus profondément les Disponible de la base de code afin que nous puissions voir comment les tailles sont effectivement calculés. Dans votre exemple, pas de sur-allocation ont été effectuées, donc je ne touche même pas sur que.

Je vais utiliser les valeurs de 64 bits ici, comme vous l'êtes.

---

La taille pour l' lists est calculé à partir de la fonction suivante, list_sizeof:

static PyObject *
list_sizeof(PyListObject *self)
{
    Py_ssize_t res;

    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
    return PyInt_FromSsize_t(res);
}

Ici, Py_TYPE(self) est une macro qui saisit l' ob_type de self (de retour PyList_Type), tandis que _PyObject_SIZE est une autre macro qui attrape tp_basicsize de ce type. tp_basicsize est calculé comme sizeof(PyListObject) où PyListObject , est l'instance struct.

L' PyListObject structure comporte trois champs:

PyObject_VAR_HEAD     # 24 bytes 
PyObject **ob_item;   #  8 bytes
Py_ssize_t allocated; #  8 bytes

ces commentaires (que j'ai coupé) expliquant ce qu'ils sont, suivez le lien ci-dessus pour les lire. PyObject_VAR_HEAD se développe en trois 8 octets des champs (ob_refcount, ob_type et ob_sizeun 24 octet contribution.

Donc pour l'instant, res est:

sizeof(PyListObject) + self->allocated * sizeof(void*)

ou:

40 + self->allocated * sizeof(void*)

Si l'instance de liste a des éléments qui sont alloués. la deuxième partie calcule leur contribution. self->allocated, comme son nom l'indique, contient le nombre de allouées éléments.

Sans aucun éléments, la taille des listes est fixée à:

>>> [].__sizeof__()
40

j'.e la taille de l'instance struct.

---

tuple objets ne définissent pas un tuple_sizeof fonction. Au lieu de cela, ils utilisent object_sizeof pour le calcul de leur taille:

static PyObject *
object_sizeof(PyObject *self, PyObject *args)
{
    Py_ssize_t res, isize;

    res = 0;
    isize = self->ob_type->tp_itemsize;
    if (isize > 0)
        res = Py_SIZE(self) * isize;
    res += self->ob_type->tp_basicsize;

    return PyInt_FromSsize_t(res);
}

Cela, comme pour lists, saisit l' tp_basicsize et, si l'objet a une valeur non nulle tp_itemsize (sens de la longueur variable des cas), il multiplie le nombre d'éléments dans le tuple (qu'il obtient via Py_SIZE) avec tp_itemsize.

tp_basicsize utilise à nouveau sizeof(PyTupleObject) où l' PyTupleObject struct contient:

PyObject_VAR_HEAD       # 24 bytes 
PyObject *ob_item[1];   # 8  bytes

Alors, sans aucun des éléments (c'est - Py_SIZE retours 0) de la taille de vide de n-uplets est égale à sizeof(PyTupleObject):

>>> ().__sizeof__()
24

hein? Eh bien, voici une bizarrerie que je n'ai pas trouvé une explication, l' tp_basicsize de tuples est en fait calculé comme suit:

sizeof(PyTupleObject) - sizeof(PyObject *)

pourquoi supplémentaires 8 octets est supprimé à partir d' tp_basicsize est quelque chose que je n'ai pas été en mesure de trouver. (Voir MSeifert commentaire pour une explication possible)

---

Mais, c'est en gros la différence dans votre exemple. lists aussi garder autour d'un certain nombre de allouées éléments qui aide à déterminer quand à la sur-allouer de nouveau.

Maintenant, lorsque de nouveaux éléments sont ajoutés, les listes ne sont en effet effectuer cette sur-allocation pour atteindre O(1) ajoute. Il en résulte en grande taille comme MSeifert du couvre parfaitement dans sa réponse.

Answer 3

MSeifert réponse le couvre largement; garder les choses simples que vous pouvez penser:

tuple est immuable. Une fois défini, vous ne pouvez pas la modifier. Si vous savez à l'avance combien de mémoire vous avez besoin d'allouer pour l'objet.

list est mutable. Vous pouvez ajouter ou supprimer des éléments ou à partir d'elle. Il a de connaître la taille (pour les internes impl.). Il redimensionne en tant que de besoin.

Il n'y a pas de repas gratuits - ces capacités a un coût. D'où la surcharge de la mémoire de listes.

Answer 4

La taille de la n-uplet est préfixé, ce qui signifie au n-uplet de l'initialisation de l'interpréteur allouer suffisamment d'espace pour le contenu des données, et c'est la fin de celui-ci, en lui donnant de l'immuable (ne peut pas être modifié), tandis qu'une liste est un objet mutable donc ce qui implique l'allocation dynamique de la mémoire, afin d'éviter d'allouer de l'espace à chaque fois que vous ajoutez ou modifiez la liste ( allouer suffisamment d'espace pour contenir les données modifiées et de copier les données), il alloue de l'espace supplémentaire pour les futurs ajout, la modification, l' ... c'est à peu près le résume.