Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!wugate!uunet!mcsun!ukc!edcastle!dcl-cs!gdt!gdr!exspes From: exspes@gdr.bath.ac.uk (P E Smee) Newsgroups: comp.lang.c Subject: Re: dynamic arrays (was: Re: lint on V.3) Message-ID: <1989Sep6.101037.29603@gdt.bath.ac.uk> Date: 6 Sep 89 10:10:37 GMT References: <1394@redsox.bsw.com> <1123@virtech.UUCP> <282@6sigma.UUCP> <14064@bloom-beacon.MIT.EDU> Reply-To: exspes@gdr.bath.ac.uk (P E Smee) Organization: University of Bristol c/o University of Bath Lines: 34 In article <14064@bloom-beacon.MIT.EDU> scs@adam.pika.mit.edu (Steve Summit) writes: >1. Many people feel that the allocation of the array should be > grown by multiplicative factors, not additive: > > nalloc *= 2; > > The drawback here is that you may allocate much more than you > need, and an intermediate allocation may fail unnecessarily, > so the code should probably be changed so it "backs off" and > tries again. The additive approach, although it could be > O(n**2) in data movement for some realloc implementations, has > proved to be efficient enough for my uses. It was suggested some years ago (about 15-20, I think) that growing things like this based on the Fibonacci series provided, on average, a better balance between the two problems of allocating too much and so wasting space, and on the other hand allocating too little and so having to do lots of reallocs. Don't know if it has been seriously looked at since. (The Fibonacci series, if you've never heard of it, is the one where each successive number is the sum of the two preceeding numbers, with the 0th and 1st members defined as being 1. So, 1, 1, 2, 3, 5, 8, 13, 21, ...) The idea being that if your first block was 1X units long, and you needed more, you'd realloc to 2X units, then to 3X units, then to 5X units, and so on. (Or looked at the other way, at the first growth you'd ADD 1X more units, at the second growth ADD 1X more units, then ADD 2X more units, etc.) -- Paul Smee | JANET: Smee@uk.ac.bristol Computer Centre | BITNET: Smee%uk.ac.bristol@ukacrl.bitnet University of Bristol | Internet: Smee%uk.ac.bristol@nsfnet-relay.ac.uk (Phone: +44 272 303132) | UUCP: ...!mcvax!ukc!gdr.bath.ac.uk!exspes