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 将为其返回值创建一个新字符串，但我们不会计算它，因为在分析该递归调用时会计算它（例如，它将是来自下一次reverse()调用的要点＃3 的字符串）。

  3. 由于 Java 字符串是不可变的，通过 "" 添加一个字符+将创建第二个字符串对象。

因此，对于长度为 N 的字符串，它将创建 (N-1)*2 个对象（因为 1-char 字符串的反转不会创建新字符串）；所以对于“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()--this 创建，这是返回值。
    • 总而言之，3 + (N-2)*3 = (N-2 + 1)*3 = (N-1)*3创建了对象。
  • QED。

[编辑] StringBuilders：

  • StringBuilder（扩展 AbstractStringBuilder）做了自己的花哨的步法：
    • 当 anStringBuilder被构造时，它被初始化char[]为大小为 16 的 a。
    • 当您附加的内容超过其当前大小时，它会将其丢弃并创建一个新char[]的 size (<old size> + <size of new data> + 1) * 2。
  • 因此，只要您的输入字符串大于 16 个字符，您的 StringBuilder 容量就基本上是您需要的 2 倍。（当输入字符串的大小更小时，你得到的char[]比你需要的多。）
  • 考虑到Strings 本质上是char[]s （用几个ints 来衡量），你char[]在每一步都有效地使用了 s 中子字符串长度的 4 倍。:(
于 2012-08-29T01:16:56.270 回答