🚀 go-pugleaf

In article <19990714.210035.0AA80202.TCaa@pierrot.co.uk>,
Terrance Richard Boyes <tez@pierrot.co.uk> wrote:
> Dave {Reply Address in.sig} <noone@llondel.demon.co.uk> wrote:
> > On 14 Jul 1999 05:51:54 GMT, Chris Croughton wrote:
> 
> >>The way I'd do it would be to read in the file, in file order, then use
> >>qsort (ANSI C routine) to sort it (or rather sort an array of pointers
> >>to the strings) and then use bsearch to find them.  You don't need to
> >>add the new IDs to the list as they come in, as they should be unique
> >>anyway among themselves.
> 
> > This is not true if you're talking to Demon's news machines. If I
> > crosspost an article to all the demon.* groups and then request
> > articles from those groups with NEWNEWS then I'll get offered the same
> 
> [snip]
> 
> That's true of any system that uses NEWNEWS since it's done 
> on a per group basis. And also of course a problem for anybody
> using XOVER as well unless you use the XREF to dedupe across
> groups.
> 
> > On the subject of KA9Q, will a hash table (as used in KA9Q) do the
> 
> I didn't even consider KA9Q, and having grabbed the code, yep
> it uses a nice simple hashing algorithm. Now all I've got to
> do is work the numbers out so it'll work nicely for 64K entries
> *in* RAM rather than 64KB *of* RAM !
> 
> > business efficiently enough? Hash each ID into a suitable number of
> > bits with a decent algorithm and you only need go search the list for
> > each hit in the hash table (which is hopefully small enough to be in
> > RAM and indexed in a reasonable manner). Obviously this doesn't work

I did some experiments when this first went into ka9q and found (in
live testing) that using two smaller tables with two different hash
generators worked better than one larger table. You hash the ID two
different ways and only if both get a hit do you search the history
file. I seem to recall (though it's been a *long* time since I looked
at the code), that the Demon customer who added the hashing adopted my
suggestion.