Re: [tlug] array duplicate check [C] [ Solved ]

[Darren Cook <darren@example.com>]

> BTW, this is the first time I've actually seen an application for a
> Bloom filter.  I'm surprised nobody has called me on my N + M claim. :-)

Bloom filters ( http://en.wikipedia.org/wiki/Bloom_filter ) are not
reliable (they can return false positives). If I've understood
correctly, in terms of the original question it means it might say an
element in b[] is in a[] when in fact it isn't.

Darren

P.S. I'd love to hear if Nguyen actually got a measurable speed
improvement (or slowdown :-) for the whole process (i.e. including
loading data into memory from disk, etc.) by sorting unsorted data then
using an N logM algorithm, compared to just using the easy O(NM) algorithm.