Better alternative to nested loop

Question

I'm currently writing a program that needs to compare similar strings with Damerau levenshtein algorithm in an ArrayList of ArrayList of String. Right now, the way I'm doing this is through a nested code loop:

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;
        }
    }
}

But this is really slow as the arraylist consists of 33000 string arraylists.

Answer 1

So if I understand your code correctly you do something along the lines of this:

for each outer as cstring : 
    for each outer as current:
       levenshtein(cstring, current)

which means you make tons of unnecessary comparisons. Assuming you have a list with strings [a, b, c], the combinations you are testing are [aa, ab, ac, ba, bb, bc, ca, cb, cc]. This includes comparisons with themselves (aa, bb, cc), which is always 0, as well as calls to the levenshtein function with swapped parameters (ab,ba,ac,ca,bc,cb), which are always identical. So if you skip identical pairs and self testing, you only need to test the combinations ab,ac,bc. You could achive this in your code pretty easily by starting your inner loop on i+1.