Le moyen le plus efficace pour une recherche/recherche dans une liste énorme (python)

Question

- J'ai juste analysé un gros fichier et j'ai créé une liste contenant 42.000 chaînes/mots. Je veux interroger [contre cette liste] pour vérifier si un mot/une chaîne lui appartient. Donc, ma question est:

Quel est le moyen le plus efficace pour une telle recherche?

Une première approche consiste à trier la liste (list.sort()), puis il suffit d'utiliser

>> if word in list: print 'word' 

qui est vraiment trivial et je suis sûr qu'il ya une meilleure façon de le faire. Mon but est d'appliquer une recherche rapide qui trouve si une chaîne donnée est dans cette liste ou non. Si vous avez des idées d'une autre structure de données, elles sont les bienvenues. Pourtant, je veux éviter pour l'instant des structures de données plus sophistiquées comme Tries etc. Je suis intéressé à entendre des idées (ou des astuces) sur les recherches rapides ou toute autre méthode de la bibliothèque python qui pourrait faire la recherche plus rapidement que la simple in.

Et aussi je veux connaître l'index de l'élément de recherche

Answer 1

Ne pas créer un list, créez un set. Il fait des recherches à temps constant.

Si vous ne voulez pas l'en-tête de mémoire d'un ensemble, conservez une liste triée et recherchez-la à l'aide du module bisect.

from bisect import bisect_left 
def bi_contains(lst, item): 
    """ efficient `item in lst` for sorted lists """ 
    # if item is larger than the last its not in the list, but the bisect would 
    # find `len(lst)` as the index to insert, so check that first. Else, if the 
    # item is in the list then it has to be at index bisect_left(lst, item) 
    return (item <= lst[-1]) and (lst[bisect_left(lst, item)] == item) 

Answer 2

Un point sur les jeux par rapport aux listes qui n'a pas été pris en considération: dans « l'analyse d'un grand fichier » on peut s'y attendre à devoir gérer dupliquer mots/chaînes. Vous n'avez pas mentionné cela du tout.

De toute évidence, l'ajout de nouveaux mots à un ensemble supprime les doublons à la volée, sans coût supplémentaire de temps processeur ou de temps de réflexion. Si vous essayez avec une liste, cela finit par O (N ** 2). Si vous ajoutez tout à une liste et supprimez les doublons à la fin, la façon la plus intelligente de le faire est ... tambour roll ... utiliser un ensemble, et l'avantage (petit) de la mémoire d'une liste est susceptible d'être submergé par le doublons.

Answer 3

Si vous prévoyez des recherches complexes plus tard - et par complexe je ne veux pas trivial - je vous recommande de le stocker dans sqlite3.

Answer 4

En utilisant ce programme, il ressemble à dicts sont les Fastes, deuxième ensemble, liste des bi_contains troisième:

from datetime import datetime 

def ReadWordList(): 
    """ Loop through each line in english.txt and add it to the list in uppercase. 

    Returns: 
    Returns array with all the words in english.txt. 

    """ 
    l_words = [] 
    with open(r'c:\english.txt', 'r') as f_in: 
     for line in f_in: 
      line = line.strip().upper() 
      l_words.append(line) 

    return l_words 

# Loop through each line in english.txt and add it to the l_words list in uppercase. 
l_words = ReadWordList() 
l_words = {key: None for key in l_words} 
#l_words = set(l_words) 
#l_words = tuple(l_words) 

t1 = datetime.now() 

for i in range(10000): 
    #w = 'ZEBRA' in l_words 
    w = bi_contains(l_words, 'ZEBRA') 

t2 = datetime.now() 
print('After: ' + str(t2 - t1)) 

# list = 41.025293 seconds 
# dict = 0.001488 seconds 
# set = 0.001499 seconds 
# tuple = 38.975805 seconds 
# list with bi_contains = 0.014000 seconds