1 
    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 個の文字列がある場合)、プログラムがcan't reserve enough space for object heapエラーを生成することです。JVM パラメータは-Xms512m -Xmx512m. 私のコードはそんなに多くのヒープ領域を必要とするでしょうか? または、コードの論理的なバグが原因ですか?

編集：リストのクローンを作成するかどうかに関係なく、この再帰的なアプローチはどちらの方法でも機能しないようです。誰かが私のために働くために必要な総ヒープメモリを見積もってくれませんか? 衝撃的だったと思います。とにかく、代わりに動的計画法のアプローチに目を向ける必要があると思います。

4

1 に答える 1

2

メソッドの各再帰呼び出しの前に、clone()各ArrayListインスタンス。これは本質的に、呼び出しごとにリスト全体とその内容のさらに別のコピーを取得することを意味します。再帰の深さが大きいと、非常に大量のメモリに簡単に追加できます。

List#sublist()の代わりに使用するか、メソッドにパラメーターを追加して、初期オブジェクトclone()の単一セットにインデックスを渡すことを検討する必要があります。List

于 2012-12-10T12:04:55.187 に答える