Perhaps this is way ancient, but in case it's not, here goes.
I just ran a simulation prog (see below) for comparing linear versus
exponential methods of key index insertion.
Result? When a key index currently contains 0, 1, 2, 3, or 5 keys,
exponential method takes one or two hits longer than linear insertion.
But for keyindexes currently containing any other number of keys, the
exponential method wins, becoming more efficient with indexes containing
larger numbers of keys.
As would be expected, it's order log n.
If a key index contains a billion keys, it takes 60 hits to find the next
free key.
Algorithm is to start at a guess of 1, and keep doubling the guess till the
key request fails, then binary search till the next empty key slot is found.
OK - that's my bit of research for the night.
Would some hard-core hacker like to come up with a multi-thread version,
which for n threads will yield the fastest possible result?
Cheers
David
-----------------------------
// key index simulation prog
#include <stdio.h>
long findnextfreekey(long actual);
int keyexists(long guess, long actual);
long max_keyfound_hits = 0;
long max_keynotfound_hits = 0;
main(int argc, char *argv[])
{
long max;
long curkey;
char buf[80];
printf("Max free index num: ");
fflush(stdout);
gets(buf);
sscanf(buf, "%ld", &max);
for (curkey = 1; curkey <= max; curkey++)
findnextfreekey(curkey);
printf("Max successful hits = %ld, max failed hits = %ld\n",
max_keyfound_hits, max_keynotfound_hits);
printf("Press <enter> to quit");
fflush(stdout);
getchar();
}
long findnextfreekey(long actual)
{
long guess;
long prev_yes = 0;
long prev_no = -1;
long prev_guess = 0;
long num_keyfound_hits = 0;
long num_keynotfound_hits = 0;
guess = 1;
while (1)
{
if (prev_guess == guess)
{
printf("actual=%ld, guess=%ld, keyfoundhits=%ld, keynotfoundhits=%ld,
totalhits=%ld\n",
actual, guess + 1, num_keyfound_hits, num_keynotfound_hits,
num_keyfound_hits + num_keynotfound_hits);
if (num_keyfound_hits > max_keyfound_hits)
max_keyfound_hits = num_keyfound_hits;
if (num_keynotfound_hits > max_keynotfound_hits)
max_keynotfound_hits = num_keynotfound_hits;
return guess + 1;
}
prev_guess = guess;
if (keyexists(guess, actual))
{
num_keyfound_hits++;
prev_yes = guess;
if (prev_no == -1)
guess *= 2;
else
guess = (guess + prev_no) / 2;
}
else
{
num_keynotfound_hits++;
prev_no = guess;
guess = (prev_yes + guess) / 2;
}
}
}
int keyexists(long guess, long actual)
{
return (guess < actual);
}
_______________________________________________
Devl mailing list
Devl at freenetproject.org
http://lists.freenetproject.org/mailman/listinfo/devl
