Re: Today's fun and educational Python recipe

From	Terry Reedy <tjreedy@udel.edu>
Subject	Re: Today's fun and educational Python recipe
Date	2011-05-04 15:42 -0400
References	<dac673e7-fc1d-41fb-839e-97baa1bad360@s16g2000prf.googlegroups.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.1168.1304538174.9059.python-list@python.org> (permalink)

Show all headers | View raw

On 5/4/2011 2:17 PM, Raymond Hettinger wrote:
> Here's a 22-line beauty for a classic and amazing algorithm:
> http://bit.ly/bloom_filter
>
> The wiki article on the algorithm is brief and well-written:
> http://en.wikipedia.org/wiki/Bloom_filter

As I understand the article, the array of num_bits should have 
num_probes (more or less independent) bits set for each key. But as I 
understand the code

         for i in range(self.num_probes):
             h, array_index = divmod(h, num_words)
             h, bit_index = divmod(h, 32)
             yield array_index, 1 << bit_index

the same bit is being set or tested num_probes times. The last three 
lines have no dependence on i that I can see, so they appear to do the 
same thing each time. This seems like a bug.

The article says "For a good hash function with a wide output, there 
should be little if any correlation between different bit-fields of such 
a hash, so this type of hash can be used to generate multiple 
"different" hash functions by slicing its output into multiple bit 
fields. Alternatively, one can pass k different initial values (such as 
0, 1, ..., k − 1) to a hash function that takes an initial value; or add 
(or append) these values to the key." I do not see the code doing either 
of these.

-- 
Terry Jan Reedy

Thread

Today's fun and educational Python recipe Raymond Hettinger <python@rcn.com> - 2011-05-04 11:17 -0700
  Re: Today's fun and educational Python recipe Irmen de Jong <irmen@-NOSPAM-xs4all.nl> - 2011-05-04 21:02 +0200
    Re: Today's fun and educational Python recipe Raymond Hettinger <python@rcn.com> - 2011-05-04 12:13 -0700
      Re: Today's fun and educational Python recipe Irmen de Jong <irmen@-NOSPAM-xs4all.nl> - 2011-05-04 21:35 +0200
    Re: Today's fun and educational Python recipe Grant Edwards <invalid@invalid.invalid> - 2011-05-04 19:17 +0000
      Re: Today's fun and educational Python recipe Ben Finney <ben+python@benfinney.id.au> - 2011-05-05 09:33 +1000
    Re: Today's fun and educational Python recipe Chris Angelico <rosuav@gmail.com> - 2011-05-05 12:22 +1000
  Re: Today's fun and educational Python recipe Paul Rubin <no.email@nospam.invalid> - 2011-05-04 12:27 -0700
    Re: Today's fun and educational Python recipe Raymond Hettinger <python@rcn.com> - 2011-05-04 14:53 -0700
  Re: Today's fun and educational Python recipe Terry Reedy <tjreedy@udel.edu> - 2011-05-04 15:42 -0400
    Re: Today's fun and educational Python recipe Raymond Hettinger <python@rcn.com> - 2011-05-04 14:39 -0700
      Re: Today's fun and educational Python recipe Terry Reedy <tjreedy@udel.edu> - 2011-05-04 20:26 -0400
        Re: Today's fun and educational Python recipe Raymond Hettinger <python@rcn.com> - 2011-05-04 18:15 -0700
  Re: Today's fun and educational Python recipe nn <pruebauno@latinmail.com> - 2011-05-05 07:33 -0700

csiph-web