Realloc 与链表扫描
我必须从文件中读取未知数量的行并将它们保存到结构中（我想避免预处理来计算元素总数）。 在阅读阶段之后，我必须对这些行的每个元素进行一些计算。
我想出了两种方法：
每次读取一行时都使用
realloc。这样，分配阶段很慢，但由于索引访问，计算阶段更容易。每次读取一行时都使用链表。这样分配阶段会更快，但计算阶段会更慢。
从复杂性的角度来看，什么更好？
I have to read from a file an unknown number of rows and save them in to a structure (I would like to avoid a prepocessing to count the total number of elements).
After the reading phase I have to make some computations on each of the elements of these rows.
I figured out two ways:
Use
realloceach time I read a row. This way the allocation phase is slow but the computation phase is easier thanks to the index access.Use a linked list each time I read a row. This way the allocation phase is faster but the computation phase is slower.
What is better from a complexity point of view?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您将多久遍历一次链表？如果只有一次，就使用链表。另外一些事情：会有很多小额分配吗？您可以创建一些较小的缓冲区（假设有 10 行）并将它们链接在一起。但这都是一个分析问题。
我会先做最简单的事情，看看是否符合我的需求，然后我才会考虑优化。
有时，即使第二最佳解决方案也完全满足需求，人们也会浪费太多时间考虑最佳方案。
How often will you traverse the linked list? If it's only once go for the linked-list. Another few things: vill there be a lot of small allocations? You could make a few smaller buffers for let's say 10 lines and link those togeteher. But that's all a question of profiling.
I'd do the simplest thing first and see if that fits my needs only then i'd think about optimizing.
Sometimes one wastes too much time thinking about the optimum even when the second best solution also fits the needs perfectly.
如果没有关于如何使用这些信息的更多详细信息，就很难对其复杂性进行评论。但是，这里有一些想法：
Without more details on how you are going to use the information, it is a bit tough to comment on the complexity. However, here are a few thoughts:
正如其他用户已经说过的：
Donald Knuth
我有一个使用 realloc 的不同建议：在 C++ STL 中，每次插入对象并且没有足够的可用空间时，
std::vector容器都会增长。增长的大小取决于当前预分配的大小，但特定于实现。例如，您可以保存预分配对象的实际数量。如果大小用完，您可以使用当前分配的双倍空间量调用reallocate。我希望这是可以理解的！当然，需要注意的是，您可能会分配比实际消耗和需要更多的空间。
as other users already have stated:
Donald Knuth
I have a different proposal using
realloc: in the C++ STL thestd::vectorcontainer grows every time an object is inserted and not enough space is available. The size of the growing depends on the current pre-allocated size but is implementation specific. For example, you could save the actual number of preallocated objects. If the size runs out, you callreallocatewith the double amount of space as currently allocated. I hope this was somewhat understandable!The caveeat is of course, that you propably will allocate more space than you actually will consume and need.