Realloc Vs Linked List Scanning

Question

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:

1. Use realloc each time I read a row. This way the allocation phase is slow but the computation phase is easier thanks to the index access.

2. 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?

Manualmanubrium

linked list for reading then mallock'ing for computing? – Seng

Answer 1

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.

Ballad

Answer 2

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:

• If you use realloc, it would likely be better to realloc to add "some" more items (rather than one each and every time). Typically, a good algorithm is to double the size each time.
• If you use a linked list, you could speed up the access in a simple post-processing step. Allocate an array of pointers to the items and traverse the list once setting the array elements to each item in the list.
• If the items are of a fixed size in the file, you could pre-compute the size simply by seeking to the end of the file, determining the size, divide by the item size and you have the result. Even if it is not a fixed size, you could possibly use this as an estimate to get "close" to the necessary size and reduce the number of reallocs required.

Equiprobable

Answer 3

as other users already have stated:

Premature optimization is the root of all evil

Donald Knuth

I have a different proposal using realloc: in the C++ STL the std::vector container 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 call reallocate with 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.

Sherrard

The second root of all evil is skipping "theory" classes, giving up on optimization entirely, and writing 50 million lines of hipster code for 3 decades that is 10,000 times slower than simple C, fail miserably every time an at scale constraint is reached, and cause a catastrophic loss of investor faith in the entire tech industry every dozen years or so... – Gazette

Upvoted your answer, and am implementing that way as well. All I'm saying is: optimizing code is how you "get gud," and that DKnuth meme may be obsolete given some of the nightmarish python out there these days. – Gazette