🚀 go-pugleaf

stefan the exiled <smd@hopf.demon.co.uk> wrote:

[snip]

> I can tell you the way *I* did it in C, which is probably far from the
> best way...

> Essentially just set up an ordered list and insert message-id's in it
> as they come out of NEWNEWS or XHDR. You could experiment with various
> ways of quickly finding the right place to insert (I don't think I
> bothered with much more than a binary chop) and if it's already there
> drop it.

I considered something like that, but binary searches don't scale
very well; especially if there are also a lot of inserts to be
done, which there certainly would be at least when reading the
history to start with.

[snip]

> There's also the various database libraries that I guess would work
> for this purpose.

Yeah, I first looked at slurp to see how it worked, they cheated
and just use whichever fetch() you've got the lib for ;)

>    Terrance> NB a pointer to some source what I want will do just as
>    Terrance> well as a detailed answer ;)

> Presumably suck has to do this (at least it claims to explicitly
> dedupe last time I used it). Probably worth a look anyway.

Just done so and suck uses both of the above. You can compile in
either use whichever DB-lib you've got available or it's got
some code to do the binary-tree thing otherwise. Though there's 
also an intriguing looking reference to INN2 and HashMessageID.

Hashing is the other way I thought of doing it, though there's
always that balance between memory and speed using a hash.
Though thinking about it, a quick read through the file to get
number of lines, it should be possible to get a good balance.
Allowing a few collisions can cut down memory usage a lot, and
would certainly be much faster than using btree.

The other thing I was considering is that unless you make a 
habit of setting the newsstamp back a long way then reading
the newshistory file backwards into the hash could give some
performance improvement when you do actually find a duplicate.

*Tez* off to have a look through the INN src now, and wondering
where he left that book about optimal hashing sol'ns :)

PS aaargh, and INN implements it's hashing by calling on MD5 lib
functions....

-- 
<URL:http://www.pierrot.co.uk/>                                  Team AMIGA
Gravity is a myth, the Earth sucks.