Méthode d'ajustement de la longueur de la liste Python (avec code)

Ce que cet article vous apporte concerne la méthode d'ajustement de la longueur des listes Python (avec code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

La liste de Python est un tableau très flexible et la longueur peut être ajustée à volonté. C'est précisément à cause de cette commodité que nous ne pouvons nous empêcher de modifier le tableau pour répondre à nos besoins. Par rapport à l'insertion, au pop, etc., l'utilisation de l'ajout est plus courante.

Certains sont utilisés comme ceci :

>>> test = []
>>> test.append(1)
>>> test.append({2})
>>> test.append([3])
>>> print test

# 输出 
[1, set([2]), [3]]

Il y en a aussi certains utilisés comme ceci :

test = []

for i in range(4):
    test.append(i)
print test

# 输出 
[0, 1, 2, 3]

L'utiliser de cette façon est très heureux et satisfaisant.

Mais en fait, chaque fois que nous rencontrons un scénario où la longueur des données peut être modifiée dynamiquement, nous devons immédiatement réagir, c'est-à-dire le problème de la gestion de la mémoire.

Si l'efficacité opérationnelle et la commodité sont réunies en même temps, ce sera une excellente nouvelle.

Cependant, lorsque Dieu vous ouvre une fenêtre, il doit aussi avoir fermé une porte !

Initialisation avare

Nous sommes profondément influencés par la connaissance de la pré-allocation. Nous pensons également que la liste se voit attribuer une certaine longueur lors de l'initialisation, sinon elle serait "faible" à demander. mémoire à chaque fois ah.

En fait, la liste est vraiment si « basse » :

import sys

test = []
test_1 = [1]
print sys.getsizeof(test)
print sys.getsizeof(test_1) - sys.getsizeof(test)

# 输出 
72     # 空列表内存大小，也是 list 对象的总大小
8       # 代表增加一个成员，list 增加的大小

Nous pensons qu'une fois la liste définie, un pool d'une certaine taille sera pré-alloué pour le remplissage data , pour éviter de demander de la mémoire à chaque tour.

Mais l'expérience ci-dessus montre que la longueur d'une liste de membres n'est que de 8 octets plus grande qu'une liste vide. S'il existe réellement un tel pool pré-alloué, alors le nombre de membres pré-alloués lors de l'ajout de membres, la taille de la mémoire des deux doit rester inchangée.

On peut donc deviner que cette liste ne dispose pas d'un tel pool de mémoire pré-alloué. Ici, nous avons besoin d'un vrai marteau

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
        
    // list对象指针的缓存
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    
    // list 成员的内存申请
    nbytes = size * sizeof(PyObject *);
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

Lorsque nous exécutons test = [1], nous ne faisons en fait que deux choses :

Selon le nombre de membres, construire une longueur correspondante Liste vide ; (au-dessus du code)

Mettez ces membres un par un

Certains enfants peuvent penser qu'à l'étape de branchement des membres, un mécanisme peut être déclenché pour le faire devenir grand ?

C'est dommage, car la méthode d'initialisation est PyList_SET_ITEM, donc il n'y a pas de mécanisme de déclenchement ici, c'est juste une simple affectation des membres du tableau :

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

Donc la liste entière est initialisé, il n'y a vraiment pas de pool de mémoire pré-alloué. Vous pouvez en faire la demande directement sur demande. Chaque carotte est une fosse, ce qui est vraiment cruel

La clé de la longueur variable

Initialisation Il est compréhensible que le processus soit ainsi, mais s'il est toujours ainsi pendant le fonctionnement, ce serait un peu déraisonnable.

Imaginez simplement, dans l'exemple d'utilisation de append au début de l'article, si la mémoire est appliquée à chaque fois qu'un élément est ajouté, alors la liste peut être critiquée au point de douter de la vie, c'est donc Il est évident que lors d'une demande de mémoire, il a toujours sa propre routine.

Dans la liste, que ce soit par insertion, pop ou ajout, vous rencontrerez list_resize. Comme son nom l'indique, cette fonction est utilisée pour ajuster l'utilisation de la mémoire des objets de liste.

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

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

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;

    # 申请内存
    items = self->ob_item;
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

Dans le code ci-dessus, nous voyons fréquemment deux noms : newsize et new_allocated Il faut expliquer ici que newsize n'est pas le nombre d'augmentations/diminutions, mais le nombre total de membres après l'augmentation. /diminuer. Par exemple :

a = [1, 2, 3]
a.append(1)

Lorsque l'ajout ci-dessus déclenche list_resize, newsize est 3 + 1, et non 1 ; c'est plus important, car lors de la réduction des membres de la liste tels que pop, la liste réduite est transmise en nombre total. .

Dans la définition de la structure de la liste, il existe deux définitions de longueur, à savoir ob_size (nombre réel de membres) et allouée (nombre total de membres)

La relation entre elles est :

 0 <= ob_size <= allocated
 len(list) == ob_size

Donc, new_allocated est facile à comprendre. Il s'agit du nouveau nombre total de fosses.

Quand le sens du nom est presque compris, on peut suivre les indices pour savoir quelle deviendra la taille d'une liste après list_resize ?

La méthode est en fait très claire d'après les commentaires et le code ci-dessus. Voici un bref résumé :

Déterminez d'abord une base : new_allocated = (newsize >> 3) + (newsize <. ; 9 ? 3 : 6);

Déterminez si new_allocated + newsize dépasse PY_SIZE_MAX S'il dépasse, une erreur sera signalée directement ;

Déterminez enfin le nouveau nombre total de fosses : new_allocated +. newsize , si newsize est 0, alors le nombre total de fosses est directement 0

Démontrez ci-dessous :

#coding: utf8
import sys

test = []
raw_size = sys.getsizeof(test)

test.append(1)
print "1 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "2 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "3 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "4 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "5 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "6 次 append 减去空列表的内存大小：%s " % (sys.getsizeof(test) - raw_size)

# 输出结果
1 次 append 减去空列表的内存大小：32
2 次 append 减去空列表的内存大小：32
3 次 append 减去空列表的内存大小：32
4 次 append 减去空列表的内存大小：32
5 次 append 减去空列表的内存大小：64
6 次 append 减去空列表的内存大小：64

Démarrez la méthode de substitution simple pour calculer étape par étape :

Parmi eux :

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize (car le newsize suivant > 0)

Lorsque l'original alloué >= newize et newize >= original alloué / 2, ne change pas l'allocation et ne s'applique pas à la mémoire et renvoie directement

第 n 次 append	列表原长度	新增成员数	原 allocated	newsize	new_allocated
1	0	1	0	0 + 1 = 1	3 + 1 = 4
2	1	1	4	1 + 1 = 2	无需改变
3	2	1	4	2 + 1 = 3	无需改变
4	3	1	4	3 + 1 = 4	无需改变
5	4	1	4	4 + 1 = 5	3 + 5 = 8
6	5	1	8	5 + 1 = 6	无需改变

通过上面的表格，应该比较清楚看到什么时候会触发改变 allocated，并且当触发时它们是如何计算的。为什么我们需要这样关注 allocated？理由很简单，因为这个值决定了整个 list 的动态内存的占用大小；

扩容是这样，缩容也是照猫画虎。反正都是算出新的 allocated， 然后由 PyMem_RESIZE 来处理。

总结

综上所述，在一些明确列表成员或者简单处理再塞入列表的情况下，我们不应该再用下面的方式：

test = []

for i in range(4):
    test.append(i)
print test

而是应该用更加 pythonic 和 更加高效的列表推导式：test = [i for i in range(4)]。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!