爲什麼StringBuilder比字符串操作更快，但列表<T>比LinkedList更快？

Question

所以我們被告知StringBuilder應該用在對字符串進行多次操作時（我聽說只有三次）。因此，我們應更換此：

string s = ""; 
foreach (var item in items) // where items is IEnumerable<string> 
    s += item; 

有了這個：

string s = new StringBuilder(items).ToString(); 

我認爲內部的StringBuilder保存到每個追加的字符串的引用，要求再結合。讓我們把它和HybridDictionary進行比較，HybridDictionary對前10個元素使用LinkedList，然後當列表增長超過10時，交換到HashTable。正如我們可以看到的那樣，少量的引用= linkedList，else使越來越多的陣列塊。

讓我們來看看List的工作原理。從列表大小開始（內部默認值爲4）。向內部數組添加元素，如果數組已滿，則創建一個新數組，將當前數組的大小加倍，將當前數組的元素複製，然後添加新元素，並將新數組作爲當前數組。

你能看到我對性能好處的困惑嗎？對於除字符串以外的所有元素，我們創建新數組，複製舊值並添加新值。但對於那些糟糕的字符串？因爲我們知道「a」+「b」從兩個舊引用「a」和「b」中創建新的字符串引用。

希望我的問題不是太混亂。爲什麼在字符串連接和數組連接之間似乎有雙重標準（我知道字符串是字符數組）？

字符串：使新的參考文獻不好！

T：其中T！=字符串：製作新引用很好！

編輯：也許我真的在這裏問，什麼時候創建新的，更大的數組和複製舊的值，開始比任意地將對象放在整個堆上的引用更快？通過更快的速度，我的意思是讀取，寫入和查找變量，而不是插入或刪除（例如，LinkedList會在插入時進行kickass，但我不關心這一點）。

最終編輯：我不在乎StringBuilder，我對將堆中的數據從堆的一部分複製到另一部分以緩存對齊所帶來的時間差異感到興趣， CPU，並在整個堆的參考。什麼時候一個變快那麼其他*

Answer 1

因此，我們應更換此：

不，你不應該。第一種情況顯示字符串連接可能發生在編譯時間，並用字符串連接代替它，發生運行時。前者是更多更理想，並將執行比後者更快。

在編譯時未知編譯的字符串數量時，使用字符串生成器很重要。通常（但並非總是）這意味着將字符串串聯在一個循環中。

早期版本的String Builder（4.0之前，如果有內存服務的話），內部看起來或多或少像List<char>，而且4.0後看起來更像是LinkedList<char[]>。然而，在循環中使用StringBuilder與使用常規字符串連接之間的主要區別不在於其中對象包含對「鏈」中的下一個對象的引用的鏈接列表樣式與基於數組的樣式之間的區別，內部緩衝區會佔用空間並根據需要偶爾重新分配空間，而是可變對象和不可變對象之間的區別。傳統字符串連接的問題在於，由於字符串是不可變的，每個連接必須將兩個字符串的所有內存複製到一個新字符串中。當使用StringBuilder時，只需要將新字符串複製到某種類型的數據結構的末尾，將所有現有的存儲器保持原樣。在這裏什麼類型的數據結構不是非常重要的;我們可以依靠微軟使用已被證明在最常見情況下具有最佳性能特徵的結構/算法。

Answer 2

在我看來，你正在將列表的大小調整與字符串表達式的評估相混淆，並假設這兩個表達式的行爲方式相同。

考慮您的例子：string s = "a" + "b" + "c" + "d"

假設沒有常量表達式的優化（編譯器會自動處理），這是什麼會做又評價每個操作：

string s = (("a" + "b") + "c") + "d" 

這導致字符串"ab"和​​被創建爲該單一表達式的一部分。這必須發生，因爲在.NET中的strings是不可變的，這意味着它們的值在創建後無法更改。這是因爲，如果字符串是可變的，你有這樣的代碼：

string a = "hello"; 
string b = a;  // would assign b the same reference as a 
string b += "world"; // would update the string it references 
// now a == "helloworld" 

如果這是一個List，代碼會更有意義，而且甚至不需要解釋：

var a = new List<int> { 1, 2, 3 }; 
var b = a; 
b.Add(4); 
// now a == { 1, 2, 3, 4 } 

因此，非字符串「list」類型提前分配額外內存的原因是出於效率原因，並且在列表擴展時減少分配。原因是string確實不是這樣做是因爲string的值是從來沒有一旦創建就更新。

你對StringBuilder的操作假設是不相關的，但StringBuilder的目的基本上是創建有效降低了多string操作的開銷非不可變對象。

Answer 3

StringBuilder的支持存儲是根據需要調整大小的char[]。在你調用StringBuilder.ToString()之前，沒有任何東西會變成字符串。

List<T>的後備存儲是T[]，根據需要調整大小。

的東西，如

string s = a + b + c + d ; 

的問題是，編譯器將其解析爲

+ 
/\ 
a + 
/\ 
    b + 
    /\ 
    c d 

，除非它可以看到優化機會，這樣做

string t1 = c + d ; 
string t2 = b + t1 ; 
string s = a + t2 ; 

從而創建兩個臨時對象和最終的字符串。然而，使用StringBuilder，它將構建它所需的字符數組，並在最後創建一個字符串。

這是一個勝利，因爲琴絃，一旦創建，是不變（不能改變），並且通常在字符串池中實習（也就是說，只有永遠一個字符串的情況下...無論創建字符串​​多少次，每個實例都將始終是對字符串池中同一對象的引用。

這也增加了字符串創建的成本：確定候選字符串後，運行時必須檢查字符串池以查看它是否已經存在，如果是，則使用該引用;如果沒有，候選字符串將被添加到字符串池中

你的例子，雖然：

string s = "a" + "b" + "c" + "d" ; 

是一個非根據前提的推理：編譯看到常量表達式並執行稱爲常量摺疊一種優化，所以它成爲（即使在調試模式）：

string s = "abcd" ; 

類似優化的發生是算術表達式：

int x = 12/3 ; 

將被優化到

int x = 4 ;