陷阱 - 迴圈中的字串連線不會縮放

請考慮以下程式碼作為說明：

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 類可用於解決此特定問題。然而，這不是這個例子真正應該是什麼。