Trovare tutte le chiavi in ​​un dizionario da un elenco dato QUICKLY

Question

Ho un dizionario (potenzialmente piuttosto grande) e un elenco di chiavi "possibili". Voglio trovare rapidamente quali chiavi hanno valori corrispondenti nel dizionario. Ho trovato molte discussioni su single valori del dizionario here e here, ma nessuna discussione sulla velocità o più voci.

Mi sono inventato quattro modi e, per i tre che funzionano meglio, paragono la loro velocità su campioni di dimensioni diverse di seguito: ci sono metodi migliori? Se le persone possono suggerire contendenti sensibili, li sottoporrò anche all'analisi sottostante.

liste di esempio e dizionari vengono creati nel modo seguente:

import cProfile 
from random import randint 

length = 100000 

listOfRandomInts = [randint(0,length*length/10-1) for x in range(length)] 
dictionaryOfRandomInts = {randint(0,length*length/10-1): "It's here" for x in range(length)} 

 

Metodo 1: la parola chiave 'in':

def way1(theList,theDict): 
    resultsList = [] 
    for listItem in theList: 
     if listItem in theDict: 
      resultsList.append(theDict[listItem]) 
    return resultsList 

cProfile.run('way1(listOfRandomInts,dictionaryOfRandomInts)') 

32 chiamate di funzione in 0.018 secondi

 

Metodo 2: gestione degli errori:

def way2(theList,theDict): 
    resultsList = [] 
    for listItem in theList: 
     try: 
      resultsList.append(theDict[listItem]) 
     except: 
      ; 
    return resultsList 

cProfile.run('way2(listOfRandomInts,dictionaryOfRandomInts)') 

32 chiamate di funzione in 0.087 secondi

 

Metodo 3: impostare intersezione:

def way3(theList,theDict): 
    return list(set(theList).intersection(set(theDict.keys()))) 

cProfile.run('way3(listOfRandomInts,dictionaryOfRandomInts)') 

26 chiamate di funzione in 0,046 secondi

 

Metodo 4: Utilizzare Naive di dict.keys():

Questo è un ammonimento - è stato il mio primo tentativo e di gran lunga il più lento !

def way4(theList,theDict): 
    resultsList = [] 
    keys = theDict.keys() 
    for listItem in theList: 
     if listItem in keys: 
      resultsList.append(theDict[listItem]) 
    return resultsList 

cProfile.run('way4(listOfRandomInts,dictionaryOfRandomInts)') 

12 chiamate di funzione in 248.552 secondi

 

EDIT: Portare i suggerimenti dati nelle risposte nella stessa struttura che ho usato per la coerenza. Molti hanno notato che in Python 3.x si possono ottenere più guadagni in termini di prestazioni, in particolare i metodi basati sulla comprensione delle liste. Mille grazie per tutto l'aiuto!

Metodo 5: Modo migliore di eseguire intersezione (grazie jonrsharpe):

def way5(theList, theDict): 
    return = list(set(theList).intersection(theDict)) 

25 chiamate di funzione tra 0.037 secondi

 

Metodo 6: Elenco comprensione (grazie jonrsharpe):

def way6(theList, theDict): 
    return [item for item in theList if item in theDict] 

24 chiamate di funzione in 0.020 secondi

 

Metodo 7: Utilizzo il keywor & d (grazie jonrsharpe):

funzione

def way7(theList, theDict): 
    return list(theDict.viewkeys() & theList) 

25 chiama 0,026 secondi

Per i metodi 1-3 e 5-7 li ho contati come sopra ed elenco/dizionari di lunghezza 1000, 10000, 100000, 1000000, 10000000 e 100000000 e mostrano un grafico del tempo di registrazione. In tutte le lunghezze, il metodo di intersezione e in-statement funziona meglio. I gradienti sono tutti circa 1 (forse un po 'più alti), indicando la scala O (n) o forse leggermente super-lineare.

Answer 1

di un paio di altri metodi che ho provato, il più veloce è stato un semplice elenco di comprensione:

def way6(theList, theDict): 
    return [item for item in theList if item in theDict] 

Questo esegue lo stesso processo come il vostro approccio più veloce, way1, ma in modo più rapido . Per confronto, il modo basata su più veloce set era

def way5(theList, theDict): 
    return list(set(theList).intersection(theDict)) 

timeit risultati:

>>> import timeit 
>>> setup = """from __main__ import way1, way5, way6 
from random import randint 
length = 100000 
listOfRandomInts = [randint(0,length*length/10-1) for x in range(length)] 
dictionaryOfRandomInts = {randint(0,length*length/10-1): "It's here" for x in range(length)} 
""" 
>>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
14.550477756582723 
>>> timeit.timeit('way5(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
19.597916393388232 
>>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
13.652289059326904 

---

avendo aggiunto @ suggerimento di abarnert:

def way7(theList, theDict): 
    return list(theDict.viewkeys() & theList) 

e rieseguire la sincronizzazione I ora ricevi:

>>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
13.110055883138497 
>>> timeit.timeit('way5(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
17.292466681101036 
>>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
14.351759544463917 
>>> timeit.timeit('way7(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
17.206370930653392 

way1 e way6 hanno cambiato i luoghi, in modo da ri-correva ancora:

>>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
13.648176054011941 
>>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 
13.847062579316628 

Quindi sembra che il metodo di cui è più lento rispetto alla lista, ma la differenza tra la lista e di lista è (sorprendentemente, per me almeno) è un po 'variabile. Direi di sceglierne uno e non preoccupiamoci, a meno che non diventi un vero collo di bottiglia più tardi.

Answer 2

In primo luogo, penso che tu sia in 2.7, quindi farò la maggior parte di questo con 2.7. Ma vale la pena notare che se sei veramente interessato a ottimizzare il tuo codice, il ramo 3.x continua a ottenere miglioramenti delle prestazioni e il ramo 2.x non lo farà mai. E perché stai usando CPython invece di PyPy?

---

Comunque, alcuni ulteriori micro-ottimizzazioni da provare (in aggiunta a quelle in jonrsharpe's answer:

---

attributo cache e/o ricerche globali variabili locali (si chiama LOAD_FAST per un motivo) . Ad esempio:

def way1a(theList, theDict): 
    resultsList = [] 
    rlappend = resultsList.append 
    for listItem in theList: 
     if listItem in theDict: 
      rlappend(theDict[listItem]) 
    return resultsList 

In [10]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 13.2 ms per loop 
In [11]: %timeit way1a(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 12.4 ms per loop 

Ma per alcuni metodi speciali operatore, come __contains__ e __getitem__, che non può essere wor sto facendo. Naturalmente non si sa fino a quando si tenta:

def way1b(theList, theDict): 
    resultsList = [] 
    rlappend = resultsList.append 
    tdin = theDict.__contains__ 
    tdgi = theDict.__getitem__ 
    for listItem in theList: 
     if tdin(listItem): 
      rlappend(tdgi(listItem)) 
    return resultsList 

In [14]: %timeit way1b(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 12.8 ms per loop 

Nel frattempo, way6 risposta di Jon ottimizza già fuori dalla resultList.append interamente utilizzando un listcomp, e abbiamo appena visto che ottimizzando le ricerche che non hanno probabilmente non lo farà Aiuto. Soprattutto in 3.x, dove la comprensione verrà compilata in una funzione a sé stante, ma anche nel 2.7 non aspetterei alcun beneficio, per le stesse ragioni del ciclo esplicito. Ma proviamo solo per essere sicuri:

def way6(theList, theDict): 
    return [theDict[item] for item in theList if item in theDict] 
def way6a(theList, theDict): 
    tdin = theDict.__contains__ 
    tdgi = theDict.__getitem__ 
    return [tdgi(item) for item in theList if tdin(item)] 

In [31]: %timeit way6(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 14.7 ms per loop 
In [32]: %timeit way6a(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 13.9 ms per loop 

Sorprendentemente (almeno per me), questa volta ha effettivamente aiutato. Non so perché.

Ma quello che stavo veramente Impostazione per era questa: un altro vantaggio di trasformare sia l'espressione di filtro e l'espressione di valore in chiamate di funzione è che possiamo usare filter e map:

def way6b(theList, theDict): 
    tdin = theDict.__contains__ 
    tdgi = theDict.__getitem__ 
    return map(tdgi, filter(tdin, theList)) 
def way6c(theList, theDict): 
    tdin = theDict.__contains__ 
    tdgi = theDict.__getitem__ 
    return map(tdgi, ifilter(tdin, theList)) 

In [34]: %timeit way6b(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 10.7 ms per loop 
In [35]: %timeit way6c(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 13 ms per loop 

Ma questo guadagno è in gran parte 2.x-specifico; 3.x ha comprensioni più veloci, mentre il suo list(map(filter(…))) è più lento di 2.x's map(filter(…)) o map(ifilter(…)).

---

Non è necessario convertire entrambi i lati di un'intersezione impostata in un set, solo il lato sinistro; il lato destro può essere qualsiasi iterabile, e un dict è già un iterable delle sue chiavi.

Ma, ancora meglio, vista la chiave di un dict (dict.keys in 3.x, dict.keyview in 2.7) è già un oggetto set-like, e uno sostenuto dalla tabella hash del dict, quindi non c'è bisogno di trasformare qualsiasi cosa. (Non ha la stessa interfaccia, non ha il metodo & ma il suo operatore & accetta valori diversi da set, che ha un metodo & che accetta solo set, ma il suo & prende solo set. Questo è fastidioso, ma ci interessa solo le prestazioni qui, giusto?)

def way3(theList,theDict): 
    return list(set(theList).intersection(set(theDict.keys()))) 
def way3a(theList,theDict): 
    return list(set(theList).intersection(theDict)) 
def way3b(theList,theDict): 
    return list(theDict.viewkeys() & theList) 

In [20]: %timeit way3(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 23.7 ms per loop 
In [20]: %timeit way3a(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 15.5 ms per loop 
In [20]: %timeit way3b(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 15.7 ms per loop 

Questo ultimo non ha aiutato (anche se usando Python 3.4 invece di 2.7, è stata del 10% più veloce ...), ma il primo sicuramente fatto.

Nella vita reale, si potrebbe anche voler confrontare le dimensioni delle due raccolte per decidere quale viene impostato, ma qui che le informazioni sono statiche, quindi non ha senso scrivere il codice per testarlo.

---

In ogni caso, il mio risultato più veloce è stato il map(filter(…)) il 2.7, da un buon margine di. Il 3.4 (che non ho mostrato qui), il listcomp di Jon è stato il più veloce (anche corretto per restituire i valori piuttosto che i tasti), e più veloce di uno qualsiasi dei 2.7 metodi. Inoltre, l'operazione set più veloce della 3.4 (usando la vista chiave come set e l'elenco come iterable) erano molto più vicini ai metodi iterativi rispetto a 2.7.

Answer 3

$ ipython2 # Apple CPython 2.7.6 
[snip] 
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 13.8 ms per loop 

$ python27x -m ipython # custom-built 2.7.9 
[snip] 
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 13.7 ms per loop 

$ ipython3 # python.org CPython 3.4.1 
[snip] 
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 
100 loops, best of 3: 12.8 ms per loop  

Quindi, questo è un aumento di velocità 8% semplicemente utilizzando un secondo Python. (E l'accelerazione era più vicina al 20% sulle versioni listcomp e dict-key-view.) E non è perché il 2.7 di Apple è cattivo o altro, è solo che 3.x ha continuato a ottenere ottimizzazioni negli ultimi 5 anni, mentre 2.7 non ha (e non lo farà mai più).

E intanto:

$ ipython_pypy # PyPy 2.5.0 Python 2.7.8 
[snip] 
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 
1000000000 loops, best of 3: 1.97 ns per loop 

Questo è un aumento di velocità 7000000x semplicemente digitando 5 caratteri aggiuntivi. :)

Sono sicuro che sta imbrogliando qui. O la JIT ha implicitamente memo- rizzato il risultato, o si è notato che non ho nemmeno guardato il risultato e ho spinto la catena e ho capito che non aveva bisogno di fare nessuno dei passi, o qualcosa del genere. Ma in realtà ciò accade nella vita reale a volte; Ho avuto un enorme pasticcio di codice che ha trascorso 3 giorni di debugging e cercando di ottimizzare prima di rendermi conto che tutto ciò che faceva era inutile ...

In ogni caso, le accelerazioni dell'ordine di 10x sono piuttosto tipiche di PyPy anche quando può imbrogliare Ed è molto più facile che modificare le attribuzioni degli attributi o invertire l'ordine di chi viene trasformato in un set del 5%.

Jython è più imprevedibile, a volte quasi veloce come PyPy, a volte molto più lento di CPython. Sfortunatamente, timeit è rotto in Jython 2.5.3, e ho appena rotto il mio Jython 2.7 completamente aggiornando da rc2 a rc3, quindi ... nessun test oggi. Allo stesso modo, IronPython è fondamentalmente Jython rifatto su una VM diversa; di solito è più veloce, ma di nuovo imprevedibile. Ma la mia versione attuale di Mono e la mia versione attuale di IronPython non stanno giocando bene insieme, quindi non ci sono nemmeno test.