c# - 为什么 StringBuilder 比字符串操作快，但 List<T> 比 LinkedList<T> 快？

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，否则制作不断增加的数组 block 。

让我们看看列表是如何工作的。从列表大小开始(内部默认值为 4)。向内部数组添加元素，如果数组已满，则创建一个两倍于当前数组大小的新数组，复制当前数组的元素，然后添加新元素并将新数组设为当前数组。

您能看到我对性能优势的困惑吗？对于除字符串之外的所有元素，我们创建新数组，复制旧值并添加新值。但对于字符串来说这很糟糕吗？因为我们知道“a”+“b”从两个旧引用“a”和“b”创建了一个新的字符串引用。

希望我的问题不会太令人困惑。为什么字符串连接和数组连接之间似乎存在双重标准(我知道字符串是字符数组)？

字符串:创建新引用是不好的!

T :其中 T != String:创建新引用很好!

编辑:也许我在这里真正要问的是，创建新的、更大的数组并复制旧值什么时候开始比在堆上随机放置对象的引用更快？

双重编辑:我所说的更快是指读取、写入和查找变量，而不是插入或删除(例如，LinkedList 在插入时会很有效，但我不关心这一点)。

最终编辑:我不关心 StringBuilder，我感兴趣的是为了缓存对齐而将数据从堆的一部分复制到另一部分所花费的时间，而不是仅仅采取cpu 缓存未命中，并且在整个堆上都有引用。什么时候一个会变得比另一个更快？*

Answer 1

Therefore we should replace this:

不，你不应该。第一个案例展示了可以在编译时发生的字符串连接，并将其替换为在运行时发生的字符串连接。前者更更可取，并且执行速度比后者更快。

当编译时连接的字符串数量未知时，使用字符串生成器非常重要。通常(但并非总是)这意味着在循环中连接字符串。

早期版本的 String Builder(4.0 之前的版本，如果没记错的话)，内部看起来或多或少像 List<char> ，并且 4.0 后它看起来更像是 LinkedList<char[]> 是正确的。然而，使用 StringBuilder 之间的主要区别在循环中使用常规字符串连接并不是链表样式(其中对象包含对“链”中下一个对象的引用)和基于数组的样式(其中内部缓冲区过度分配空间并根据需要偶尔重新分配)之间的区别，而是可变对象和不可变对象(immutable对象)之间的区别。传统字符串连接的问题在于，由于字符串是不可变的，因此每次连接都必须将两个字符串中的所有内存复制到一个新字符串中。当使用StringBuilder时新字符串只需复制到某种类型的数据结构的末尾，保留所有现有内存不变。什么类型的数据结构在这里并不是非常重要；我们可以信赖 Microsoft 使用的结构/算法已被证明在最常见的情况下具有最佳性能特征。