我注意到实现动态数组是很常见的(尤其是在面试问题和家庭作业中);通常,我看到的问题是这样表述的:
实现一个数组,其中doubles满时容量
或者非常相似的东西。他们几乎总是(根据我的经验)使用这个词double明确地,而不是更笼统地
实现一个数组,其中增加满时容量
我的问题是,为什么要加倍?我理解为什么使用常量值是一个坏主意(感谢这个问题 https://stackoverflow.com/questions/20448031/is-doubling-the-capacity-of-a-dynamic-array-necessary)但似乎使用比 double 更大的倍数更有意义;为什么不将容量增加三倍、四倍或平方呢?
澄清一下,我不是在问how为了使数组的容量加倍,我问why加倍是惯例。
是的,这是常见的做法。
加倍是管理内存的好方法。堆管理算法通常基于经典的 Buddy System,这是处理寻址、合并和其他挑战的简单方法。知道了这一点,在处理分配时最好坚持使用 2 的倍数(尽管有一些混合算法,如平板分配器,可以帮助解决碎片问题,因此使用倍数并不像以前那么重要)。
高德纳在他的一本书中对此进行了介绍,我已经忘记了书名。
See http://en.wikipedia.org/wiki/Buddy_memory_allocation http://en.wikipedia.org/wiki/Buddy_memory_allocation
将数组大小加倍的另一个原因是增加成本。您不希望每个 Add() 操作都触发重新分配调用。如果您已经填满了 N 个插槽,那么您很有可能需要 N 的倍数,历史是未来需求的良好指标,因此该对象需要“毕业”到下一个竞技场大小。通过加倍,重新分配的频率呈对数下降 (Log N)。加倍只是最方便的倍数(作为最小的整体乘数,它比 3*N 或 4*N 的内存效率更高,而且它往往紧密遵循堆内存管理模型)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)