Bri*_*and 18 c c# java stringbuilder
在C中,我正在研究一个管理字节缓冲区的"类",允许将任意数据附加到结尾.我现在正在调查自动调整大小,因为底层数组使用调用填充realloc.这对任何使用过Java或C#的人都有意义StringBuilder.我知道如何调整大小.但是,没有任何人有任何建议,与理规定,关于有多少成长与每个调整缓冲区？
显然,在浪费的空间和过多的realloc调用之间存在折衷(这可能导致过度复制).我已经看过一些建议加倍的教程/文章.如果用户设法提供良好的初始猜测,这似乎是浪费.是否值得尝试在平台上舍入到两个或多个对齐大小的幂？
有没有人知道Java或C#在幕后做了什么？
Eri*_*ert 37
在C#中,用于增长StringBuilder使用的内部缓冲区的策略随着时间的推移而发生了变化.
解决这个问题有三种基本策略,它们具有不同的性能特征.
第一个基本策略是:
这个策略有很多问题,其中最明显的问题是,如果构建的字符串非常大,它的时间是O(n 2).假设k是一千个字符,最后一个字符串是一百万个字符.你最终在1000,2000,3000,4000,...重新分配字符串,因此复制1000 + 2000 + 3000 + 4000 + ... + 999000个字符,总计大约5000亿字符的复制!
这种策略具有很好的特性,即"浪费"的内存量以k为界.
实际上,由于这种n平方问题,很少使用这种策略.
第二个基本策略是
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)表示他们的测试比以往任何时候都要广泛得多,并得出了同样的结论(所以,对于例如,std::vector在他们的C++标准库中的实现使用1.5).
| 归档时间： |
|
| 查看次数： |
1435 次 |
| 最近记录： |