2
\$\begingroup\$

I have written a Java program to calculate the Hamming distance between two adjacency lists. The program calculates the Hamming distance correctly, but it takes a very long time, especially when dealing with bigger lists. Can anyone suggest a better way to optimize my program?

Below are the sample lists and the method that calculates Hamming distance:

Adjacency list for a:

0 => 0 1 2 
1 => 0 1 
2 => 

Adjacency list for b:

0 => 0 
1 => 0 1 2 
2 => 0 1 2

Hamming distance between Adjacency List A and B is: 6

public int hamming(ArrayList[] a, ArrayList[] b) {
    int distance = 0;
    for (int i2 = 0; i2 < b.length; i2++) {
        for (int j2a = 0; j2a < a[i2].size(); j2a++) {
            boolean found = false;
            for (int k = 0; k < b[i2].size(); k++) {
                if ((int) a[i2].get(j2a) == (int) b[i2].get(k)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                distance++;
            }
        }
        for (int j2b = 0; j2b < b[i2].size(); j2b++) {
            boolean found = false;
            for (int k = 0; k < a[i2].size(); k++) {
                if ((int) b[i2].get(j2b) == (int) a[i2].get(k)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                distance++;
            }
        }
    }
    System.out.println("Hamming distance between Adjacency List  A and B is: " + distance + "\n");
    return distance;
}
\$\endgroup\$

migrated from stackoverflow.com Oct 13 '17 at 1:06

This question came from our site for professional and enthusiast programmers.

1
\$\begingroup\$

First what you want is not the Hamming distance but the Levenshtein distance (the Hamming distance in fact assumes that the two strings (in this case lists) have the same size). Computing the Levenshtein distance is not trivial and to build an efficient algorithm you need to use the dynamic programming (otherwise you can come up with a recursive algorithm that is less efficient).

The approach is the following: A list can be transformed in a second one by applying tree different operations to an element: insert, remove, modify.

With this in mind we design the algorithm as follow: we keep a matrix M where

M[i][j] = distance between the first i-th elms of the the first list and the first j-th elems of the second list.

Thus, the first row of the matrix represents the distance between an empty list and the second list if you consider only the first i-th elements. Thus it has to initialized as follow:

for i in range(len(l1)):
    M[0][i] = i

because we can always transform a list to the empty one by dropping all the elements (so i operations).

Similarly first column also is initialized in the same way:

for i in range(len(l2)):
    M[i][0] = i

At this point to compute the distance between the first i elements of l1 and the first j elements of l2 we have to consider which is the operation that will transform l1 to l2 with fewer operations. So we take the minimum between

  • the number of operations to transform l1[0:i-1] into l2[0:j] + 1 (the added 1 is the cost for this operation which is the deletion)
  • the number of operations that we had to perform to transform l1[0:i] into l2[0:j-1] + 1 (this represent the insertion operation)
  • and the number of operations to transform l1[0:i-1] into l2[0:j-1]. Summing 1 if l1[i] != l2[j] (we have to substitute te element), 0 otherwise.

This translated into formula is:

M[i][j] = min(M[i-1][j] + 1, M[i][j-1] + 1, M[i-1][j-1] + 1 if l1[i]==l2[j] else 0

Implementing everything in java is:

public static int editDistance(List<String> l1, List<String> l2)
{
    int[][] M = new int[l1.size()][l2.size()];
    for(int i = 0; i < l2.size();i++)
        M[0][i] = i;
    for(int i = 0; i < l1.size(); i++)
        M[i][0] = i;

    for(int i = 1; i < l1.size(); i++)
    {
        for(int j = 1; j < l2.size(); j++)
        {
            int substitute = 0;
            if(!l1.get(i).equals(l2.get(j)))
                substitute = 1;

            int minRemoveAdd = Math.min(M[i - 1][j] + 1, M[i][j - 1] + 1);
            M[i][j] = Math.min(minRemoveAdd, M[i-1][j-1] + substitute);
        }
    }
    return M[l1.size() - 1][l2.size() - 1];
}
\$\endgroup\$
  • \$\begingroup\$ If instead you really wanted the hamming distance of two list (but they have to be of the same size) then given surely don't have repetitions in each list of the adjacency list for two list l1 and l2 of the first and the second adjacency list, just do: Set<String> intersection = new HashSet<>(l1).retainAll(new HashSet<>(l2)) return intersection.size() \$\endgroup\$ – Tommaso Pasini Oct 12 '17 at 16:34
0
\$\begingroup\$

Analysis of your code:

For all starting nodes i2 [by the way, that's not a helpful name...], you count how many elements from a[i2] are not contained in b[i2] and vice versa. So you're comparing two ArrayLists for elements not appearing in both of them. Your twice-two-nested-loops solution is OK if the ArrayLists are short. As you're asking this question, I suppose they aren't.

Then one solution would be:

Set<Integer> intersection = new HashSet<Integer>(list1).retainAll(list2);
int distance = list1.size() + list2.size() - 2*intersection.size();

If this doesn't help enough (and your node numbers are starting from 0 and don't have significant gaps, as it looks like), I'd change the data structure to use bits in a BigInteger instead of the ArrayList elements (e.g. a 0b10001001 replacing a list of [7, 3, 0]). Then do:

BigInteger delta = bits1.xor(bits2);
int distance = delta.bitCount();

But as usual, there's a tradeoff, e.g. using BigInteger makes enumerating the child nodes from a starting node more complicated. So you have to decide what's more important. Or maybe you go for a dual data structure, maintaining both the ArrayList and the BigInteger in parallel.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy