陷阱 - 循环中的字符串连接不会缩放

Created: November-22, 2018

请考虑以下代码作为说明：

public String joinWords(List<String> words) {
    String message = "";
    for (String word : words) {
        message = message + " " + word;
    }
    return message;
}

不幸的是，如果 words 列表很长，这段代码效率很低。问题的根源是这句话：

message = message + " " + word;

对于每个循环迭代，此语句创建一个新的 message 字符串，其中包含原始 message 字符串中所有字符的副本，并附加了额外的字符。这会生成许多临时字符串，并进行大量复制。

当我们分析 joinWords 时，假设有 N 个平均长度为 M 的单词，我们发现创建了 O(N) 个临时字符串，并且在此过程中将复制 O（MN 2 ）个字符。N 2 组分特别麻烦。

针对此类问题 1 的推荐方法是使用 StringBuilder 而不是字符串连接，如下所示：

public String joinWords2(List<String> words) {
    StringBuilder message = new StringBuilder();
    for (String word : words) {
        message.append(" ").append(word);
    }
    return message.toString();
}

对 joinWords2 的分析需要考虑生长保存构建器角色的 StringBuilder 后备阵列的开销。但是，事实证明，创建的新对象的数量是 O(logN)，并且复制的字符数是 O(MN) 字符。后者包括在最后的 toString() 调用中复制的字符。

（可以通过创建具有正确容量的 StringBuilder 来进一步调整它。但是，整体复杂性保持不变。）

回到最初的 joinWords 方法，事实证明，关键语句将由典型的 Java 编译器优化为：

  StringBuilder tmp = new StringBuilder();
  tmp.append(message).append(" ").append(word);
  message = tmp.toString();

但是，Java 编译器不会将 StringBuilder提升到循环之外，正如我们在 joinWords2 的代码中所做的那样。

参考：

“Java 循环中的字符串’+‘运算符是否缓慢？”

1 - 在 Java 8 及更高版本中，Joiner 类可用于解决此特定问题。然而，这不是这个例子真正应该是什么。