乘法的效率2 [英] Efficiency of multiplication by 2

问题描述

我应该在几何分配内存并将初始大小设置为1000.当填充时，它将扩展到2000,4000等。

I'm supposed to allocate memory geometrically and set the initial size to 1000. When this is filled, it would expand to 2000, 4000, and so on.

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

My question is: If I set the initial size to multiply of 2, which is 1024, would it be any different in terms of efficiency or any other aspects?

请

推荐答案

Andrew Koenig发表了一篇文章， 1998年一期关于缓冲增长策略的对象定向编程杂志。很遗憾，我无法找到该文章的在线副本。

There was an article by Andrew Koenig in a 1998 issue of Journal of Object Orient Programming about buffer growth strategies. Unfortunately, I am not able to locate an online copy of the article.

一般来说，指数增长优先于固定增长。在指数生长中，优选1.6（或1.5）的因子。 Koenig在usenet文章中谈到这里的原因

In general exponential growth is preferred to fixed growth. In exponential growth a factor of 1.6 (or 1.5) is preferred. Koenig talks about the reason here in a usenet post

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

有一个技术原因喜欢1.5到2 - 更具体来说，
喜欢小于（1 + sqrt（5））/ 2的值。

There is a technical reason to prefer 1.5 to 2 -- more specifically, to prefer values less than (1+sqrt(5))/2.

假设您使用的是第一个适配的内存分配器，并且您正在逐步将
附加到向量。然后每次你重新分配，你分配新的
内存，复制元素，然后释放旧的内存。这留下一个缺口，和
这将是很高兴能够使用该内存最终。如果向量
增长得太快，它对于可用的存储器将总是太大。
事实证明，如果生长因子> =（1 + sqrt（5））/ 2，新内存
对于已经离开sofar的洞将总是太大;如果是
<（1 + sqrt（5））/ 2，则新的存储器将最终适合。所以1.5是足够小到
允许内存回收。

Suppose you are using a first-fit memory allocator, and you're progressively appending to a vector. Then each time you reallocate, you allocate new memory, copy the elements, then free the old memory. That leaves a gap, and it would be nice to be able to use that memory eventually. If the vector grows too rapidly, it will always be too big for the available memory. It turns out that if the growth factor is >= (1+sqrt(5))/2, the new memory will always be too big for the hole that has been left sofar; if it is <(1+sqrt(5))/2, the new memory will eventually fit. So 1.5 is small enough to allow the memory to be recycled.

向量的PJ Plauger的STL实现（由MSVC使用） 。

P J Plauger's STL Implementation (used by MSVC) of vector uses 1.5 based on the above.

很多大型C ++讨论的完整线程 - http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/6ac1ff5688d6289c/ba558b4924758e2e ＃ba558b4924758e2e

The full thread where a lot of big C++ guys discuss it - http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/6ac1ff5688d6289c/ba558b4924758e2e#ba558b4924758e2e

此外，还有一些文章介绍了Koenig的JOOP文章。

Also there are a couple of articles which talk about Koenig's article in JOOP.

1） http：// www。 gotw.ca/gotw/043.htm

有关详细信息，请参阅1998年9月发行的JOOP的Andrew Koenig的专栏（Journal of Object-Oriented Programming）。 Koenig也显示了为什么，一般来说，最好的生长因子不是2，但可能约为1.5。

For more information, see Andrew Koenig's column in the September 1998 issue of JOOP (Journal of Object-Oriented Programming). Koenig also shows why, again in general, the best growth factor is not 2 but probably about 1.5.

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

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

The growth policy enables the user to specify how a pointer vector grows in case it needs more elements. Although in most cases the optimal growth strategy suggested by Andrew Koenig [Koe98,Sut07] should provide the best performance for most scenarios, in some scenarios a dierent approach can still make a difference.

这篇关于乘法的效率2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！