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
--
http://mail.python.org/mailman/listinfo/python-list
