Domanda Dimensione dell'elenco in memoria


Ho appena sperimentato la dimensione delle strutture di dati Python in memoria. Ho scritto il seguente frammento:

import sys
lst1=[]
lst1.append(1)
lst2=[1]
print(sys.getsizeof(lst1), sys.getsizeof(lst2))

Ho testato il codice nelle seguenti configurazioni:

  • Windows 7 a 64 bit, Python3.1: l'output è: 52 40 quindi lst1 ha 52 byte e lst2 ha 40 byte.
  • Ubuntu 11.4 32 bit con Python3.2: l'output è 48 32
  • Ubuntu 11.4 32bit Python2.7: 48 36

Qualcuno può spiegarmi perché le due taglie differiscono nonostante entrambe le liste contengano un 1?

Nella documentazione di Python per la funzione getsizeof ho trovato quanto segue: ...adds an additional garbage collector overhead if the object is managed by the garbage collector. Potrebbe essere il caso nel mio piccolo esempio?


44
2017-08-30 17:29


origine


risposte:


Ecco una sessione interattiva più completa che mi aiuterà a spiegare cosa sta succedendo (Python 2.6 su Windows XP a 32 bit, ma non importa davvero):

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52
>>> 

Si noti che la lista vuota è un po 'più piccola di quella con [1] dentro. Quando un elemento viene aggiunto, tuttavia, diventa molto più grande.

La ragione di ciò sono i dettagli di implementazione in Objects/listobject.c, nella fonte di CPython.

Lista vuota

Quando una lista vuota [] viene creato, nessuno spazio per gli elementi è allocato - questo può essere visto in PyList_New. 36 byte è la quantità di spazio richiesta per la struttura dei dati dell'elenco stessa su una macchina a 32 bit.

Elenco con un elemento

Quando una lista con un singolo elemento [1] viene creato, lo spazio per un elemento viene allocato in aggiunta alla memoria richiesta dalla struttura dei dati dell'elenco stessa. Di nuovo, questo può essere trovato in PyList_New. Dato size come argomento, calcola:

nbytes = size * sizeof(PyObject *);

E poi ha:

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;

Quindi lo vediamo con size = 1, lo spazio per un puntatore è allocato. 4 byte (sulla mia scatola a 32 bit).

Aggiungendo a una lista vuota

Quando si chiama append su una lista vuota, ecco cosa succede:

  • PyList_Append chiamate app1
  • app1 chiede la dimensione della lista (e ottiene 0 come risposta)
  • app1 quindi chiama list_resize con size+1 (1 nel nostro caso)
  • list_resize ha una strategia di allocazione interessante, sintetizzata in questo commento dalla sua fonte.

Ecco qui:

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

Facciamo un po 'di matematica

Vediamo come vengono raggiunti i numeri che ho citato nella sessione all'inizio del mio articolo.

Quindi 36 byte è la dimensione richiesta dalla struttura dei dati dell'elenco stessa su 32 bit. Con un singolo elemento, lo spazio è allocato per un puntatore, quindi sono 4 byte in più - totale 40 byte. OK finora.

quando app1 viene chiamato su una lista vuota, chiama list_resize con size=1. Secondo l'algoritmo di sovra-allocazione di list_resize, la prossima dimensione più grande disponibile dopo 1 è 4, quindi verrà assegnato un posto per 4 puntatori. 4 * 4 = 16 byte e 36 + 16 = 52.

In effetti, tutto ha un senso :-)


90
2017-08-30 17:49



scusa, il commento precedente è stato un po 'brusco.

quello che sta succedendo è che stai guardando come sono allocate le liste (e penso che forse volevi solo vedere quanto erano grandi le cose - in quel caso, usa sys.getsizeof())

quando qualcosa viene aggiunto a una lista, può accadere una delle due cose:

  1. l'oggetto in più si adatta allo spazio libero

  2. è necessario spazio aggiuntivo, quindi viene creato un nuovo elenco, i contenuti vengono copiati e la parte aggiuntiva aggiunta.

dal momento che (2) è costoso (copiare le cose, anche i puntatori, richiede tempo proporzionale al numero di cose da copiare, quindi cresce man mano che le liste diventano grandi) vogliamo farlo di rado. quindi invece di aggiungere un po 'più di spazio, aggiungiamo un pezzo intero. tipicamente la dimensione della quantità aggiunta è simile a quella che è già in uso - in questo modo la matematica calcola che il costo medio di allocazione della memoria, distribuito su molti usi, è solo proporzionale alla dimensione dell'elenco.

quindi quello che stai vedendo è legato a questo comportamento. non conosco i dettagli esatti, ma non sarei sorpreso se [] o [1] (o entrambi) sono casi speciali, in cui è allocata solo una quantità di memoria sufficiente (per risparmiare memoria in questi casi comuni), quindi l'aggiunta fa "afferrare un nuovo blocco" sopra descritto che aggiunge altro.

ma non conosco i dettagli esatti - questo è solo il modo in cui gli array dinamici funzionano in generale. l'esatta implementazione degli elenchi in python sarà ottimizzata per renderla ottimale per i tipici programmi python. quindi tutto quello che sto dicendo è che non ti puoi fidare della dimensione di una lista per dirti esattamente quanto contenga: potrebbe contenere spazio extra e la quantità di spazio libero extra è difficile da giudicare o prevedere.

ps un'alternativa pulita a questo è di fare liste come (value, pointer) coppie, in cui ogni puntatore punta alla tupla successiva. in questo modo è possibile aumentare le liste in modo incrementale, sebbene la memoria totale utilizzata sia più alta. questa è una lista collegata (ciò che Python usa è più come un vettore o un array dinamico).

[aggiorna] vedi l'eccellente risposta di Eli. lui / lei spiega che entrambi [] e [1] sono assegnati esattamente, ma che si aggiungono a [] alloca un altro chunk. il commento nel codice è quello che sto dicendo sopra (questo è chiamato "sovra-allocazione" e l'importo è proporzionale a quello che abbiamo in modo che il costo medio ("ammortizzato") sia proporzionale alle dimensioni).


9
2017-08-30 17:44



Ecco una rapida dimostrazione del modello di crescita dell'elenco. Cambiare il terzo argomento in range () cambierà l'output in modo che non assomigli ai commenti in listobject.c, ma il risultato quando semplicemente aggiungendo un elemento sembra perfettamente accurato.

allocated = 0
for newsize in range(0,100,1):
    if (allocated < newsize):
        new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)
        allocated = newsize + new_allocated;
    print newsize, allocated

2
2017-08-01 21:11