🚀 go-pugleaf

Nikki Locke <nikki@trmphrst.demon.co.uk> wrote:
> In article <19990713.200500.0AA80202.PEaa@pierrot.co.uk>, Terrance 
> Richard Boyes wrote:
>> I'm looking for an efficient way to check for duplicate Message-IDs
>> in a large NewsHistory file against the output of NEWNEWS (or XOVER
>> after extracting the Message-ID).

>> Any thoughts on the best way to do it in C ?

> That's what hash tables are for, surely. I'm pretty sure that's how 
> PERL does it under the hood.

Probably, when using awk the read time is proportional to file
size, and check time is always practically instantaneous (at
least up to 1,000,000 items).

> Most C++ libraries include some form of Dictionary, which works like 
> the PERL method, and is usually implemented using hash tables. 

> I seem to remember standard Unix library functions to do hash tables - 
> were they called hcreate/hsearch/hdestroy?

I'd prefer not to use anything that may be OS dependant, certainly
nothing that uses runtime libs.

Though if I did the GDBM looks useful...

> The basic idea is that you create an array large enough to hold at 
> least the expected number of message ID's. 

Performance wise (at least in RDBMS terms) it makes more sense to 
leave a fair amount of empty space.

[snip]

> The efficiency of the hash table depends heavily on the suitability of 
> the initial hashing algorithm - if the ID's all hash to different 
> numbers, it is very fast. If they all hash to the same number, it is as 
> slow as a linear search.

One problem with message-ids is how to hash them uniquely, they
tend to be relatively large, so any prime-multiplication
type method would result in huge numbers. I did a few experiments
last night with simple things like adding up all the ASCII values
(and a variant splitting the message-id into <lhs@rhs>) and
there is a lot of overflow.

-- 
<URL:http://www.pierrot.co.uk/>                                  Team AMIGA
Life is like an onion: you peel off layer after layer, then you find
there is nothing in it.