Algorithme pour trouver un ensemble de mots dans une grande liste de mots

Question

Je cherche l'algorithme le plus rapide qui puisse trouver un ensemble de mots correspondant à un autre ensemble de mots dans une liste de 9 millions d'enregistrements. Problème: J'ai une liste avec près de 100 000 ensembles de mots et je dois rechercher une correspondance de chacun des ensembles de mots dans une autre liste de 9 millions d'ensembles de mots.

Ma solution actuelle va comme ceci, je lis tous les enregistrements (à partir d'un fichier texte) et je garde en mémoire (sous la forme d'un tableau, appelons-la 'liste de recherche'). Lors de la construction de ce tableau, je trier l'ensemble des mots par ordre alphabétique et une fois tous les ensembles de mots ajoutés, je trier la liste entière. Je fais la même chose avec l'autre grande liste, appelons cette 'liste de données'.

Maintenant, je parcourir sur chacun des éléments de ma liste de recherche et essayer de trouver une correspondance. Une fois qu'une correspondance est trouvée, je me souviens de la position à laquelle elle correspond et de la prochaine recherche que je fais à partir de la même position. Cela m'évite d'itéter toute la liste des données encore et encore pour chaque élément de la liste de recherche. Je suppose que c'est super rapide mais malheureusement, ce n'est pas le cas. Il faut presque 15 à 20 minutes pour compléter l'itération complète de la liste de recherche. Ceci est inacceptable.

Voici un extrait de mon code

int lastPointer = 0 
for(int i=0; i<search list.size(); i++){  
    def this_matched_out = [] 
    inmem_json_arr[i][0] 
    for(int j=lastPointer; j<data list.size(); j++){ 
     if(data list[j].containsAll(search list[i])){ 
      this_matched_out.add(data list[j]) 
      lastPointer = j 
     } 
    } 
    if(this_matched_out.size()>0) - println "found a match for search "+list[i] 
    else println "No match found for "+list[i] 
} 

Quelqu'un peut-il me suggérer un meilleur algorithme ou que je fais quelque chose de mal ici?

Answer 1

Utilisez une table de hachage. Une recherche prend O (1) temps, peu importe la taille de votre ensemble de mots.