Changeset 35270 in project for release


Ignore:
Timestamp:
03/09/18 07:20:09 (9 months ago)
Author:
kon
Message:

fix bloom-filter-set! overcount possiblity, add types, use foldl

File:
1 edited

Legend:

Unmodified
Added
Removed
  • release/4/bloom-filter/trunk/bloom-filter.scm

    r35268 r35270  
    4343(use
    4444  lolevel
    45   srfi-1
    46   srfi-13
     45  (only srfi-1 list-copy take!)
    4746  iset
    4847  message-digest-primitive message-digest-type message-digest-item
    4948  record-variants
    50   type-checks type-errors
     49  (only type-checks
     50    define-check+error-type
     51    check-positive-fixnum check-flonum check-open-interval check-list)
    5152  hash-utils)
    5253
     
    177178;=> m : bits, k : hashes
    178179(define (optimum-size p n)
    179   (let ((m (inexact->exact (ceiling (/ (* n (log p)) -LN2^2)))))
     180  (let (
     181    (m (inexact->exact (ceiling (/ (* n (log p)) -LN2^2)))) )
    180182    (values m (inexact->exact (ceiling (/ (* m LN2) n)))) ) )
    181183
     
    220222;
    221223(define (actual-k mdps)
    222   (fold
    223     (lambda (len tot)
    224       (fx+ tot (fx/ len (unsigned-native-integer-size))) )
    225     0
    226     (message-digest-primitive-lengths mdps)) )
     224  (let (
     225    (siz (unsigned-native-integer-size)) )
     226    (foldl
     227      (lambda (tot len) (fx+ tot (fx/ len siz)))
     228      0
     229      (message-digest-primitive-lengths mdps)) ) )
    227230
    228231;;; Bloom Filter
     
    276279    (check-list 'make-bloom-filter mdps 'mdps))
    277280  ;get the "desired" # of hash values (k)
    278   (let ((act-k (actual-k mdps)))
     281  (let (
     282    (act-k (actual-k mdps)) )
    279283    (if (not des-k)
    280284      (set! des-k act-k)
     
    283287        (error 'make-bloom-filter "insufficient hash functions supplied" act-k des-k) ) ) )
    284288  ;bloom filter is a multi-hash into a bitvector
    285   (%make-bloom-filter
    286     0 m des-k
    287     (make-bit-vector m)
    288     (map (cut make-bloom-filter-hasher <> m) mdps)
    289     mdps) )
     289  (let (
     290    (bits (make-bit-vector m))
     291    (hashers (map (cut make-bloom-filter-hasher <> m) mdps)) )
     292    (%make-bloom-filter 0 m des-k bits hashers mdps) ) )
    290293
    291294(: bloom-filter-p-false-positive (bloom-filter --> number))
     
    301304;
    302305(define (bloom-filter-set! bf obj)
    303   (check-bloom-filter 'bloom-filter-set! bf)
    304   (%bloom-filter-bits-set!
    305     bf
    306     (bloom-filter-foldl
    307       bf
    308       (lambda (bits idx) (bit-vector-set! bits idx #t))
    309       (%bloom-filter-bits bf)
    310       obj))
    311   (%bloom-filter-n-set! bf (fx+ (%bloom-filter-n bf) 1))
    312   #;(void) )
     306  (unless (bloom-filter-exists? (check-bloom-filter 'bloom-filter-set! bf) obj)
     307    (let (
     308      (bits
     309        (bloom-filter-foldl
     310          bf
     311          (lambda (bits idx)
     312            (bit-vector-set! bits idx #t)
     313            bits )
     314          (%bloom-filter-bits bf)
     315          obj)) )
     316      (%bloom-filter-bits-set! bf bits) )
     317    (%bloom-filter-n-set! bf (fx+ (%bloom-filter-n bf) 1)) ) )
    313318
    314319(: bloom-filter-exists? (bloom-filter * --> boolean))
    315320;
    316321(define (bloom-filter-exists? bf obj)
    317   (let (
    318     (bits (%bloom-filter-bits (check-bloom-filter 'bloom-filter-exists? bf))))
    319     (fx=
    320       (%bloom-filter-k bf)
     322  (let* (
     323    (bits
     324      (%bloom-filter-bits
     325        (check-bloom-filter 'bloom-filter-exists? bf)))
     326    (refs
    321327      (bloom-filter-foldl
    322328        bf
    323         (lambda (cnt idx) (if (bit-vector-ref bits idx) (fx+ cnt 1) cnt))
     329        (lambda (cnt idx)
     330          (if (bit-vector-ref bits idx)
     331            (fx+ cnt 1)
     332            cnt ) )
    324333        0
    325         obj)) ) )
     334        obj)) )
     335    (fx= (%bloom-filter-k bf) refs) ) )
    326336
    327337) ;module bloom-filter
Note: See TracChangeset for help on using the changeset viewer.