Realloc与链接列表扫描

Question

我必须从一个文件中读取一个未知数量的行并将它们保存到一个结构中(我希望避免使用预处理来计算元素的总数).在读取阶段之后,我必须对这些行的每个元素进行一些计算.

我想出了两种方法:

1. 使用realloc每个我读了一排时间.这样,分配阶段很慢,但由于索引访问,计算阶段更容易.

2. 每次我读一行时都使用链表.这样,分配阶段更快,但计算阶段更慢.

从复杂的角度来看,有什么更好的？

Answer 1

您经常浏览链表？如果它只是一次去链表.还有一些事情:那会有很多小额分配吗？您可以制作一些较小的缓冲区,让我们说10行并链接那些togeteher.但这都是剖析问题.

我先做最简单的事情,然后看看是否符合我的需要,然后再考虑优化.

有时候,即使第二个最佳解决方案也能完美地满足需求,人们也会浪费太多时间来考虑最优.

Answer 2

如果没有关于如何使用这些信息的更多细节,那么评论复杂性就有点难了.不过,这里有一些想法:

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