Date: Tue, 23 Sep 1997 00:48:48 -0700 From: John-Mark Gurney <gurney_j@efn.org> To: "Justin T. Gibbs" <gibbs@plutotech.com> Cc: current@FreeBSD.ORG Subject: Re: cvs commit: src/sys/conf files src/sys/dev/vx if_vx.c if_vxreg.h src/sys/i386/apm apm.c src/sys/i386/conf GENERIC files.i386 src/sys/i386/eisa 3c5x9.c aha1742.c aic7770.c bt74x.c eisaconf.c eisaconf.h if_fea.c if_vx_eisa.c src/sys/i386/i386 autoconf. Message-ID: <19970923004848.31356@hydrogen.nike.efn.org> In-Reply-To: <199709230651.AAA13934@pluto.plutotech.com>; from Justin T. Gibbs on Tue, Sep 23, 1997 at 12:51:04AM -0600 References: <19970922233930.12159@hydrogen.nike.efn.org> <199709230651.AAA13934@pluto.plutotech.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Justin T. Gibbs scribbled this message on Sep 23: > >> I'll stop for now, since this is as much a learning experience for me as > >> anything, and I don't want to wear out my welcome. :) :) > > > >now... I want to know why something more effecient isn't used.. something > >like a Fibonacci heap... this will provide amortized constant time for > >insert and minimum (find what is min)... then for actually deleting a > >key (performed once for each key when either expired or removed) it > >performs in O(lgn) time... > > I considered using a standard heap, but heaps are expensive/difficult > to grow on demand as it requires reallocating an array. I'm not > familiar with Fibonacci heaps though and perhaps this isn't a problem > with them. the Fibonacci heap still has that problem.. i.e. you actually have to allocate the space for each element... and it is actually slightly larger than most standard heaps as current data space for a node (with a void *data element) is 28bytes (assuming 4byts for poitners and ints) and an overhead of 16bytes (same assumption) for the base storage... but as I mentioned... the performance over amortized time is VERY nice... and there is no performance difference (none that is significant) if you remote an entry before it expires... all significant work is done when you remove the minimum element... and to remove a element early, you simply decrese the key to -inf (which can be done in O(1)) and then extract it... in order to get this performance... you still need the new calling method else you won't be able to find the key to remove unless you spend O(n) searching for it... ttyl.. -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking Live in Peace, destroy Micro$oft, support free software, run FreeBSD
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19970923004848.31356>