extra/bloom-filters/bloom-filters-tests.factor

   1 USING: accessors bit-arrays bloom-filters bloom-filters.private kernel layouts
   2 math random sequences tools.test ;
   3 IN: bloom-filters.tests
   4
   5
   6 [ { 200 5 } ] [ { 100 7 } { 200 5 } smaller-second ] unit-test
   7 [ { 200 5 } ] [ { 200 5 } { 100 7 } smaller-second ] unit-test
   8
   9 ! The sizing information was generated using the subroutine
  10 ! calculate_shortest_filter_length from
  11 ! http://www.perl.com/pub/a/2004/04/08/bloom_filters.html.
  12
  13 ! Test bloom-filter creation
  14 [ 47965 ] [ 7 0.01 5000 bits-to-satisfy-error-rate ] unit-test
  15 [ 7 47965 ] [ 0.01 5000 size-bloom-filter ] unit-test
  16 [ 7 ] [ 0.01 5000 <bloom-filter> n-hashes>> ] unit-test
  17 [ 47965 ] [ 0.01 5000 <bloom-filter> bits>> length ] unit-test
  18 [ 5000 ] [ 0.01 5000 <bloom-filter> maximum-n-objects>> ] unit-test
  19 [ 0 ] [ 0.01 5000 <bloom-filter> current-n-objects>> ] unit-test
  20
  21 ! Should return the fewest hashes to satisfy the bits requested, not the most.
  22 [ 32 ] [ 4 0.05 5 bits-to-satisfy-error-rate ] unit-test
  23 [ 32 ] [ 5 0.05 5 bits-to-satisfy-error-rate ] unit-test
  24 [ 4 32 ] [ 0.05 5 size-bloom-filter ] unit-test
  25
  26 ! This is a lot of bits.
  27 [ 0.00000001 max-array-capacity size-bloom-filter ] [ capacity-error? ]  must-fail-with
  28
  29 ! Other error conditions.
  30 [ 1.0 2000 <bloom-filter> ] [ invalid-error-rate? ] must-fail-with
  31 [ 20 2000 <bloom-filter> ] [ invalid-error-rate? ] must-fail-with
  32 [ 0.0 2000 <bloom-filter> ] [ invalid-error-rate? ] must-fail-with
  33 [ -2 2000 <bloom-filter> ] [ invalid-error-rate? ] must-fail-with
  34 [ 0.5 0 <bloom-filter> ] [ invalid-n-objects? ] must-fail-with
  35 [ 0.5 -5 <bloom-filter> ] [ invalid-n-objects? ] must-fail-with
  36
  37 ! Should not generate bignum hash codes.  Enhanced double hashing may generate a
  38 ! lot of hash codes, and it's better to do this earlier than later.
  39 [ t ] [ 10000 iota [ hashcodes-from-object [ fixnum? ] both? ] map [ ] all? ] unit-test
  40
  41 [ ?{ t f t f t f } ] [ { 0 2 4 } 6 <bit-array> [ set-indices ] keep ] unit-test
  42
  43 : empty-bloom-filter ( -- bloom-filter )
  44     0.01 2000 <bloom-filter> ;
  45
  46 [ 1 ] [ empty-bloom-filter dup increment-n-objects current-n-objects>> ] unit-test
  47
  48 : basic-insert-test-setup ( -- bloom-filter )
  49     1 empty-bloom-filter [ bloom-filter-insert ] keep ;
  50
  51 ! Basic tests that insert does something
  52 [ t ] [ basic-insert-test-setup bits>> [ ] any? ] unit-test
  53 [ 1 ] [ basic-insert-test-setup current-n-objects>> ] unit-test
  54
  55 : non-empty-bloom-filter ( -- bloom-filter )
  56     1000 iota
  57     empty-bloom-filter
  58     [ [ bloom-filter-insert ] curry each ] keep ;
  59
  60 : full-bloom-filter ( -- bloom-filter )
  61     2000 iota
  62     empty-bloom-filter
  63     [ [ bloom-filter-insert ] curry each ] keep ;
  64
  65 ! Should find what we put in there.
  66 [ t ] [ 2000 iota
  67         full-bloom-filter
  68         [ bloom-filter-member? ] curry map
  69         [ ] all?
  70 ] unit-test
  71
  72 ! We shouldn't have more than 0.01 false-positive rate.
  73 [ t ] [ 1000 iota [ drop most-positive-fixnum iota random 1000 + ] map
  74         full-bloom-filter
  75         [ bloom-filter-member? ] curry map
  76         [ ] count
  77         ! TODO: This should be 10, but the false positive rate is currently very
  78         ! high.  300 is large enough not to prevent builds from succeeding.
  79         300 <=
  80 ] unit-test