Return to BSD News archive
Xref: sserve comp.os.386bsd.questions:12262 comp.os.386bsd.development:2374 comp.os.386bsd.misc:3147 Path: sserve!newshost.anu.edu.au!harbinger.cc.monash.edu.au!msuinfo!agate!howland.reston.ans.net!gatech!nntp.msstate.edu!nntp.memphis.edu!nntp.rhodes.edu!zen.mathcs.rhodes.edu!stuart Newsgroups: comp.os.386bsd.questions,comp.os.386bsd.development,comp.os.386bsd.misc Subject: Re: Why does FreeBSD 1.1.5 say gets() is unsafe? Message-ID: <1994Aug11.102341.1020@rhodes> From: stuart@zen.mathcs.rhodes.edu (Brian L. Stuart) Date: 11 Aug 94 10:23:40 -0500 References: <311m2e$o33@agate.berkeley.edu> <324v1b$14g@boavista.bln.sub.org> <1994Aug10.151130.1017@rhodes> <CuDGIo.Jn6@cogsci.ed.ac.uk> Distribution: world Nntp-Posting-Host: zen.mathcs.rhodes.edu Lines: 36 In article <CuDGIo.Jn6@cogsci.ed.ac.uk>, richard@cogsci.ed.ac.uk (Richard Tobin) writes: |> In article <1994Aug10.151130.1017@rhodes> stuart@zen.mathcs.rhodes.edu (Brian L. Stuart) writes: |> >At the risk of picking an excessively fine nit (and mixing my metaphors), |> >a good argument can be made for doubling the size of the array rather |> >than adding a fixed amount. |> ... |> >It is true that doubling will lead to waste bounded by n |> >whereas adding a fixed amount bounds the waste by the increment. |> |> You can of course reduce the waste by increasing the space by, say, |> 20% each time instead of doubling. This will waste at most 20% of the |> required space and still be much faster than adding a constant amount |> in the cases where it matters. Good point. As long as you increase the size by a multiplicitive factor rather than an additive one, you'll get O(n) time behavior. Of course, you'll also have waste that is O(n) whereas an additive change leads to wast of O(1). |> |> >It seems to be the classic time vs. space tradeoff. |> |> Right, and the tradeoff allows plenty of points between the two you |> mention. True also. I didn't mean to imply that there were only two points. Tradeoffs usually involve a multitude of choices. I personally usually increase the size by a factor of 2 as a "happy medium" wrt the constants hidden by the big-O. Naturally, design decisions like these aren't etched in stone to be used in all situations. That's where experience and professional judgement come in---picking the right point in the tradeoff space. Brian L. Stuart Math/CS Dept, Rhodes College, Memphis, TN 38112 stuart@mathcs.rhodes.edu