Re: LBAcache devel BUGFIX and improved release

X-Comment-To: Eric Auer

Hi!

11-=EE=CF=D1-2002 09:44 [email protected] (Eric Auer) wrote to fd-dev@top=
ica.com:

EA> Some algorithms from the past:
EA> - always use a new slot. If all slots are full, search for the slot tha=
t
EA>   was touched by findbin and newbin least often. May take lots of CPU.

     I suggest, for you will be useful book Jon Bentley "Programmin Pearls"=
,
2nd ed. There in chapter 14 described queues with priorities, implemented
with help of heap ("heap" as in "heapsort"). Some info you may find on the
site <http://netlib.bell-labs.com/cm/cs/pearls/>. He also makes short
introfuction into hashing, but for hashing better look in Knuth's excelent
book "Art of Computer Programming", 2nd ed., vol 3, "Sorting and Searching"=
,
chapter 6.4.

     There heapsort alwys gives fixed (relative small) time O(n*log n), but=

with correct implemenation hashing will be much-much better - O(1)!