Mailing List Archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

> 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 ( ) 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.


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.

Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links