Оптимизация для сравнения элементов HashMap во время итерации

Question

У меня есть файл csv с именами почти 845k строк.

Я хочу сравнить нечеткое имя строки соответствия. Я использовал Java fuzzy string matching реализацию известного алгоритма fuzzywuzzy Python.

Реализованный ниже код работает отлично для меня. Проблема - это время для процесса. Каждое время сравнения строк составляет около 15 секунд с другими линиями. Это 240 строк в течение часа, и весь процесс будет около 6000 строк. И весь процесс будет завершен через несколько месяцев. Это неприемлемое рабочее время.

Мне нужна техника или метод оптимизации. Мне нужно некоторое предложение, а не решение.

Что вы предлагаете для нижнего кода?

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. Вы можете попробовать вместо Левенштейна алгоритм расстояния, может быть, это даст вам лучшую производительность. Или попробуйте любой другой алгоритм. Предоставить ссылку на реализацию алгоритма
2. Лучше не сравнивать Integer с ==, используйте nameId1.intValue() == nameId2
3. Создайте N потоков, где N - количество ядер. Поместите все свои строки в ConcurrentLinkedQueue. Позвольте вам опросить очередь, возьмите слово, сострадайте, как только закончите - напишите в файл в синхронизированной секции. Это позволит вам использовать все ваши ядра на вашем ПК, а не только 1
4. Почему это занимает так много времени, возможно, у вас есть ограничение памяти, которое заставляет GC съесть ваши циклы процессора и повлиять на производительность.
5. Вы можете применить некоторые незначительные оптимизации, скажем, если она отличается от слов длиной более 50%, вы никогда не получите 95% бонус
6. Взгляните на эту implementation они используют пороговое значение, я считаю, что это даст вы повышаете максимальный уровень, я думаю, что алгоритм вернется раньше, если расстояние больше порога. Также проверьте это question