efficienza delle chiavi lunghe (str) nel dizionario python

Question

Sto analizzando alcuni xml (con qualche codice Python 3.4) e voglio recuperare sia il testo da un nodo che il suo attributo id. Esempio: <li id="12345"> Some text here </li> Il mio codice corrente è strutturato attorno al solo testo (sto ora aggiungendo l'id, ma non ne avevo bisogno prima). Sto scorrendo un elenco di testo/frasi e poi procedo a fare qualcosa. Quindi ho pensato di creare un dizionario con il testo/frase come chiave e questo attributo id come valore.

Tuttavia, questo non sembra molto efficiente. Il testo può essere un intero paragrafo, rendendo la chiave molto lunga. Mentre l'id è sempre di una lunghezza abbastanza limitata (ma comunque di tipo str sebbene, ad esempio alcuni caratteri alfa seguiti da alcune cifre). Ma rendendo gli id ​​la chiave e il testo il valore richiede una certa riscrittura del codice. Tutto non è molto problematico, ma questo mi ha fatto pensare: quanto sarebbe inefficiente avere il testo (potenzialmente un intero paragrafo) come chiave, rispetto a un id come "ulp_887362487687678" come chiave?

Posso solo creare due dizionari inversi (uno con ID come chiave, l'altro con testo come chiave) e confrontare la costruzione e la ricerca e tutto. E ho anche trovato alcuni argomenti sul limite di lunghezza della chiave (Do Dictionaries have a key length limit?). Ma mi sto semplicemente chiedendo quali sono i tuoi pensieri su questo. Avere delle chiavi così lunghe nel tuo modo di dire qualcosa che vuoi assolutamente evitare, o non è un grosso problema? Se potessi condividere alcuni pro/contro, sarebbe fantastico!

Answer 1

No, la lunghezza della stringa Python ha difficilmente un impatto sulle prestazioni del dizionario. L'unica influenza che può avere la lunghezza della stringa è la funzione hash() utilizzata per mappare la chiave in uno slot di tabella hash.

lunghezza della stringa ha un impatto minimo sulle prestazioni del hash():

>>> import random 
>>> from timeit import timeit 
>>> from string import ascii_letters 
>>> generate_text = lambda len: ''.join([random.choice(ascii_letters) for _ in xrange(len)]) 
>>> for i in range(8): 
...  length = 10 + 10 ** i 
...  testword = generate_text(length) 
...  timing = timeit('hash(t)', 'from __main__ import testword as t') 
...  print 'Length: {}, timing: {}'.format(length, timing) 
... 
Length: 11, timing: 0.061537027359 
Length: 20, timing: 0.0796310901642 
Length: 110, timing: 0.0631730556488 
Length: 1010, timing: 0.0606122016907 
Length: 10010, timing: 0.0613977909088 
Length: 100010, timing: 0.0607581138611 
Length: 1000010, timing: 0.0672461986542 
Length: 10000010, timing: 0.080118894577 

mi sono fermato a generare una stringa di 10 milioni di caratteri, perché non poteva essere disturbati in attesa che il mio computer portatile per generare un 100 milioni stringa di caratteri.

Le temporizzazioni sono praticamente costanti, poiché il valore viene effettivamente memorizzato nella cache dell'oggetto stringa una volta calcolato.