realloc()的性能影响

Question

我有一个记录列表,在开始我不知道记录的数量.我需要将它们读入数组.因此,建议逐个读取所有记录并逐个进行重新分配,然后随着元素的增加继续增加数组大小,或者我应该花一次通过来识别记录数并只执行一次malloc吗？哪一个计算成本会低一些？

Answer 1

A realloc不是很贵.但要求realloc每个元素有点多.我建议你这样做:

• 从尺寸开始
• 添加元素时,请检查是否有足够的空间
• 如果没有足够的空间,可以加倍

正确地猜测适当的初始大小也有帮助.因此,如果60%的输入少于100条记录,请从此开始.

Answer 2

正如其他人所指出的，每当数组变满时，将其大小加倍是一种常见的技术。事实上，使用这种技术可以确保每个元素花费的时间不超过恒定量，如WikiPedia 上所述。

根据代码需要的速度以及您正在读取的源，在单独的过程中计算输出的大小可能是一个好主意。如果您从磁盘读取数据，您可能应该使用动态数组，但否则您可能应该做任何更容易实现的事情。