19

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

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

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

4

7 回答 7

39

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

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

第一个基本策略是：

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

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

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

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

第二个基本策略是

  • 做一个数组
  • 当你的空间用完时，创建一个包含更多字符的新数组，用于某个常数 k。
  • 将旧数组复制到新数组，并孤立旧数组。

k% 通常为 100%；如果是，那么这就是所谓的“双满”策略。

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

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

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

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

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

.NET 框架中的字符串生成器曾经使用双时满策略；它现在使用块链表策略。

于 2012-04-17T19:05:11.280 回答
8

您通常希望保持增长因子略小于黄金平均值 (~1.6)。当它小于黄金分割时，丢弃的段将足够大以满足稍后的请求，只要它们彼此相邻。如果你的生长因子大于黄金分割，那是不可能的。

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

我似乎记得几年前在 Usenet 上的一次谈话，其中 Dinkumware 的 PJ Plauger（或者可能是 Pete Becker）说他们会进行比我做过的更广泛的测试，并得出了相同的结论（所以，对于例如，std::vector他们的 C++ 标准库中的实现使用 1.5)。

于 2012-04-17T18:45:18.387 回答
2

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

考虑您有一个 16 字节数组的情况，将其大小增加 128 字节是多余的；然而，如果你有一个 4096 字节的数组并且只增加了 128 字节，你最终会复制很多。

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

于 2012-04-17T18:41:24.083 回答
1

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

查看以下链接，了解它是如何在 JDK11 的 Java 的 StringBuilder 中完成的，特别是 ensureCapacityInternal 方法。 https://java-browser.yawk.at/java/11/java.base/java/lang/AbstractStringBuilder.java#java.lang.AbstractStringBuilder%23ensureCapacityInternal%28int%29

于 2012-04-17T18:47:01.303 回答
0

将其翻译为 C。

我可能会保留一份List<List<string>>清单。

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

   public Append(List<string> listOfCharsToAppend)
   {

       list.Add(listOfCharsToAppend);
   }

}

这样，您只需维护列表列表并按需分配内存，而不是提前分配内存。

于 2012-04-17T18:45:08.200 回答
0

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

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

于 2012-04-17T19:31:44.400 回答
0

根据文档，它是特定于实现的，但从 16 开始：

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

StringBuilder 对象可以在实例的值放大时分配更多的内存来存储字符，并相应地调整容量。例如，Append、AppendFormat、EnsureCapacity、Insert 和 Replace 方法可以放大实例的值。

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

基于其他一些 .NET 框架的东西，我建议每次达到当前容量时将其乘以 1.1。如果需要额外的空间，只需有一个等价物EnsureCapacity将手动将其扩展到必要的大小。

于 2012-04-17T18:37:09.170 回答