我正在使用一个动态数组来表示一个最小堆。有一个循环删除最小值,并将随机元素添加到最小堆,直到出现某些情况。虽然我不知道堆的长度在运行时会如何变化(随机性很大),但我知道上限,也就是 1000 万。我有两个选择:
1) 使用 malloc 声明一个小数组,然后当堆中的元素数量超过长度时调用 realloc。
2) 使用 malloc 声明一个 1000 万个条目的数组。这避免了调用 realloc。
问题
选项 2 是否比选项 1 更有效?
我用我的代码对此进行了测试,使用 2 似乎显着减少了运行时间 (20%)。这是由于代码中的随机性而估计的。预先使用 malloc 声明一个 10-5000 万条目的大型数组有什么缺点吗?
最佳答案
如果您可以腾出内存来进行大量的前期分配,并且它提供了有值(value)的性能提升,那么一定要这样做。
如果您坚持使用 realloc
,那么您可能会发现每次都将大小加倍而不是增加固定数量可以在性能和高效内存使用之间取得良好的平衡。
关于c - 多个 realloc 是否比一个巨大的 malloc 更昂贵?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13825096/