乘以2的效率

Question

我应该以几何方式分配内存并将初始大小设置为1000.当填充它时,它将扩展到2000,4000,依此类推.

我的问题是:如果我将初始大小设置为乘以2,即1024,那么它在效率或任何其他方面会有什么不同吗？

请不要谈论分配的向量和替代方法,这只是理论上的.

Answer 1

Andrew Koenig在1998年出版的"物体定向编程期刊"中有一篇关于缓冲增长策略的文章.不幸的是,我无法找到该文章的在线副本.

通常,指数增长优于固定增长.在指数增长中,优选1.6(或1.5)倍.Koenig在一篇usenet帖子中讨论了这里的原因

http://groups.google.com/group/comp.lang.c++.moderated/msg/ba558b4924758e2e？

技术上有理由偏好1.5到2 - 更具体地说,偏好小于(1 + sqrt(5))/ 2的值.

假设您正在使用第一个适合的内存分配器,并且您逐渐附加到向量.然后每次重新分配时,分配新内存,复制元素,然后释放旧内存.这留下了一个空白,最终能够使用那个记忆会很好.如果向量增长太快,它对于可用内存总是太大.事实证明,如果增长因子是> =(1 + sqrt(5))/ 2,那么新的记忆总是对于已经留下的洞来说太大了; 如果它是<(1 + sqrt(5))/ 2,则新内存最终会适合.所以1.5小到足以让内存被回收.

PJ Plauger的STL实现(由MSVC vector使用)基于上述使用1.5.

许多大型C++人员讨论的完整主题 - http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/6ac1ff5688d6289c/ba558b4924758e2e#ba558b4924758e2e

还有一些文章谈论Koenig在JOOP中的文章.

1)http://www.gotw.ca/gotw/043.htm

有关更多信息,请参阅1998年9月出版的JOOP(面向对象编程期刊)中的Andrew Koenig专栏.Koenig还说明了为什么一般来说,最佳增长因素不是2,而是大约1.5.

2)http://www10.informatik.uni-erlangen.de/Publications/TechnicalReports/TechRep09-11.pdf

增长策略使用户能够指定指针向量在需要更多元素时如何增长.尽管在大多数情况下,Andrew Koenig [Koe98,Sut07]提出的最佳增长策略应该为大多数场景提供最佳性能,但在某些情况下,不同的方法仍然可以产生影响.