在构造多个字符串时使用 StringBuilder 是否有任何显着的性能优势？

Question

假设我正在构建一组字符串，其中每个字符串都是下一个字符串的前缀。例如，假设我写了一个函数：

public Set<String> example(List<String> strings) {
    Set<String> result = new HashSet<>();
    String incremental = "";
    for (String s : strings) {
        incremental = incremental + ":" + s;
        result.add(incremental);
    }
    return result;
}

重写它以使用 StringBuilder 而不是串联是否值得？显然，这将避免在循环的每次迭代中构造一个新的 StringBuilder，但我不确定这是否对大型列表有重大好处，或者您通常希望通过在循环中使用 StringBuilder 来避免的开销主要是不必要的字符串构造。

Answer 1

通常，您总是想在一个循环中寻找 StringBuilder，因为 O(n) 算法会变成 O(n^2)。然而，这已经是 O(n^2)。甚至所需的内存使用量也是 O(n^2)。看起来好像非常无关紧要，但也许有两个性能差异的因素。另外，正如您从评论中看到的那样，读者正在期待 StringBuilder - 不要不必要地让他们感到惊讶。

总的来说，虽然有些人可能会说测量，但 O(n^2) 可能会在测试中不会出现的情况下爆炸。无论如何，谁愿意对他们所有的代码进行微基准测试？避免大 O 效率低下是理所当然的事。

在某些实现中，String.substring 会在原始字符串和子字符串之间共享支持 char[]。但是，我认为目前通常不会这样做。这并不能阻止您编写自己的小 String class.

Answer 2

这个答案只对 Java 8 是正确的；正如@user85421 指出的那样，字符串上的 + 不再编译为及更高版本中的 StringBuilder 操作。

至少从理论上讲，仍然有理由在您的示例中使用 StringBuilder。

让我们考虑一下字符串连接是如何工作的：赋值 incremental = incremental + ":" + s; 实际上创建了一个新的 StringBuilder，通过复制将 incremental 附加到它，然后将 ":" 附加到它复制，然后通过复制将 s 附加到它，然后调用 toString() 通过复制构建结果，并将对新字符串的引用分配给变量 incremental。从一个地方复制到另一个地方的字符总数是 (N + 1 + s.length()) * 2 其中 N 是 incremental 的原始长度，因为每个字符都复制到 StringBuilder 的缓冲区一次, 然后再退出一次。

相反，如果您显式使用 StringBuilder - 在所有迭代中使用相同的 StringBuilder - 然后在循环中您将编写 incremental.append(":").append(s); 然后显式调用 toString() 构建要添加到集合中的字符串。此处复制的字符总数为 (1 + s.length()) * 2 + N，因为 ":" 和 s 必须被复制进出 StringBuilder，但 N toString() 方法中 StringBuilder 的 out 只需要复制前一个状态的字符；它们也不必复制进来，因为它们已经存在了。

因此，通过使用 StringBuilder 而不是串联，您在每次迭代中将更少的字符复制到缓冲区中，而从缓冲区中复制的字符数相同。 N 的值从最初的 0 增长到所有字符串长度的总和（加上冒号的数量），因此总节省量是字符串长度总和的二次方。这意味着节省的费用可能非常可观；我会把它留给其他人进行实证测量，看看它有多重要。

在构造多个字符串时使用 StringBuilder 是否有任何显着的性能优势？

Is there any significant performance benefit to using StringBuilder when constructing multiple strings?

java

stringbuilder