c - 动态数组的收缩因子？

Question

动态数组通常有 3/2 到 2 的增长因子。但是一旦分配了内存，它就永远不会自动收缩。假设衰减因子是生长因子的两倍是否合适？我的意思是，如果元素的数量比衰减因子小 N 倍，则数组会重新分配 (realloc)，并且尺寸更小？

我找到了大量关于动态数组增长的信息，但没有找到关于相反操作的信息。

Answer 1

要使衰减因子有意义，您需要期望您的数组

• 长时间运行，元素很少

• 在需要更多内存的地方突发

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

通常情况并非如此。通常的情况是以下任一情况:

• 数组是一次增长，一次使用，丢弃。

• 该数组存在时间长，并且经常更改其长度。

• 阵列生命周期很长，通常根本不会增长/收缩太多。

在所有这些情况下，引入收缩因子将是纯粹的开销。这就是为什么通常不会理会此类收缩因素的原因。特别是因为收缩因子有可能破坏指数增长分配的 O(N) 聚合添加时间行为。