0

以下のコードが「stephan」のような文字列に対して12個のオブジェクトを作成するかどうかを理解しようとしています

public String reverse(String str) {
            if ((null == str) || (str.length()  <= 1)) {
                return str;
            }
            return reverse(str.substring(1)) + str.charAt(0);
        }

これにより、文字列が再帰的に反転されます。私はそれがどのように機能するかを理解しています。しかし、この場合、文字列の長さと連結によって作成された文字列オブジェクトの数の間に関係があるかどうかを考えていましたか？

4

2 に答える 2

2

はい、大量の文字列オブジェクトが作成されます。

「reverse（）」を再帰的に呼び出すたびに、2が作成されます。

  1. str.substring(1)新しいStringオブジェクトを作成します

  2. reverse()callは戻り値の新しい文字列を作成しますが、その再帰呼び出しを分析するときにカウントされるため、カウントされません（たとえば、次の呼び出しの箇条書き＃3からの文字列になりreverse()ます）。

  3. また、Java文字列は不変であるため、 ""を介してcharを追加すると、 2番目のStringオブジェクト+が作成されます。

したがって、長さがNの文字列の場合、（N-1）* 2オブジェクトが作成されます（1文字の文字列を逆にすると新しい文字列は作成されないため）。したがって、「stephan」の7文字の場合、6 * 2=12の文字列オブジェクトが作成されます。

于 2012-08-29T00:30:39.553 に答える
1

定理：

  • 文字列がN文字長の場合、@Phoenixのreverse実装は(N-1)*3新しいオブジェクトを作成します。

証明（帰納法による）：

  • strが1文字の場合、直接返されます。(1*1)*3 = 0。
  • strがN文字の場合：
    • 新しいStringはによって作成され.substring(1)ます。
    • 誘導仮説により、オブジェクトが作成されたreverse(...)後にへの呼び出しが返されます。(N-2)*3
    • StringBuilder文字列を追加するために新しいものが作成され、最初に作成されますchar（これは、バイトコードを逆コンパイルすることで確認できます）。
    • 新しいStringはによって作成されStringBuilder.toString()ます--これは戻り値です。
    • 全体として、3 + (N-2)*3 = (N-2 + 1)*3 = (N-1)*3作成されたオブジェクトがありました。
  • QED。

[編集]StringBuilders：

  • StringBuilder（AbstractStringBuilderを拡張）は、独自の凝ったフットワークを実行します。
    • StringBuilderが構築されると、サイズ16で初期化さchar[]れます。
    • 現在のサイズよりも大きいものを追加すると、それが破棄され、新しいchar[]サイズが作成され(<old size> + <size of new data> + 1) * 2ます。
  • したがって、入力文字列が16文字を超えるとすぐに、必要なStringBuilder容量の2倍の容量が基本的に得られます。（入力文字列のサイズが小さい場合は、char[]必要以上のサイズになります。）
  • Stringsが本質的にsであることを考えるchar[]と（適切な測定のために数秒あります）、各ステップintでsの部分文字列の長さの4倍を効果的に使用しています。char[]:(
于 2012-08-29T01:16:56.270 に答える