Dove posso trovare la complessità temporale e spaziale dei tipi di sequenza incorporati in Python

Question

Non sono riuscito a trovare una fonte per queste informazioni, a meno di esaminare personalmente il codice sorgente Python per determinare come funzionano gli oggetti.Qualcuno sa dove potrei trovarlo online?

Answer 1

Controlla il Complessità temporale pagina sul wiki py dot org.Copre set/dicts/lists/etc almeno per quanto riguarda la complessità temporale.

Answer 2

Raimondo D.Hettinger lo fa un ottimo discorso (diapositive) sulle raccolte integrate di Python denominate "Core Python Containers - Under the Hood".La versione che ho visto si concentrava principalmente su set E dict, Ma list era coperto anch'esso.

Ci sono anche alcune foto delle diapositive pertinenti di EuroPython in un blog.

Ecco un riassunto dei miei appunti su list:

• Memorizza gli elementi come una serie di puntatori.L'abbonamento costa O(1) tempo.Aggiungere i costi ammortizzati O(1) tempo.Inserire i costi O(n) tempo.
• Cerca di evitare memcpy quando si cresce per sovraallocazione.Molte liste piccole sprecano molto spazio, ma le liste grandi non sprecano mai più del 12,5% circa a causa della sovraallocazione.
• Alcune operazioni predimensionano.Gli esempi forniti sono stati range(n), map(), list(), [None] * n, e affettare.
• Quando si restringe, l'array è realloced solo quando spreca il 50% dello spazio. pop é economico.

Answer 3

Se stai chiedendo quello che penso tu stia chiedendo, puoi trovarli Qui...pagina 476 e seguenti.

È scritto sulle tecniche di ottimizzazione per Python;È principalmente la notazione Big-O dell'efficienza temporale e non molta memoria.