迭代比較HashMap元素的優化

我想比較模糊名稱字符串匹配。我用Java fuzzy string matching實現了衆所周知的Python的fuzzywuzzy算法。

在代碼下面實現它對我來說非常完美。問題是過程時間到很多。每行比較時間與其他行近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); 
}

來源

2017-01-06 Yilmazerhakan

如何在AWS中的幾個CPU或幾臺服務器上運行此操作？如果我是對的，24個核心應該需要3天：（（845000 * 15/2）/ 60/60/24）/ 24〜3.05天。我認爲這是可以接受的，因爲你應該這樣做一次。 –

@MaximDobryakovİt是我的臺式電腦與I7的CPU和16 GB的RAM.win 10操作系統。 – Yilmazerhakan

你可以嘗試，而不是Levenshtein距離算法，也許它會給你更好的性能。或者嘗試其他算法。提供鏈接到算法實現
最好不要將Integer與==比較，使用nameId1.intValue() == nameId2
創建N個線程，其中N是核心數。將所有行放入ConcurrentLinkedQueue中。讓你線程輪詢隊列，寫下一句話，一旦完成就表示同情 - 寫入同步部分下的文件。它可以讓你使用你PC上的所有內核，不僅僅需要很多時間，也許你有一些內存限制，這會迫使GC吃掉你的CPU週期並影響性能。
您可以將一些細微的優化，讓我們說，如果單詞長度之間的不同更多的則是50％，你將永遠不會獲得95％的匹配
看看這個implementation他們正在使用的閾值，我相信它會給你最大的提升，如果距離大於閾值，我認爲算法會返回更早。此外，請檢查此question

來源

2017-01-06 22:59:16 Anton

我會使用比內核多的線程，因爲兩個線程仍然可以在同一個內核上運行。 – NickL

謝謝安東。我會盡快嘗試2和5。對於1，我編輯並鏈接了fuzzywuzzy github庫。它也基於levensthein並且有一些類似於亂序文字的比較。我無法理解第二名。對不起，我很少使用java，但NameIds也是整數。我將搜索，學習並嘗試3.對於4，它是我的桌面，並在上面的答案評論中給出了屬性。 – Yilmazerhakan

2）是關於你不應該用==比較對象，通過調用Integer對象的intValue（）來比較原語。然而，在這種情況下，因爲我們正在討論hashmap的關鍵，我認爲在Integer對象上使用==是安全的（甚至可能是最快的）。 – NickL

迭代比較HashMap元素的優化

回答

相關問題