2
\$\begingroup\$

I have the following method, which finds all the possible paths from the top left to bottom right of an N x M matrix. I was wondering what is the best way to optimize it for speed as it is a little slow right now. The resulting paths are then stored in a set.You can only move down or right to an adjacent spot, no diagonals from your current position.

    static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {
        String newString = tempString + arr[i][j];
        if (i == m -1 && j == n-1) {
            palindrome.add(newString);
            return;
        }
        //right
        if (j+1 < n) {
            printPaths (newString, i, j+1, m, n, arr, palindrome);
        }
        //down
        if (i+1 < m) {
            printPaths (newString, i+1, j, m, n, arr, palindrome);          
        }
    }
\$\endgroup\$
  • \$\begingroup\$ Your question is missing a lot of detail. What is a palindrome in this context? What are m and n... they never change? Can you give some example input and output? I suspect there is a much better solution to this, if I am right about the guesses I have about the missing details.... \$\endgroup\$ – rolfl Apr 7 '15 at 10:24
  • 1
    \$\begingroup\$ This might not be feasible with (most) choices of N and M, for there is exactly (N + M)! / (N! x M!) possible, distinct paths, where ! denotes factorial. \$\endgroup\$ – coderodde Apr 7 '15 at 11:07
2
\$\begingroup\$
static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {

You say palindrome? Maybe you shouldn't recycle names from other tasks.

This method should not be public. And should not be called "printWhatever" as it - fortunately - does not print.

arr is an array, nice, but then why did you write "matrix" in your text? Maybe, because of matrix being a more descriptive name? So use it.

The arguments m and n are redundant as they can be obtained from the matrix (and it's improbably more time-consuming than passing them around). Too many arguments make a method hard to use and to read.

So the public method could be

static public Set<String> allPaths(char [][] matrix) {
    Set<String> result = new HashSet<>();
    addAllPathsTo(result, matrix, "", 0, 0);
    return result;
}

with a helper like

static private void addPathsTo(Set<String> result, String tempString, int i, int j, char [][] matrix) {
    String newString = tempString + arr[i][j];
    int m = matrix.length;
    int n = matrix[0].length;
    if (i == m-1 && j == n-1) {
        result.add(newString);
        return;
    }
    //right
    if (j+1 < n) {
        addPathsTo(result, newString, i, j+1, matrix);
    }
    //down
    if (i+1 < m) {
        addPathsTo(result, newString, i+1, j, matrix);
    }
}

The optimization by JS1 makes a lot of sense and could be included. My point was clean up only.

\$\endgroup\$
1
\$\begingroup\$

I found a couple of ways to improve your program speed by significant amounts.

Test methodology

First, I ran your original function using a 14x15 matrix. I ran it two times in a row in the same run and timed the second run. It took 31.19 seconds on my machine. I used that as the baseline time to beat.

Use ArrayList instead of HashSet

I'm not sure why you chose to use a HashSet as the container to build your results. Since we are going to presumably just print out all the results sequentially, an ArrayList would be faster because it avoids any unnecessary hashing.

After switching the HashSet to an ArrayList, the time went from 31.19 to 12.80 seconds (2.4x faster).

Using a char [] instead of a String

You can speed up your program by using a char array instead of a String as your temporary string that you build. Something like this:

static public void findPaths (char [] tempPath, int i, int j, int m,
        int n, char [][] arr, ArrayList<String> results) {
    tempPath[i+j] = arr[i][j];
    if (i == m -1 && j == n-1) {
        results.add(new String(tempPath));
        return;
    }
    //right
    if (j+1 < n) {
        findPaths (tempPath, i, j+1, m, n, arr, results);
    }
    //down
    if (i+1 < m) {
        findPaths (tempPath, i+1, j, m, n, arr, results);          
    }
}

You must call the function initially with a char array of size m+n-1. A lot of time in the original function is being spent creating temporary strings. This method avoids all the intermediate strings and only creates the strings that appear in the output.

After switch to a char [] as a temp, the time went from 12.80 to 7.30 seconds (1.75x faster).

Other things I tried that didn't make any difference

I tried a couple of other things that ended up not making any difference in the time.

  1. I added "short circuiting" to the code. When either i or j reaches its limit, you can handle that case specially and immediately reach the final cell instead of continuing to recurse.

  2. I converted the recursive function into an iterative one.

Both of the above neither hurt nor helped the final time.

\$\endgroup\$
  • \$\begingroup\$ @Eric Gan Another more-general case alternative is to use Java's StringBuilder. Remember that as Strings are immutable your code as stands generates and discards many temporary String objects; this is expensive. \$\endgroup\$ – RJFalconer Apr 7 '15 at 13:14
  • \$\begingroup\$ @RJFalconer Sure, but the only strings JS1 generates are the ones to be stored in results. StringBuilder could be used instead of his arrays, but it's harder to use here and a bit slower too. \$\endgroup\$ – maaartinus Apr 7 '15 at 19:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.