Methode zur Anpassung der Listenlänge in Python (mit Code)

In diesem Artikel geht es um die Längenanpassungsmethode von Python-Listen (mit Code). Freunde in Not können sich darauf beziehen.

Pythons Liste ist ein sehr flexibles Array und die Länge kann nach Belieben angepasst werden. Gerade aus diesem Grund können wir nicht anders, als das Array an unsere Bedürfnisse anzupassen. Im Vergleich zu Einfügen, Pop usw. ist die Verwendung von Anhängen häufiger.

Einige werden so verwendet:

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

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

Es gibt auch einige, die so verwendet werden:

test = []

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

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

Es ist sehr glücklich und befriedigend, es auf diese Weise zu verwenden.

Tatsächlich sollten wir jedoch immer dann, wenn wir auf ein Szenario stoßen, in dem die Datenlänge dynamisch geändert werden kann, sofort auf eines reagieren, und zwar auf das Problem der Speicherverwaltung.

Wenn Betriebseffizienz und Komfort gleichzeitig gewährleistet sind, sind das großartige Neuigkeiten.

Wenn Gott jedoch ein Fenster für dich öffnet, muss er auch eine Tür geschlossen haben!

Geizige Initialisierung

Wir sind stark von dem Wissen über die Vorzuweisung beeinflusst. Wir sind auch der Meinung, dass der Liste bei der Initialisierung eine bestimmte Länge zugewiesen wird, sonst wäre die Beantragung „niedrig“. Erinnerung jedes Mal ah.

Dann ist die Liste tatsächlich so „niedrig“:

import sys

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

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

Unsere Vermutung ist, dass nach der Definition der Liste ein Pool einer bestimmten Größe vorab zugewiesen wird, um die Daten zu füllen . Vermeiden Sie es, auf Schritt und Tritt Speicher zu beantragen.

Aber das obige Experiment zeigt, dass die Länge einer Mitgliederliste nur 8 Bytes größer ist als die einer leeren Liste. Wenn es wirklich einen solchen vorab zugewiesenen Pool gibt, dann ist die Anzahl der vorab zugewiesenen Mitglieder. Die Speichergröße beider sollte unverändert bleiben.

Man kann also davon ausgehen, dass diese Liste keinen solchen vorab zugewiesenen Speicherpool hat. Hier brauchen wir einen echten Hammer

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;
}

Wenn wir test = [1] ausführen, machen wir eigentlich nur zwei Dinge:

Erstellen Sie eine leere Liste entsprechender Länge basierend auf der Anzahl der Mitglieder. (Obeniger Code)

Setzen Sie diese Mitglieder einzeln ein;

Einige Kinder denken vielleicht, dass beim Schritt des Füllens der Mitglieder ein Mechanismus ausgelöst werden könnte, um sie größer zu machen?

Es ist schade, denn die Initialisierungsmethode ist PyList_SET_ITEM, daher gibt es hier keinen Auslösemechanismus, sondern nur eine einfache Zuweisung von Array-Mitgliedern:

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

Die Initialisierung der gesamten Liste erfolgt also Das Einzige ist, dass es keinen vorab zugewiesenen Speicherpool gibt. Sie können ihn bei Bedarf direkt beantragen.

Der Schlüssel zur variablen Länge 🎜>

Der Initialisierungsprozess ist zwar verständlich, aber wenn das im laufenden Betrieb weiterhin so bleibt, wäre das etwas unzumutbar.

Stellen Sie sich vor, im Beispiel der Verwendung von append am Anfang des Artikels wird die Liste möglicherweise so kritisiert, dass das Leben in Frage gestellt wird, wenn bei jedem Anhängen eines Elements ein Speicher angewendet wird Es ist offensichtlich, dass er bei der Beantragung des Gedächtnisses immer noch seine eigene Routine hat.

In der Liste, egal ob es sich um Einfügen, Einfügen oder Anhängen handelt, werden Sie auf list_resize stoßen. Wie der Name schon sagt, wird diese Funktion verwendet, um die Speichernutzung des Listenobjekts anzupassen.

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;
}

Im obigen Code kommen häufig zwei Substantive vor: newsize und new_allocated. Hier muss erklärt werden, dass newsize nicht die Anzahl der Erhöhungen/Verringerungen ist, sondern die Gesamtzahl der Mitglieder nach der Erhöhung/Verringerung . Zum Beispiel:

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

Wenn das obige Anhängen list_resize auslöst, ist newsize 3 + 1, nicht 1; dies ist wichtiger, da beim Reduzieren von Listenmitgliedern wie Pop die reduzierte Gesamtzahl übergeben wird.

In der Strukturdefinition der Liste gibt es zwei Längendefinitionen, nämlich ob_size (tatsächliche Anzahl der Mitglieder) und zugewiesen (Gesamtzahl der Mitglieder)

Die Beziehung zwischen ihnen ist:

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

new_allocated ist also leicht zu verstehen. Dies ist die neue Gesamtzahl der Pits.

Wenn die Bedeutung des Substantivs fast verstanden ist, können wir den Hinweisen folgen, um zu erfahren, wie groß eine Liste nach „list_resize“ sein wird.

Die Methode geht aus den Kommentaren und dem Code oben eigentlich sehr klar hervor:

Bestimmen Sie zunächst eine Basis: new_allocated = (newsize >> 3) + (newsize < ; 9 ? 3 : 6);

Beurteilen Sie, ob new_allocated + newsize PY_SIZE_MAX überschreitet, wird direkt ein Fehler gemeldet;

Bestimmen Sie abschließend die neue Gesamtzahl der Pits: new_allocated + newsize: Wenn newsize 0 ist, beträgt die Gesamtzahl der Pits direkt 0 >Unter ihnen:

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize (da die folgende newsize > 0)

Wenn die original zugewiesen >= newsize und newsize >= ursprünglich zugewiesen / 2, ändert die zugewiesene Größe nicht, gilt nicht für den Speicher und gibt direkt

zurück

第 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)]。

Das obige ist der detaillierte Inhalt vonMethode zur Anpassung der Listenlänge in Python (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!