Hi Neil! :-)

 NH> I don't know of a 32-bit real system.  By "real" I take
it that you 
 NH> mean a system using segments and offsets.  I'll bet the paging system
 NH> in memory looks forward to flexing its muscles with that.  Whatever, I 
 NH> think that it's time I try it out for myself.
What I meant was that you need to initialize all that memory for the hash
table and also the full table will never fit into the CPU's cache, meaning
you'll have lots of real memory accesses, which are slow.

For one of my projects, I did a rgb2yuv colorspace conversion routine in
two variants. One used a full lookup table (256MB), the other a smaller 8KB
table and some fixed-point int additions and shifts. The variant with the
8KB table turned out to be faster because the whole table did fit into the
CPU L1 cache and stayed there because it was only occupying 1/8th of the
cache and accessed frequently. The variant with the large table had almost
no computations in it, but the memory accesses were killing performance.

What I'm saying is that sometimes an algorithm that looks faster on paper
turns out to suck in practise.

 PS>> The most primitive algorithm for this problem 
 PS>> (compare each with each) would be O(n^2).
 NH> Yipes, I hope it doesn't come to that.
That one is very memory efficient, though, and good enough for smaller
input sets. Think about using your approach for 64 bit integers, how much
memory would your hash table consume?

Ciao
Pascal

--- Msged/LNX 6.1.1