2009-05-27 16 views
54

Qual è la tipica struttura dati sottostante utilizzata per implementare il tipo di dati dell'elenco integrato di Python?Qual è la struttura dati sottostante per gli elenchi Python?

+0

due opzioni: 1) solo curiosità, o 2) ottimizzazione prematura. – flybywire

+0

Qualcun altro mi ha fatto questa domanda e ho detto loro che la mia intuizione era che l'implementazione era basata su array ma non ero sicuro. Questo ha aumentato la mia curiosità un po 'quindi decido di chiedere. – Nixuz

+13

Credetemi o meno Ho passato un paio di minuti su google per la risposta e anche se avessi scaricato il codice sorgente, probabilmente non saprei da dove cominciare. Ho pensato che qualcuno qui avrebbe saputo la risposta con il minimo sforzo e sembra che avessi ragione. Rappresentazione facile per loro, risposta veloce per me, tutti vincono. – Nixuz

risposta

42

Gli oggetti elenco sono implementati come array . Sono ottimizzati per operazioni veloci a lunghezza fissa e costi di spostamento memoria O (n) per operazioni di inserimento (0, v) inserto (0, v) che modificano sia la dimensione che la posizione della rappresentazione di dati sottostante di .

Consulta anche: http://docs.python.org/library/collections.html#collections.deque

Btw, trovo interessante il fatto che il tutorial Python su strutture di dati raccomanda l'uso di pop (0) per simulare una coda, ma non parlare di O (n) o l'opzione deque .

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

+5

Ottimo punto sul tutorial! Questo dovrebbe essere risolto. –

+4

Il tutorial esisteva molto prima del modulo deque, ecco perché. Segnalalo a bugs.python.org, se possibile con una patch per una frase corretta e il tutorial non fornirà più suggerimenti errati. –

23

CPython:

typedef struct { 
    PyObject_VAR_HEAD 
    /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ 
    PyObject **ob_item; 

    /* ob_item contains space for 'allocated' elements. The number 
    * currently in use is ob_size. 
    * Invariants: 
    *  0 <= ob_size <= allocated 
    *  len(list) == ob_size 
    *  ob_item == NULL implies ob_size == allocated == 0 
    * list.sort() temporarily sets allocated to -1 to detect mutations. 
    * 
    * Items must normally not be NULL, except during construction when 
    * the list is not yet visible outside the function that builds it. 
    */ 
    Py_ssize_t allocated; 
} PyListObject; 

Come si può vedere sulla riga seguente, l'elenco viene dichiarato come un array di puntatori a PyObjects.

PyObject **ob_item; 
Problemi correlati