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

Question

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

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

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

Answer 1

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

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

第一个基本策略是：

• 设置字符数组
• [空间不足时，请为常数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框架中的字符串生成器，曾经使用过双重填充策略；它现在使用阻止链接列表策略。

您通常希望使增长因子略小于黄金均值（〜1.6）。当它小于黄金均值时，只要它们彼此相邻，则丢弃的段将足够大，可以满足以后的请求。如果您的增长因素大于黄金分割，那就不会发生。

[我发现将因子减小到1.5仍然可以很好地工作，并且具有易于在整数数学中实现的优点（size = (size + (size << 1))>>1;-使用不错的编译器，您可以将其写为(size * 3)/2，并且仍应编译为快速代码。

[我似乎想起了几年前在Usenet上的一次对话，当时Dinkumware的PJ Plauger（也许是Pete Becker）说，他们进行的测试比以往任何时候都更广泛，并且得出了相同的结论（ ，例如，其C ++标准库中std::vector的实现使用1.5）。

[使用扩展和收缩缓冲区时，您想要的关键属性是按大小的倍数增长或收缩，而不是恒定的差。

考虑到您有一个16个字节的数组，将其大小增加128个字节是过大的；但是，如果相反，您有一个4096字节的数组并将其仅增加了128个字节，则最终将导致大量复制。

有人教我总是将数组加倍或减半。如果您确实没有关于大小或最大值的提示，则乘以2可确保您长时间拥有大量容量，并且除非您在资源受限的系统上工作，否则最多分配两倍的空间不会太可怕了此外，将事物保持为2的幂可以使您使用移位和其他技巧，并且底层分配通常为2的幂。

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

[请查看以下链接，以了解如何在Java的JDK11的StringBuilder中完成此操作，尤其是suresureCapacityInternal方法。https://java-browser.yawk.at/java/11/java.base/java/lang/AbstractStringBuilder.java#java.lang.AbstractStringBuilder%23ensureCapacityInternal%28int%29

根据the documentation，它是特定于实现的，但以16开始]]

此实现的默认容量为16，默认容量为 最大容量为Int32.MaxValue。

StringBuilder对象可以分配更多内存来存储字符 当实例的值被放大并且容量为 相应地进行了调整。例如，Append，AppendFormat， 确保功能，插入和替换方法可以扩大 一个实例。

分配的内存量是特定于实现的，并且 异常（ArgumentOutOfRangeException或OutOfMemoryException） 如果所需的内存量大于最大值，则会引发 容量。

基于其他.NET框架，我建议每次达到当前容量时将其乘以1.1。如果需要额外的空间，只需具有与EnsureCapacity等效的字符，它将手动将其扩展为所需的大小。

将其翻译为C。

我可能会保留一个List<List<string>>列表。

class StringBuilder
{
   private List<List<string>> list;

   public Append(List<string> listOfCharsToAppend)
   {

       list.Add(listOfCharsToAppend);
   }

}

这样，您只维护列表列表并在

demand上分配内存，而不是提前分配内存。    

。NET框架中的列表使用此算法：如果指定了初始容量，它将创建此大小的缓冲区，否则，直到添加第一个项目之前，才分配缓冲区，该缓冲区分配的空间等于添加的项目数，但不少于4个。当需要更多空间时，它将分配两倍于先前容量的新缓冲区，并将所有项目从旧缓冲区复制到新缓冲区。早期的StringBuilder使用类似的算法。

。NET 4中，StringBuilder分配初始缓冲区的大小，该初始缓冲区的大小在构造函数中指定（默认大小为16个字符）。如果分配的缓冲区太小，则不会进行复制。相反，它将当前缓冲区填充到边缘，然后创建StringBuilder的新实例，该实例分配大小为* MAX（length_of_remaining_data_to_add，MIN（length_of_all_previous_buffers，8000））*的缓冲区，以便至少所有剩余数据适合新缓冲区和所有缓冲区的总大小至少翻了一番。新的StringBuilder保留了对旧StringBuilder的引用，因此各个实例创建了缓冲区的链接列表。

Answer 2

Answer 3

Answer 4

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

Answer 5

此实现的默认容量为16，默认容量为 最大容量为Int32.MaxValue。

Answer 6

我可能会保留一个List<List<string>>列表。

Answer 7

。NET 4中，StringBuilder分配初始缓冲区的大小，该初始缓冲区的大小在构造函数中指定（默认大小为16个字符）。如果分配的缓冲区太小，则不会进行复制。相反，它将当前缓冲区填充到边缘，然后创建StringBuilder的新实例，该实例分配大小为* MAX（length_of_remaining_data_to_add，MIN（length_of_all_previous_buffers，8000））*的缓冲区，以便至少所有剩余数据适合新缓冲区和所有缓冲区的总大小至少翻了一番。新的StringBuilder保留了对旧StringBuilder的引用，因此各个实例创建了缓冲区的链接列表。