🚀 go-pugleaf

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

RAM isn't a problem ;~)

> too well above a certain size if there are enough history file entries
> to fill the hash table (bigger table will fix this but slows down
> searching).

My normal newshistory tends to sit at about 32K entries
(about 1 month worth) which comes to a little over 1.3 MB in
raw file size. So allowing for overheads that'd still be
less than 2MB. When I said large I wasn't meaning on an ISP
scale...

-- 
<URL:http://www.pierrot.co.uk/>                                  Team AMIGA
Yeast is yeast and nest is nest and never the mane shall tweet.