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?
risposta
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
Ottimo punto sul tutorial! Questo dovrebbe essere risolto. –
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. –
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;
Nel Jython implementation, è un ArrayList<PyObject>
.
- 1. qual è la struttura dati sottostante dell'elenco STL, vettore e set?
- 2. Come sincronizzare gli elenchi Python?
- 3. struttura dati appropriata per la tabella che utilizza gli intervalli
- 4. Qual è la struttura dati dietro i set di Clojure?
- 5. Qual è la migliore struttura (i) di dati C# Per la seguente situazione
- 6. Struttura dati più appropriata (Python)
- 7. Qual è il tema sottostante in OSGi?
- 8. C# Union vs Contiene per gli elenchi di dati continui
- 9. Qual è la best practice per gli elenchi di sola lettura in NHibernate
- 10. Unisci gli elenchi per valore
- 11. lstrip(), rstrip() per gli elenchi
- 12. Buona struttura dati per la conversione dell'unità?
- 13. Qual è il trasporto sottostante per D-Bus?
- 14. Java: qual è la migliore struttura di implementazione per Graph?
- 15. Cosa fa questa notazione per gli elenchi in Python: "someList [:]"?
- 16. Come indicizzare gli elenchi annidati in Python?
- 17. In che modo Python memorizza gli elenchi internamente?
- 18. Python "best practice formattazione" per gli elenchi, dizionario, ecc
- 19. Qual è la migliore struttura dati per rappresentare una scacchiera quando la velocità è la preoccupazione principale?
- 20. Qual è la migliore struttura di database per mantenere i dati multilingue?
- 21. Qual è la migliore struttura dati per il completamento automatico del testo?
- 22. Qual è la migliore struttura dati per rappresentare una matrice triangolare superiore in Java?
- 23. A * qual è la migliore struttura dati per il set aperto?
- 24. Confronto degli elenchi Python
- 25. La migliore struttura dati per i dati della serie storica
- 26. Equivale a rindex per gli elenchi in Python
- 27. Qual è la differenza tra un tipo di dati astratto (ADT) e una struttura dati?
- 28. Struttura dati per processo decisionale Markov
- 29. Il linguaggio "in" di python è predisposto per thread-safe per gli elenchi?
- 30. Qual è la struttura di un flusso video?
due opzioni: 1) solo curiosità, o 2) ottimizzazione prematura. – flybywire
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
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