c - Realloc 与链表扫描

Question

我必须从文件中读取未知数量的行并将它们保存到一个结构中（我想避免计算元素总数）。在阅读阶段之后，我必须对这些行的每个元素进行一些计算。

我想出了两种方法：

1. realloc每次阅读一行时使用。这种方式分配阶段很慢，但由于索引访问，计算阶段更容易。

2. 每次阅读一行时使用一个链表。这样分配阶段更快，但计算阶段更慢。

从复杂性的角度来看，什么更好？

Answer 1

你多久遍历一次链表？如果它只是一次去链表。另外几件事：会有很多小分配吗？您可以为假设 10 行创建一些较小的缓冲区并将它们链接在一起。但这都是一个配置文件的问题。

我会先做最简单的事情，看看它是否符合我的需求，然后我才会考虑优化。

有时，即使第二个最佳解决方案也完全符合需求，也会浪费太多时间来考虑最佳解决方案。

Answer 2

如果没有更多关于您将如何使用这些信息的详细信息，很难评论其复杂性。但是，这里有一些想法：

• 如果您使用 realloc，那么 realloc 可能会更好地添加“一些”更多项目（而不是每次都添加一个）。通常，一个好的算法是每次将大小加倍。
• 如果您使用链表，您可以通过简单的后处理步骤加快访问速度。分配指向项目的指针数组并在将数组元素设置为列表中的每个项目后遍历列表。
• 如果文件中的项目是固定大小的，您可以预先计算大小，只需查找文件末尾，确定大小，除以项目大小即可得到结果。即使它不是固定大小，您也可以将其用作估计值，以“接近”必要的大小并减少所需的重新分配数量。

Answer 3

正如其他用户已经说过的那样：

过早的优化是万恶之源

唐纳德·克努特

我有一个不同的建议realloc：在 C++ STL 中，std::vector每次插入对象并且没有足够的空间可用时，容器都会增长。增长的大小取决于当前预分配的大小，但特定于实现。例如，您可以保存预分配对象的实际数量。如果大小用完，您将reallocate使用当前分配的双倍空间进行调用。我希望这有点可以理解！

当然，需要注意的是，您分配的空间可能比实际消耗和需要的空间多。