动态数组的收缩因子?

问题描述 投票:0回答:1

动态数组通常具有3/2到2的增长因子。但是一旦分配了内存,它就不会自动收缩。假设衰变因子的大小是增长因子的两倍是否合适?我的意思是,如果元素数比decay factor小N倍,则以较小的大小重新分配数组(realloc)?

我发现了很多有关动态数组增长的信息,但没有发现相反的操作。

c arrays dynamic-memory-allocation
1个回答
3
投票

为了使衰减因子有意义,您需要期望阵列具有

  • 使用少量元素进行长时间操作

  • 需要大量存储空间的地方爆发

  • 和其他在数组较大时不需要内存的数据结构。

通常不是这样。通常情况是以下两种情况之一:

  • 数组仅增长一次,使用一次,扔掉。

  • 数组寿命长,并且经常更改其长度。

  • 该数组寿命长,并且通常根本不会增长/缩小很多。

在所有这些情况下,引入收缩因子都是纯开销。这就是为什么这种收缩因素通常不会受到困扰的原因。尤其是由于收缩因子有可能破坏指数增长分配的O(N)聚合加时间行为。

© www.soinside.com 2019 - 2024. All rights reserved.