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 20:26 -0400
References	<dac673e7-fc1d-41fb-839e-97baa1bad360@s16g2000prf.googlegroups.com> <mailman.1168.1304538174.9059.python-list@python.org> <c3f5a37b-d268-4c28-8ec1-8f2ca8365aae@f31g2000pri.googlegroups.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.1176.1304555225.9059.python-list@python.org> (permalink)

Show all headers | View raw

On 5/4/2011 5:39 PM, Raymond Hettinger wrote:

> The 512 bits in h are progressively eaten-up between iterations.  So
> each pass yields a different (array index, bit_mask) pair.

Yeh, obvious now that I see it.

> It's easy to use the interactive prompt to show that different probes
> are produced on each pass:
>
>>>> bf = BloomFilter(num_bits=1000, num_probes=8)
>>>> pprint(list(bf.get_probes('Alabama')))
> [(19, 1073741824),
>   (11, 64),
>   (9, 134217728),
>   (25, 1024),
>   (24, 33554432),
>   (6, 16),
>   (7, 16777216),
>   (22, 1048576)]

Should have tried that.

> The 512 bits are uncorrelated -- otherwise sha512 wouldn't be much of
> a cryptographic hash ;)

> The fifty state example in the recipe is a reasonable demonstration
> that the recipe works as advertised.  It successfully finds all fifty
> states (the true positives) and it tries 100,000 negatives resulting
> in only a handful of false negatives.

I presume you mean 'false positives', as in the program comment and 
Wikipedia.

The test would be more convincing to many with 100000 other geographic 
names (hard to come by, I know), or other english names or words or even 
with longer random strings that matched the lengths of the state names. 
But an average of 5/100000 false positives in 5 runs is good.

-- 
Terry Jan Reedy

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

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