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

Ketil Malde ketil at malde.org
Tue Jun 3 04:26:47 EDT 2008


"Thomas Hartman" <tphyahoo at gmail.com> writes:

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

I tried to modify examples/Words.hs to use Data.Set insted.  The
results look like this (first Bloom, second Data.Set, both compiled
with -O2):

    nmd9999:..filter/examples % ./Words   
    57025 words
    0.013326ss to count words
    Bloom { 4194304 bits } 
    0.050608ss to construct filter
    0.034806ss to query every element

    nmd9999:..filter/examples % ./WordsS                
    57025 words
    0.013291ss to count words
    False
    0.755115ss to construct filter
    0.423289ss to query every element

In order to avoid printing the entire set, while still evaluating it,
I replaced the printing of the set with printing the result of a
search for a non-existing element - I should really use a strict
insert, I guess.  Anyway, this hopefully gives an indication - looks
like a factor of 10 in this case, but it will depend on the size of
the data - more data, greater improvement.

BTW, Nice work, Bryan!  I have plans for this.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants


More information about the Haskell-Cafe mailing list