Qual è il modo più efficiente per cercare un elenco milioni di volte?

Question

So che il modo semplice per cercare sarebbe quello di avere una lista contenente le stringhe, e fare semplicemente if string in list, ma rallenta, e ho sentito che le chiavi del dizionario non hanno praticamente alcun rallentamento con set di grandi dimensioni a causa del fatto che sono non ordinato

Tuttavia, non ho bisogno di ulteriori informazioni relative agli articoli, quindi è un po 'sbagliato creare un dizionario solo per tenere i tasti e impostare i valori su None.

C'è qualcosa che posso usare che funge da tasti del dizionario in termini di velocità, ma si comporta come una lista?

Ecco un rapido esempio:

import time, random 

totalRange = 100000 
searchFor = 5000 

#Create a list of 10 million characters 
searchableList = [] 
for i in range(totalRange): 
    searchableList.append(random.randint(0, totalRange)) 

#Create dictonary with keys set to 'None' 
searchableDict = {} 
for i in searchableList: 
    searchableDict[i] = None 

searchableSet = set(searchableList) 

#Search list 
startTime = time.time() 
numberMatches = 0 
for number in range(searchFor): 
    if number in searchableList: 
     numberMatches += 1 
print numberMatches, time.time()-startTime 

#Search dictionary keys 
startTime = time.time() 
numberMatches = 0 
for number in range(searchFor): 
    if number in searchableDict: 
     numberMatches += 1 
print numberMatches, time.time()-startTime 

#Search set 
startTime = time.time() 
numberMatches = 0 
for number in range(searchFor): 
    if number in searchableSet: 
     numberMatches += 1 
print numberMatches, time.time()-startTime 

Qui ci sono le uscite di tempo:

List: 18.8 seconds 
Set: 0.002 seconds 
Dictionary: 0.0009 seconds 

Anche se insieme è molto più veloce di una lista, il dizionario è ancora due volte più veloce, in modo da Mi chiedo se c'è qualcos'altro che non so. Usare un dizionario non sarebbe male, immagino che ci fosse un modo più semplice per farlo rispetto allo dictionary[key]=None.

Edit in base alla risposta del iCodez:

test quando totalRange=1000000 e searchFor=50000 (10 volte maggiore):

List = 20 minutes and still going 
Dictionary = 0.023 seconds 
Set = 0.02 seconds 
Set.intersection = 0.008 seconds 

Con più calcoli sembra insiemi e dizionari hanno un rendimento molto simile, ma la Il modo set.intersetion è chiaramente molto migliore.

Answer 1

è necessario utilizzare un set in questo caso. I set hanno lo stesso tempo di ricerca dei dizionari (constant), ma sono costituiti da singoli elementi anziché coppie chiave/valore. Quindi, ottieni la stessa velocità per meno memoria e una migliore rappresentazione dei dati.

---

Inoltre, si dovrebbe migliorare l'efficienza utilizzando set.intersection invece di un ciclo for:

numberMatches = len(searchableSet.intersection(xrange(searchFor))) 

Noterete anche che ho sostituito con rangexrange. Ciò impedisce a Python di creare un elenco non necessario e quindi di sprecare memoria.

Answer 2

uso

a_dict = dict.fromkeys(my_text.split())