Optimisation pour la comparaison d'éléments HashMap lors de l'écriture

Question

J'ai un fichier csv avec des noms proches de la ligne 845k.

Je souhaite comparer une chaîne de noms floue. J'ai utilisé l'implémentation Java fuzzy string matching de l'algorithme fuzzywuzzy de Python.

Mis en œuvre sous le code, il fonctionne parfaitement pour moi. Le problème est le temps de traitement à beaucoup. Chaque ligne de comparaison de temps dure près de 15 secondes avec les autres lignes. Ceci est 240 lignes pour une heure et tout le processus sera près de 6000 lignes. Et tout le processus sera fini en mois. Ceci est un temps de travail inacceptable.

J'ai besoin d'une technique ou d'une méthode d'optimisation. J'ai besoin de suggestion plutôt que de solution.

Que conseillez-vous pour le code ci-dessous?

BufferedReader br = new BufferedReader(new FileReader("data/names.csv")); 
BufferedWriter bw = new BufferedWriter(new FileWriter("data/similars.csv")); 
ConcurrentHashMap<Integer,String> map = new ConcurrentHashMap<Integer,String>(); 

String lines; 
while((lines = br.readLine()) != null){ 
    String[] line = lines.split("\\t",-1); 
    Integer nameId = Integer.parseInt(line[0]); 
    String name = line[1]; 
    map.put(nameId, name); 
} 

for (Map.Entry<Integer, String> entry1 : map.entrySet()) { 
    Integer nameId1 = entry1.getKey(); 
    String name1 = entry1.getValue(); 

    for (Map.Entry<Integer, String> entry2 : map.entrySet()) { 
     Integer nameId2 = entry2.getKey(); 
     if (nameId1 == nameId2) { 
      continue; 
     } 
     String name2 = entry2.getValue(); 
     int ratio = FuzzySearch.ratio(name1,name2); 
     if(ratio > 95){ 
      bw.write(nameId1 + "," + nameId2 + "\n"); 
     } 
    } 
    // For to prevent matching same pairs again 
    map.remove(nameId1); 
} 

Answer 1

1. Vous pouvez à la place Levenshtein algorithme à distance, peut-être vous donnera de meilleures performances. Ou essayez un autre algorithme. Fournir un lien vers Algoritm mise en œuvre
2. Il est préférable de ne pas comparer avec Integer ==, utilisez nameId1.intValue() == nameId2
3. Créer des threads N, où N est le nombre de cœurs. Mettez toutes vos lignes dans la file d'attente ConcurrentLinkedQueue. Laissez les threads interroger la file d'attente, prendre un mot, faire de la compassion, une fois terminé - écrire dans le fichier sous la section synchronisée. Cela vous permettra d'utiliser tous vos cœurs sur votre PC, pas seulement 1
4. Pourquoi cela prend autant de temps, peut-être que vous avez des restrictions de mémoire, ce qui oblige le GC à manger les cycles de votre processeur et à affecter les performances.
5. Vous pouvez appliquer une optimisation mineure, disons que si elle est différente entre la longueur des mots est plus de 50%, vous ne serez jamais match de 95%
6. Jetez un oeil à ce implementation ils utilisent la valeur de seuil, je crois qu'il donnera Je pense que l'algoritm reviendra plus tôt si la distance est supérieure au seuil. Vérifiez également ce question