java - 使用递归实现编辑距离方法会导致对象堆错误

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

例如，输入可以是 ["div","table","tr","td","a"] 和 ["table","tr","td","a","strong"] ，相应的输出应为 2。

我的问题是，当任一输入列表的大小太大时，例如列表中有 40 个字符串，程序将生成 无法为对象堆保留足够的空间 错误。 JVM 参数为 -Xms512m -Xmx512m。我的代码需要这么多堆空间吗？或者是由于我的代码中的逻辑错误？

编辑:无论是否克隆列表，这种递归方法似乎都不起作用。有人可以帮助估计为我工作所需的总堆内存吗？我想这会令人震惊。不管怎样，我想我必须转向动态编程方法。

Answer 1

在每次递归调用方法之前，clone() 每个 ArrayList 实例。这本质上意味着您每次调用都会获得整个列表及其内容的另一个副本 - 它可以轻松地增加大量内存以实现大递归深度。

您应该考虑使用List#sublist()而不是 clone()，甚至向方法添加参数以将索引传递给一组初始 List 对象。