Implementing edit distance method using recursion results in object heap error

Question

    private static int editDistance(ArrayList<String> s1, ArrayList<String> s2) {
        if (s1.size()==0) {
            return s2.size();
        } 
        else if (s2.size()==0) {
            return s1.size();
        } 
        else {
            String temp1 = s1.remove(s1.size()-1);
            String temp2 = s2.remove(s2.size()-1);
            if (temp1.equals(temp2)) {
                return editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone());
            } else {
                s1.add(temp1);
                int first = editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone())+1;
                s2.add(temp2);
                s1.remove(s1.size()-1);
                int second = editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone())+1;
                s2.remove(s2.size()-1);
                int third = editDistance((ArrayList<String>)s1.clone(),(ArrayList<String>)s2.clone())+1;
                if (first <= second && first <= third ) {
                    return first;
                } else if (second <= first && second <= third) {
                    return second;
                } else {
                    return third;
                }
            }
        }
    }

For example, the input can be ["div","table","tr","td","a"] and ["table","tr","td","a","strong"] and the corresponding output should be 2.

My problem is when either input list has a size too big, e.g., 40 strings in the list, the program will generate a can't reserve enough space for object heap error. The JVM parameters are -Xms512m -Xmx512m. Could my code need so much heap space? Or it is due to logical bugs in my code?

Edit: With or without cloning the list, this recursive approach does not seem to work either way. Could someone please help estimate the total heap memory it requires to work for me? I assume it would be shocking. Anyway, I guess I have to turn to the dynamic programming approach instead.

At a first glance I would say your recursion does not terminate — Jochen, Dec 10 '12 at 12:03
That is due to the cloning lists. It would better to pass two indices and increment them on each recursive call appropriately. — khachik, Dec 10 '12 at 12:04
@Jochen Well I've tested lists of small length, e.g., 10, and it works. — Terry Li, Dec 10 '12 at 12:05
`can't reserve enough space for object heap` suggests you are not getting out of memory - but you try to reserve to much space. What environment do you have? Is it some embedded system? — amit, Dec 10 '12 at 12:06
Why don't you try a golbal static counter variable and increment it each time you call editDistance, at the end of program print that counter. This should give you a good idea of how many lists are you cloning as well as how big is your recursion tree — Sap, Dec 10 '12 at 12:08
@Grrrrr Unless absolutely needed, global static counter is usually a bad practice. — amit, Dec 10 '12 at 12:10
@amit Try it once just for testing and remove it right after! — Sap, Dec 10 '12 at 12:10
@Jochen: errr... it seems to me that it should always terminate - I believe that at least one of the lists is always reduced by one element on the next recursive call... — thkala, Dec 10 '12 at 12:10
As a matter of fact I can already see that this program will create a huge recursion tree each time it goes in the else part.. Did you ever check this http://stackoverflow.com/questions/7574311/efficiently-compute-intersection-of-two-sets-in-java unless this is homework — Sap, Dec 10 '12 at 12:12

score 2 · Accepted Answer · answered Dec 10 '12 at 12:04

2

You clone() each ArrayList instance before each recursive call of your method. That essentially means that you get yet another copy of the whole list and its contents for each call - it can easily add-up to a very large amount of memory for large recursion depths.

You should consider using List#sublist() instead of clone(), or even adding parameters to your method to pass down indexes towards a single set of initial List objects.

answered Dec 10 '12 at 12:04

thkala

84,049
23
157
201

With or without cloning the list, this recursive solution does not seem to work anyway, resulting in the same heap error. I think I'm gonna use dynamic programming techniques instead. – Terry Li Dec 10 '12 at 13:40

Implementing edit distance method using recursion results in object heap error

1 Answers1