嵌套循环的更好替代方案

Question

我目前正在编写一个程序，该程序需要在ArrayList of String中将类似的字符串与Damerau levenshtein算法进行比较。现在，我这样做的方式是通过嵌套代码循环：

Damerau d = new Damerau();
for(int i = 0;i<outer.size();i++) {
    System.out.println(i);
    String cstring = outer.get(i).get(5);
    for(ArrayList<String> current : outer) {
        if(d.distance(cstring , current.get(5)) < 30){
            //System.out.println(cstring);
            outer.get(i).set(0, current.get(0));
            break;
        }
    }
}

但这真的很慢，因为数组列表由 33000 个字符串数组列表组成。

Answer 1

因此，

如果我正确理解您的代码，您可以执行以下操作：

对于每个外部作为 cstring：    对于每个外部作为电流：       Levenshtein（cstring， current）

这意味着您进行了大量不必要的比较。假设您有一个包含字符串[a, b, c]的列表，您正在测试的组合[aa, ab, ac, ba, bb, bc, ca, cb, cc] 。这包括与自身（aa, bb, cc）的比较，它总是0，以及使用交换参数（ab,ba,ac,ca,bc,cb）调用levenshtein函数，这些参数总是相同的。因此，如果您跳过相同的配对和自检，则只需要测试组合ab,ac,bc。通过在 i+1 上启动内部循环，您可以在代码中轻松实现这一点。