On Fri, Jun 16, 2006 at 10:55:05AM -0500, Jacob Yocom-Piatt wrote:
> the current code uses realloc in the manner suggested by the manpage:
>
> newsize = size + 1;
> time(&t1); // start timing realloc
> if ((newap = (int *)realloc(ap, newsize*sizeof(int))) == NULL) {
> free(ap);
> ap = NULL;
> size = 0;
> return (NULL);
> }
> time(&t2); // stop timing realloc; start timing fscanf
>
> as the size of ap grows, so does the time it takes to realloc the space.
Growing your array by only a constant amount each iteration takes
quadratic time. By instead doubling the array size each time as
necessary, you can reduce this to (amortized) linear time. (I believe
the man page's intention was to show how to avoid leaking memory, not
how to write an efficient program.)
Alternatively, just do as others have suggested and mmap() the file and
make an extra preliminary pass.
