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

Question

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

显然，要在浪费的空间和过多的重新分配调用之间进行权衡（这可能导致过多的复制）。我看过一些建议加倍的教程/文章。如果用户设法提供一个很好的初始猜测，那似乎是浪费。是否值得尝试将平台的对齐大小取整为两倍或整数倍的幂？

有人知道引擎盖下的Java或C＃是什么吗？

Answer 1

在C＃中，用于增长StringBuilder使用的内部缓冲区的策略已随时间而改变。

解决此问题有三种基本策略，它们具有不同的性能特征。

第一个基本策略是：

• 制作字符数组
• 当您的空间不足时，请为常数k创建一个包含k个其他字符的新数组。
• 将旧阵列复制到新阵列，然后孤立旧阵列。

该策略存在许多问题，最明显的问题是，如果要构建的字符串非常大，则及时变为O（n
2）。假设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框架中的字符串生成器过去曾使用过双重填充策略。现在，它使用了阻止链接列表策略。