具有显着变化长度的输入的最佳StringBuffer初始容量是多少？

Question

大家下午好,我正在使用java.lang.StringBuilder存储一些字符.我不知道我要提前存储多少个角色,除了:

1. 60%的时间,它只有(确切地说)7个字符
2. 39%的时间,(大约)3500个字符
3. 1%的时间,大约是20k个字符

我们如何计算应该使用的最佳初始缓冲区长度？

_{目前我正在使用,new java.lang.StringBuilder(4000)但这只是因为我以前懒得思考.}

Answer 1

这里有两个因素:时间和内存消耗.时间主要受java.lang.AbstractStringBuilder.expandCapacity()所调用次数的影响.当然,每次调用的成本与缓冲区的当前大小成线性关系,但我在这里简化并计算它们:

数expandCapacity()(时间)

默认配置(16个字符容量)

• 在60%的情况下,StringBuilder将扩展0次
• 在39%的情况下,这StringBuilder将扩大8倍
• 在1%的情况下,StringBuilder将扩大11倍

预期数量expandCapacity为3,23.

初始容量为4096个字符

• 在99%的情况下,StringBuilder将扩展0次
• 在1%的情况下,StringBuilder将扩大3倍

预期的数量expandCapacity是0,03.

正如您所看到的,第二种情况似乎要快得多,因为它很少需要扩展StringBuilder(每100个输入三次).但请注意,第一次扩展不太重要(复制少量内存); 此外,如果您以巨大的块为构建器添加字符串,它将在更少的迭代中更加热切地扩展.

另一方面,内存消耗增长:

内存消耗

默认配置(16个字符容量)

• 在60%的情况下,StringBuilder将占用16个字符
• 在39%的情况下,StringBuilder将占用4K个字符
• 在1%的情况下,StringBuilder将占用32K字符

预期的平均内存消耗为:1935个字符.

初始容量为4096个字符

• 在99%的情况下,StringBuilder将占用4K个字符
• 在1%的情况下,StringBuilder将占用32K字符

预期的平均内存消耗为:4383个字符.

TL; DR

这让我相信将初始缓冲区扩大到4K会使内存消耗增加两倍以上,同时将程序加速两个数量级.

底线是:试试!编写一个能够处理具有不同初始容量的不同长度的百万字符串的基准并不难.但我相信更大的缓冲区可能是一个不错的选择.