Prestazioni di iteratore del dizionario Python

Question

Quando si lavora con i dizionari in Python, this page dice che la complessità temporale dell'iterazione attraverso l'elemento del dizionario è O(n), dove n è la dimensione più grande del dizionario.

Tuttavia, non penso che esista un modo ovvio per scorrere gli elementi di una tabella hash. Posso assumere una buona prestazione di dict.iteritems() durante l'iterazione attraverso l'elemento di una tabella hash, senza troppo carico?

Poiché i dizionari sono molto utilizzati in Python, presumo che questo sia implementato in modo intelligente. Eppure, ho bisogno di essere sicuro.

Answer 1

Se si guarda alla notes on Python's dictionary source code, penso che i punti rilevanti sono i seguenti:

Tali metodi (di iterazione e di quotazione chiave) un ciclo su ogni potenziale ingresso

quante voci potenziali saranno ci sarà, in funzione della dimensione maggiore (il maggior numero di chiavi mai memorizzate in quel dizionario)? Guarda le due sezioni seguenti nello stesso documento:

Carico dizionario massimo in PyDict_SetItem. Attualmente impostato su 2/3

Tasso di crescita al raggiungimento del carico massimo. Attualmente impostato su * 2.

Questo sembra indicare che la scarsità di un dizionario sta per essere da qualche parte circa 1/3 ~ 2/3 (a meno che il tasso di crescita è impostato su * 4, allora è 1/6 ~ 2/3). Quindi fondamentalmente controllerai fino a 3 (o 6 se * 4) potenziali voci per ogni chiave.

Ovviamente, se si tratta di 3 voci o 1000, è ancora O (n), ma 3 sembra un fattore costante abbastanza accettabile.

Tra l'altro qui sono il resto della documentazione fonte &, compresa quella del DictObject:

http://svn.python.org/projects/python/trunk/Objects/