Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!lll-winken!lll-tis!ames!joyce!sri-unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <1709@garth.UUCP>
Date: 2 Nov 88 00:21:51 GMT
Article-I.D.: garth.1709
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <8630@smoke.ARPA> <1704@dataio.Data-IO.COM> <119@twwells.uu
Reply-To: smryan@garth.UUCP (Steven Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 27

>>Realloc has to copy data, so this should be less efficient than just
>>doing another malloc & free.
>
>Err, umm, "realloc" is often used when you have e.g. an array with N

ERRR, UMMMM, we seem to have lost the point here.

It sounds as though someone's guessing what the data structure size should
be, guesses wrong, and has to increase it. If data structure size keeps
getting bumped bit by bit until the problem size is finally determined,
then we've got an O(n) structure which has been copied O(n/increment)=O(n)
times so that the cost of creating just this structure is O(n**2) so that
the overall time is quadratic, at best.

This sounds more like someone's using an inappropriate data structure which
is going to cost far more than any amount tweaking is going to get you.

Tweaking a program gives at best linear improvement.

Fixing the basic algorithm gives at least linear improvement.

--------------------------------------------------------------------------------
Well, gee, how do you allocate an indefinite sized array?

Glad you asked. I stuff it down a stack, each element individually
handcrafted with malloc, until I've reached the end and know exactly
how big it is. Then, IF I need random access, I copy it to an array.
Linear time.