🚀 go-pugleaf

>>>>> "Terrance" == Terrance Richard Boyes <tez@pierrot.co.uk> wrote:

   Terrance> I'm looking for an efficient way to check for duplicate
   Terrance> Message-IDs in a large NewsHistory file against the
   Terrance> output of NEWNEWS (or XOVER after extracting the
   Terrance> Message-ID).

[...]

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

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.

It doesn't seem that slow in practice (at least not compared with the
speed at which the message-id's come in anyway), although I haven't
done any benchmarking with large numbers of message-ids (only a few
hundred or so at a time). Some who actually knows about efficiency of
algorithms is welcome to tell me this sucks :-)

Of course another way that might be easier, depending on what you're
going to do with the articles, is not bother with deduping at all but
do an explicit CHECK on the message-id before downloading it, and then
download and throw it at the local newsserver with TAKETHIS if the
initial reply code was positive.

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

   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.

http://home.att.net/~bobyetman/index.html

Stefan

On Tue, 13 Jul 1999 21:05:00 +0100 (BST), Terrance Richard Boyes 
   <tez@pierrot.co.uk> 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).

>As in those languages it's much quicker than scanning through
>an array.
>
>Any thoughts on the best way to do it in C ?

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.

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

If you want a general facility for adding elements to a database and
searching quickly, have a look for packages called btree and ctree.
These maintain a database in "balanced tree" style, so that the lookup
time is proportional to log(n) (n is number of elements in the
database).  There used to be at least one implementation which was
public domain generic C source.

Alternatively (my favourite solution), use C++ where the map class is
explicitly designed for that sort of thing.  However, it's a relatively
recent addition to C++ (in the last couple of years) and older C++
compilers didn't always have it implemented.

HTH

Chris C

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.

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?

Or, if there isn't anything in your library, look it up in any book on 
algorithms.

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

You take the ID string, and compute a hash code which is guaranteed to 
be between 0 and the size of the array. You look in the array at that 
slot - if it is empty, you haven't seen that ID before, and you place 
it in the slot. If it is not empty, you compare the actual message ID 
stored in the slot. If it is the same, you have had the ID before. What 
to do if it is different (i.e. your new ID and the one in the slot hash 
to the same value) varies. 

Some algorithms perform some computation on the hash code, to give a 
new slot number, repeating until the ID or an empty slot is found. The 
trick here is to choose a computation which will eventually visit all 
the slots only once - usually a prime number of slots is chosen, and 
the computation is a simple addition.

Other algorithms make each slot actually a linked list of all ID's that 
hash to the same code, and the list is searched linearly. This method 
allows the initial array to be smaller than the number of ID's, and is 
particularly good if the number of ID's is not known in advance.

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.

-- 
Nikki Locke, Trumphurst Ltd.      PC & Unix consultancy & programming
nikki@trmphrst.demon.co.uk            http://www.trumphurst.com/