Confronto velocità di accesso dizionario con chiave intera contro chiave stringa

Question

Ho un ampio dizionario da cui devo cercare valori molte volte. Le mie chiavi sono numeri interi ma rappresentano etichette quindi non devono essere aggiunte, sottratte, ecc ... Ho finito per provare a valutare il tempo di accesso tra la chiave di stringa e il dizionario di chiavi intero e qui è il risultato.

from timeit import Timer 

Dint = dict() 
Dstr = dict() 

for i in range(10000): 
    Dint[i] = i 
    Dstr[str(i)] = i 


print 'string key in Dint', 
print(Timer("'7498' in Dint", "from __main__ import Dint").timeit(100000000)) 
print 'int key in Dint', 
print(Timer("7498 in Dint", "from __main__ import Dint").timeit(100000000)) 
print 'string key in Dstr', 
print(Timer("'7498' in Dstr", "from __main__ import Dstr").timeit(100000000)) 
print 'int key in Dstr', 
print(Timer("7498 in Dstr", "from __main__ import Dstr").timeit(100000000)) 

che produce leggere variazioni tra le esecuzioni riprodotte ogni volta:

string key in Dint 4.5552944017 
int key in Dint 7.14334390267 
string key in Dstr 6.69923791116 
int key in Dstr 5.03503126455 

vuol dimostrare che utilizzando il dizionario con le stringhe come chiavi è più veloce per l'accesso che con numeri interi come chiavi?

Answer 1

L'implementazione di CPython dict è infatti ottimizzata per ricerche di chiavi stringa. Esistono due diverse funzioni, lookdict e lookdict_string (lookdict_unicode in Python 3), che possono essere utilizzate per eseguire ricerche. Python utilizzerà la versione ottimizzata per le stringhe fino alla ricerca di dati non stringa, dopodiché verrà utilizzata la funzione più generale. È possibile esaminare l'implementazione effettiva scaricando l'origine di CPython e leggendo tramite dictobject.c.

Come risultato di questa ottimizzazione le ricerche sono più veloci quando uno dict ha tutte le chiavi di stringa.

Answer 2

Ho paura che i tuoi tempi non si dimostrino molto.

Il test per la stringa in Dint è il più veloce: in generale un test per tutto ciò che non è in un dizionario è abbastanza probabile che sia veloce, ma è solo perché sei stato fortunato e la prima volta hai colpito una cella vuota in modo che la ricerca potesse terminare. Se sei stato sfortunato e hai scelto un valore che ha colpito una o più celle complete, allora potrebbe finire più lentamente dei casi che effettivamente trovano qualcosa.

Il test per una stringa arbitraria in un dizionario deve calcolare il codice hash per la stringa. Ciò richiede tempo proporzionale alla lunghezza della stringa, ma Python ha un trucco accurato e lo calcola solo una volta per ogni stringa. Poiché si usa sempre la stessa stringa nel test di cronometraggio, il tempo impiegato per calcolare l'hash viene perso poiché avviene solo la prima volta e non le altre 99999999 volte. Se stavate usando una stringa diversa ogni volta otterreste un risultato molto diverso.

Python ha ottimizzato il codice per i dizionari in cui le chiavi sono stringhe. Nel complesso dovresti scoprire che usare le chiavi di stringa dove usi le stesse chiavi più volte è leggermente più veloce, ma se devi continuare a convertire gli interi in stringa prima della ricerca, perderai questo vantaggio.