Ricerca efficiente del dizionario?

Question

Ho avuto una breve domanda sull'efficienza della ricerca tramite i dizionari grandi in in Python. Sto leggendo un grande file separato da virgola e ricevo una chiave e un valore da ogni riga. Se la mia chiave è già nel dizionario, aggiungo il valore al valore elencato nel dizionario, se la chiave non esiste nel dizionario, aggiungo semplicemente il valore. In precedenza ero utilizzare questo:

if key in data_dict.keys(): 
    add values 
else: 
    data_dict[key] = value 

Questo inizia piuttosto veloce, ma come il dizionario cresce diventa sempre più lento, al punto in cui non posso usarlo affatto. Ho cambiato il mio modo di cercare la chiave nel dizionario a questo:

try: 
    # This will fail if key not present 
    data_dict[keyStr] = input_data[keyStr] + load_val 
except: 
    data_dict[keyStr] = load_val 

Questa è infinitamente più veloce, e in grado di leggere/scrivere oltre 350.000 linee di codice in 3 secondi.

La mia domanda era: perché il comando if key in data_dict.keys(): richiede molto più tempo della chiamata a try: data_dict[keyStr]? E perché Python non dovrebbe utilizzare l'istruzione try durante la ricerca di una chiave in un dizionario?

Answer 1

Il problema è che per ogni test viene generato un nuovo elenco di chiavi con .keys(). Man mano che la lista delle chiavi si allunga, il tempo richiesto aumenta. Anche as noted by dckrooney, la ricerca della chiave diventa lineare invece di sfruttare la struttura della tabella hash del dizionario.

Sostituire con:

if key in data_dict: 

Answer 2

Questo non risponde alla domanda, ma piuttosto la evita. Prova a utilizzare collections.defaultdict. Non è necessario il if/else o try/except.

from collections import defaultdict 

data_dict = defaultdict(list) 
for keyStr, load_val in data: 
    data_dict[keyStr].append(load_val) 

Answer 3

Questo perché data_dict.keys() restituisce una lista contenente le chiavi nel dizionario (almeno in Python 2.x). Quale, per trovare se una chiave è nella lista, richiede una ricerca lineare.

Considerando che, tentare di accedere a un elemento del dict sfrutta direttamente le fantastiche proprietà dei dizionari in modo che l'accesso sia quasi istantaneo.

Answer 4

C'è qualcosa di simile alla funzione di prova che dovrebbe aiutare: dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val 

Answer 5

data_dict.keys() restituisce una lista non ordinata di chiavi nel dizionario. Così ogni volta che controlli se una determinata chiave è nel dizionario, stai facendo una ricerca lineare attraverso l'elenco di chiavi (un'operazione O (n)). Più lunga è la tua lista, più tempo è necessario per cercare una determinata chiave.

Contrasto a data_dict[keyStr]. Questo esegue una ricerca hash, che è un'operazione O (1). Non dipende (direttamente) dal numero di chiavi nel dizionario; anche se aggiungi più chiavi, il tempo di controllare se una determinata chiave è presente nel dizionario rimane costante.

Answer 6

Si può anche semplicemente usare

if key in data_dict: 

invece di

if key in data_dict.keys(): 

Come accennato, il primo è una ricerca diretta hash - la destinato offset viene calcolato direttamente, e quindi controllato - è grosso modo O (1), mentre il controllo delle chiavi è una ricerca lineare, che è O (n).

In [258]: data_dict = dict([(x, x) for x in range(100000)]) 

In [259]: %timeit 999999 in data_dict.keys() 
100 loops, best of 3: 3.47 ms per loop 

In [260]: %timeit 999999 in data_dict 
10000000 loops, best of 3: 49.3 ns per loop 

Answer 7

Indietro nei vecchi giorni abbiamo usato setdefault:

data_dict.setdefault(keyStr, []).append(load_val) 

Answer 8

Come molti altri hanno notato, il problema sta nel fatto che key in data_dict.keys() utilizza il non ordinata list restituito dal metodo keys() (in Python 2.x), che prende linear timeO (n) per cercare abbastanza, il che significa che il tempo di esecuzione aumenta in modo lineare con le dimensioni del dizionario, oltre a generare l'elenco delle chiavi stesso richiederà più tempo e più a mano a mano che le dimensioni aumentano.

D'altra parte, key in data_dict richiede solo tempo costante O (1), in media, per eseguire una ricerca indipendentemente dalle dimensioni del dizionario, perché internamente fa un look-up hash table. Inoltre, questa tabella hash esiste già dalla sua parte della rappresentazione interna dei dizionari e, pertanto, non deve essere generata prima di utilizzarla.

Python non lo fa automaticamente perché l'operatore in conosce solo il tipo dei suoi due operandi, non le loro origini, quindi non può ottimizzare automaticamente il primo caso in cui tutto ciò che vede è la chiave e un elenco.

Tuttavia, in questo caso il problema della velocità di ricerca può probabilmente essere evitato del tutto memorizzando i dati in una versione specializzata di un dizionario chiamato defaultdict trovato nel modulo integrato collections. Ecco come il codice potrebbe apparire se si è utilizzato uno:

from collections import defaultdict 

input_data = defaultdict(float) # (guessing factory type) 
... 
data_dict[keyStr] = input_data[keyStr] + load_val 

Quando non c'è alcuna voce preesistente per input_data[keyStr] uno sarà generato automaticamente con un valore di default (0.0 per float in questo esempio). Come puoi vedere, il codice è più breve e molto probabilmente più veloce, il tutto senza la necessità di alcun test if o gestione delle eccezioni.