java - 迭代时比较 HashMap 元素的优化

Question

我有一个名称接近 845k 行的 csv 文件。

我要比较模糊名称字符串匹配。 我用了Java fuzzy string matching著名的 Python 的 fuzzywuzzy 算法的实现。

在下面的代码中实现，它非常适合我。 问题是处理时间太多。 每行与其他行的比较时间接近 15 秒。 这是一个小时240行，整个过程将近6000行。 所有过程将在几个月内完成。 这是 Not Acceptable 工作时间。

我需要一种优化技术或方法。 我需要一些建议而不是解决方案。

您对以下代码有何建议？

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. 您可以试试 Levenshtein 距离算法，也许它会给您带来更好的性能。或者尝试任何其他算法。提供算法实现的链接
2. Integer最好不要和==比较，使用nameId1.intValue() == nameId2
3. 创建 N 个线程，其中 N 是核心数。将所有行放入 ConcurrentLinkedQueue。让你的线程轮询队列，说一句话，做同情，一旦完成 - 写入同步部分下的文件。它将允许您在 PC 上使用所有内核，而不仅仅是 1
4. 为什么要花这么多时间，也许您有一些内存限制，这会迫使 GC 消耗您的 CPU 周期并影响性能。
5. 您可以应用一些小的优化，假设如果单词长度之间的差异超过 50%，您永远不会获得 95% 的匹配
6. 看看这个implementation 他们正在使用阈值，我相信它会给你最大的提升，我认为如果距离大于阈值，算法会更早返回。还要检查这个 question