c# - 在类似 StringBuilder 的 C 模块中增加多少缓冲区？

Question

在 C 中，我正在研究一个管理字节缓冲区的“类”，允许将任意数据附加到末尾。我现在正在研究当底层数组填满时使用调用 realloc 自动调整大小。这对于曾经使用过 Java 或 C# StringBuilder 的人来说应该是有意义的。我了解如何调整大小。但是有没有人对每次调整大小时增加多少缓冲区有任何建议，并提供了理由？

显然，在浪费的空间和过多的 realloc 调用(这可能会导致过多的复制)之间需要权衡取舍。我看过一些建议加倍的教程/文章。如果用户设法提供一个好的初始猜测，那似乎很浪费。是否值得尝试四舍五入到平台上对齐大小的两倍或倍数？

有谁知道 Java 或 C# 在幕后做了什么？

Answer 1

在 C# 中，用于增加 StringBuilder 使用的内部缓冲区的策略已随时间发生变化。

解决这个问题的基本策略有3种，它们具有不同的性能特点。

第一个基本策略是:

• 制作一个字符数组
• 当你用完空间时，创建一个包含 k 个以上字符的新数组，k 为常数。
• 将旧数组复制到新数组，并孤立旧数组。

这个策略有很多问题，其中最明显的是如果正在构建的字符串非常大，它的时间复杂度为 O(n²)。假设 k 是一千个字符，最终的字符串是一百万个字符。您最终将字符串重新分配到 1000、2000、3000、4000，...，因此复制了 1000 + 2000 + 3000 + 4000 + ... + 999000 个字符，总计复制了 5000 亿个字符!

这个策略有一个很好的特性，即“浪费”的内存量以 k 为界。

由于 n 平方问题，在实践中很少使用这种策略。

第二个基本策略是

• 制作一个数组
• 当你用完空间时，创建一个新数组，其中包含 k% 以上的字符，k 为常数。
• 将旧数组复制到新数组，并孤立旧数组。

k% 通常为 100%；如果是，则这称为“满时加倍”策略。

这个策略有一个很好的特性，即它的摊销 成本是 O(n)。再次假设最终字符串是一百万个字符，而您从一千个字符开始。您以 1000、2000、4000、8000、... 进行复制，最终复制了 1000 + 2000 + 4000 + 8000 ... + 512000 个字符，总计复制了大约一百万个字符；好多了。

无论您选择什么百分比，该策略的摊销成本都是线性的。

这种策略有一些缺点，有时复制操作非常昂贵，您可能会在未使用的内存中浪费高达 k% 的最终字符串长度 .

第三种策略是创建一个数组链表，每个数组的大小为 k。当您溢出现有数组时，会分配一个新数组并将其附加到列表的末尾。

这个策略有一个很好的特性，即没有操作特别昂贵，总浪费的内存受 k 限制，并且您不需要定期在堆中定位大块。它的缺点是最终将事物转换为字符串可能会很昂贵，因为链表中的数组可能具有较差的局部性。

.NET Framework 中的字符串生成器过去使用双倍策略；它现在使用 block 链表策略。