[Haskell-cafe] [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters

[Thomas Hartman]

What kind of speed do you get on your laptop for Data.Set? How much
faster is the bloom filter?

thomas.

2008/5/30 Bryan O'Sullivan <bos at serpentine.com>:
> I'm pleased to announce the availability of a fast Bloom filter library
> for Haskell.  A Bloom filter is a probabilistic data structure that
> provides a fast set membership querying capability.  It does not give
> false negatives, but has a tunable false positive rate.  (A false
> positive arises when the filter claims that an element is present, but
> in fact it is not.)
>
> The library is easy to use.  As an example, here's a reimplementation of
> the Unix "spell" command.
>
> import Data.BloomFilter.Easy (easyList, elemB)
>
> main = do
>  filt <- (easyList 0.01 . words) `fmap` readFile "dictionary.txt"
>  let check word | word `elemB` filt = ""
>                 | otherwise         = word ++ "\n"
>  interact (concat . map check . lines)
>
> It is also carefully tuned for performance.  On my laptop, I can sustain
> a construction or query rate well in excess of a million ByteStrings per
> second.
>
> Source code:
>
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bloomfilter
>
> Latest bits:
>
> darcs get http://darcs.serpentine.com/bloomfilter
>
>        <b
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>