CODEWITHSUNDEEP
javarecursionmemoization
Anthony Feudale
Anthony Feudale

Reputation: 41

Memoization of a Recursive Search

I am trying to solve a problem in which you have to count the number of possible bar codes you can make given specific parameters. I solved the problem recursively and am able to get the correct answer every time. However, my program is dreadfully slow. I tried to rectify this using a technique I read about called memoization but my program still crawls when given certain input (ex: 10, 10, 10). Here's the code in java.

Does anybody have any idea what I'm doing wrong here?

import java.util.Scanner;

//f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

public class BarCode { public static int[][] memo;

public static int count(int units, int bars, int width) {
    int sum = 0;
    if (units >= 0 && memo[units][bars] != -1) //if the value has already been calculated return that value
            return memo[units][bars];

    for (int i = 1; i <= width; ++i) {
        if (units == 0 && bars == 0)
            return 1;
        else if (bars == 0)
            return 0;
        else {
            sum += count(units - i, bars - 1, width);
        }
    }
    if (units > -1)
        memo[units][bars] = sum;

    return sum;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    //while (in.hasNext()) {
        int num = in.nextInt();
        int bars = in.nextInt();
        int width = in.nextInt();
        memo = new int[51][51];
        for (int i = 0; i < memo.length; ++i) {
            for (int j = 0; j < memo.length; ++j)
                memo[i][j] = -1;
        }
        int sum = 0;
        sum += count(num, bars, width);
        System.out.println(sum);
    //}
    in.close();
}
}

TL:DR My memoization of a recursive search is too slow. Help!

Upvotes: 2

Views: 134

Answers (2)

Modus Tollens
Modus Tollens

Reputation: 5123

You exclude all results from count calls with units < 0 from memoization:

if (units > -1)
    memo[units][bars] = sum;

This leads to a lot of unnecessary calls to count for these values.

To include all cases, you could use a HashMap with a key generated from units and bars values. I used a string generated from units and bars like this:

//f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

public class BarCode {
    public static Map<String, Integer>  memo    = new HashMap<>();

    public static int count(int units, int bars, int width) {
        int sum = 0;

        final String key = units + " " + bars;
        Integer memoSum = memo.get(key);
        if (memoSum != null) {
           return memoSum.intValue();
        }

        for (int i = 1; i <= width; ++i) {
            if (units == 0 && bars == 0)
                return 1;
            else if (bars == 0)
                return 0;
            else {
                sum += count(units - i, bars - 1, width);
            }
        }

        memo.put(key, Integer.valueOf(sum));

        return sum;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int bars = in.nextInt();
        int width = in.nextInt();
        memo = new HashMap<>();
        int sum = 0;
        sum += count(num, bars, width);
        System.out.println(sum);
        in.close();
    }
}

For example, this brings the number of calls to count down from over 6 million to 4,150 for the input values "10 10 10" with 415 entries saved in the Map.

Upvotes: 1

Dogs
Dogs

Reputation: 3167

Your memoization implementation looks to be valid. It might help some, but the real problem here is your choice of algorithm.

From my cursory inspection of your code, on average a call to your count method will loop through width number of times. and each time it loops through, it goes a layer deeper by calling count again. It also looks like it's going to loop down bars layers deeper from the first layer. If my asymptotic analysis a few fingers of scotch in is correct, this would result in an algorithm which has a O(width^bars) runtime complexity. As you increase your input parameters, especially bars, the amount of steps your application needs to take in order to calculate your answer will increase greatly (exponentially, in the case of bars).

Your memoization will reduce the number of duplicate calculations needed, but each value being memoized will still need to be calculated at least once for the memoization to help. So with or without the memoization, you're still dealing with a non-polynomial time complexity, and that always spells bad performance.

You might want to consider looking for a more efficient approach. Instead of trying to count the number of bar code combinations, perhaps try using combinatorics to try to calculate it. For example, I could try to figure out the number of lowercase character strings (using only chars a-z) I can make for a string of length n by generating all of them and counting how many of them there are, but that will have an exponential time complexity and will not be performant. On the other hand, I know basic combinatorics tells me that the formula for the number of strings I can create is 26^n (26 choices in each position, and n positions), which the computer can easily evaluate quickly.

Look for a similar approach for computing the number of bar codes.

Upvotes: 1

Related Questions