È sempre più veloce usare la stringa come chiave in un dict?

Question

Su questo page, vedo qualcosa di interessante:

Si noti che non v'è un fast-percorso per dicts che (in pratica) trattare solo con le chiavi str; questo non influenza la complessità algoritmica, ma può influenzare in modo significativo i fattori costanti: quanto velocemente un programma tipico finisce.

Quindi cosa significa esattamente?

Significa utilizzare la stringa poiché la chiave è sempre più veloce?

Se sì, perché?

Aggiornamento:

Grazie per i suggerimenti circa l'ottimizzazione! Ma in realtà sono più interessato alla pura verità, che se o quando dovremmo fare l'ottimizzazione.

Aggiornamento 2:

Grazie per le grandi risposte, io cito il contenuto dal link fornita da @DaveWebb qui:

" ...

ma_lookup è inizialmente impostato sulla funzione lookdict_string (rinominata lookdict_unicode in 3.0), che come Suppone che sia le chiavi nel dizionario sia la chiave ricercata siano standard di PyStringObject. È quindi in grado di effettuare un paio di ottimizzazioni, come ad esempio l'attenuazione di vari controlli degli errori, poiché il confronto tra stringhe e stringhe non genera mai eccezioni. Inoltre, non è necessario effettuare confronti tra oggetti ricchi, il che significa evitare di chiamare PyObject_RichCompareBool e utilizzare sempre _PyString_Eq direttamente.

... "

Inoltre, per i numeri esperimento, penso che la dimensione della differenza sarà ancora più grande se non c'è int-to-stringa di conversione

Answer 1

Il codice C che sottende il dict Python è ottimizzato per le chiavi stringa. You can read about this here (e nel libro si riferisce al blog).

Se il runtime di Python sa che il proprio dtt contiene solo chiavi di stringa, può fare cose come non tener conto degli errori che non si verificano con un confronto tra stringhe e stringhe e ignorare gli operatori di confronto ricco. Ciò renderà il caso comune della chiave di stringa solo dict un po 'più veloce. (Aggiornamento: i tempi indicano che è più che un po '.)

Tuttavia, è improbabile che ciò cambierebbe significativamente il tempo di esecuzione della maggior parte dei programmi Python. Solo preoccuparsi di questa ottimizzazione se si sono misurate e trovate le ricerche dict come collo di bottiglia nel codice. As the famous quote says, "Premature optimization is the root of all evil."

L'unico modo per vedere come le cose molto più veloce realmente sono, è a tempo loro:

>>> timeit.timeit('a["500"]','a ={}\nfor i in range(1000): a[str(i)] = i') 
0.06659698486328125 
>>> timeit.timeit('a[500]','a ={}\nfor i in range(1000): a[i] = i') 
0.09005999565124512 

Quindi, utilizzando chiavi di stringa è di circa il 30% più veloce anche rispetto al int chiavi, e devo ammettere che ho è stato sorpreso dalle dimensioni della differenza.

Answer 2

Ciò penalizza solo il il tempo costante, è probabile che non importi affatto.L'unica volta che devi davvero ottimizzare è quando lavori con insiemi di dati molto grandi - il che non ha nulla da influenzare

Ciò che significa è che nei casi dove hai piccoli dizionari con stringhe come chiavi, Python sarà veloce - questo è un uso comune, quindi è stato ottimizzato per.

Come sottolinea Ignacio Vazquez-Abrams, è probabile che la conversione della chiave in una stringa costerà (molto) molto di più della leggera spinta che si potrebbe ottenere dal fatto che sia una stringa per il dict.

In breve, ciò che è rilevante per la vostra situazione - l'ottimizzazione dovrebbe essere fatta solo dove ce n'è bisogno, non prima.

Alcuni test:

python -m timeit -s "a={key: 1 for key in range(1000)}" "a[500]" 
10000000 loops, best of 3: 0.0773 usec per loop 

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[\"500\"]" 
10000000 loops, best of 3: 0.0452 usec per loop 

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[str(500)]" 
1000000 loops, best of 3: 0.244 usec per loop 

Come si può vedere, mentre il dict basato sulle stringhe è più veloce, convertendo la chiave è molto costoso in confronto, totalmente mitigare il guadagno (e poi alcuni).

Quindi sì, se i dati si sta utilizzando è solo usando come chiavi del dizionario, e quale formato il vostro negozio di loro in non importa, quindi le stringhe sono preferibili, in un piccolo dizionario. In pratica, questo è un caso molto raro (e probabilmente useresti già le stringhe).