Leg*_*dre 4 c arrays malloc realloc
我使用动态数组来表示最小堆.有一个循环可以删除最小值,并将随机元素添加到最小堆中,直到出现某些条件.虽然我不知道堆的长度在运行时会如何变化(有很多随机性),但我知道上限,即1000万.我有两个选择:
1)使用malloc声明一个小数组,然后当堆中的元素数超过长度时调用realloc.
2)使用malloc声明一个1000万条目数组.这避免了调用realloc.
题
选项2是否比选项1更有效？
我用我的代码测试了这个,并且使用2似乎有显着的(20%)运行时间减少.这是因为代码中的随机性而估计的.使用malloc预先声明一个大型的10-50万个入口阵列有什么缺点吗？
如果你可以节省内存以进行大量的前期分配,并且它提供了有价值的性能提升,那么一定要做到这一点.
如果你坚持使用realloc,那么你可能会发现每次加倍大小而不是增加固定数量可以在性能和有效内存使用之间进行良好的权衡.