7

ここに、Javaで文字列を逆にするための2つの異なる再帰関数があります。

    Long ms1 = System.currentTimeMillis();
    String str1 = reverse1(str);
    ms1 = System.currentTimeMillis() - ms1;

    Long ms2 = System.currentTimeMillis();
    String str2 = reverse2(str);
    ms2 = System.currentTimeMillis() - ms2;

    System.out.println("Input: " + str);
    System.out.println("  Length: " + str.length());
    System.out.println("Reverse 1:");
    System.out.println("  " + herp + " function calls");
    System.out.println("  " + ms1 +  " milliseconds");
    System.out.println("Reverse 2:");
    System.out.println("  " + derp + " function calls");
    System.out.println("  " + ms2 +  " milliseconds");
}
public static String reverse1(String str){
    herp++;
    if(str.length() == 1) return str;
    return reverse1(str.substring(str.length()/2)) + reverse1(str.substring(0, str.length()/2));
}
public static String reverse2(String str){
    derp++;
    if(str.length() == 1) return str;
    return reverse2(str.substring(1)) + str.charAt(0);
}

長さ5000の文字列が与えられた場合、これはプログラムの出力です。

Input: ...
  Length: 5000
Reverse 1:
  9999 function calls
  16 milliseconds
Reverse 2:
  5000 function calls
  52 milliseconds

では、関数呼び出しが2倍の関数が3倍速くなるのはなぜですか？Javaで最高速度を実現するために、再帰関数をどのように構成する必要がありますか？

4

3 に答える 3

7

それは古き良きアルゴリズム分析の問題です。reverse1O（n logn）時間で実行する必要がありますが、 reverse2O（n²）時間が必要なため、反転する文字列が長いほど、より劇的に高速reverse2になりreverse1ます。

リソースの使用量は、呼び出しの数ではなく、各文字列連結操作で作成された新しいStringオブジェクトに文字をコピーするのにかかる時間によって決まります。の文字列連結は、の文字​​列よりも平均reverse2して長い文字列で機能するため、合計実行時間は長くなります。reverse1

  • ではreverse1、再帰呼び出しツリーの深さが約log2（n）であるため、すべての文字がlog2（n）回コピーされます（nは元の文字列の長さです）。

  • reverse2すべての文字で、元の文字列内の位置に等しい回数（±1、私は気にしません）がコピーされます。これにより、各文字の平均でn/2のコピーが作成されます。

nが大きい場合、log2（n）はn / 2よりもはるかに小さいため、reverse1高速になる傾向があります。

于 2012-11-06T16:23:32.370 に答える
2

最初のタイプの呼び出しの約50％は、何も行わずに終了しstr.length() == 1ます。これにより、重要な作業を伴う呼び出しの数はほぼ等しくなります。終了条件の後に移動derp++してherp++呼び出しを行うと、「重要な」呼び出しの数が得られ、それらは等しくなります。

他の呼び出しも、平均して短い文字列を連結し、3倍の違いを補うため、より高速になります。

于 2012-11-06T16:22:49.730 に答える
1

@HenningMakholmの答えは素晴らしいですが、@ cHaoによる反復法と不変の文字列に関するコメントに基づいて、これを捨てたかっただけです。これはおそらくコメントに最も適切でしょうが、私は答えのスペース不動産が欲しかったです...

public static String reverse3(String str){
    StringBuilder sb = new StringBuilder();
    int i;
    for(i = str.length() - 1; i >= 0; i--) {
        sb.append(str.charAt(i));
    }
    return sb.toString();
}

String最後に不変オブジェクトを1つだけ作成し、時間内に実行するこの反復法ではO(n)、次の結果が得られます。

  Length: 5406
Reverse 1:
  10811 function calls
  59 milliseconds
  5406 length correctness test
Reverse 2:
  5406 function calls
  126 milliseconds
  5406 length correctness test
Reverse 3:
  3 milliseconds
  5406 length correctness test
于 2012-11-06T17:27:36.673 に答える