Changeset 35270 in project
 Timestamp:
 03/09/18 07:20:09 (6 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

release/4/bloomfilter/trunk/bloomfilter.scm
r35268 r35270 43 43 (use 44 44 lolevel 45 srfi1 46 srfi13 45 (only srfi1 listcopy take!) 47 46 iset 48 47 messagedigestprimitive messagedigesttype messagedigestitem 49 48 recordvariants 50 typechecks typeerrors 49 (only typechecks 50 definecheck+errortype 51 checkpositivefixnum checkflonum checkopeninterval checklist) 51 52 hashutils) 52 53 … … 177 178 ;=> m : bits, k : hashes 178 179 (define (optimumsize 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)))) ) 180 182 (values m (inexact>exact (ceiling (/ (* m LN2) n)))) ) ) 181 183 … … 220 222 ; 221 223 (define (actualk mdps) 222 (fold 223 (lambda (len tot) 224 (fx+ tot (fx/ len (unsignednativeintegersize))) ) 225 0 226 (messagedigestprimitivelengths mdps)) ) 224 (let ( 225 (siz (unsignednativeintegersize)) ) 226 (foldl 227 (lambda (tot len) (fx+ tot (fx/ len siz))) 228 0 229 (messagedigestprimitivelengths mdps)) ) ) 227 230 228 231 ;;; Bloom Filter … … 276 279 (checklist 'makebloomfilter mdps 'mdps)) 277 280 ;get the "desired" # of hash values (k) 278 (let ((actk (actualk mdps))) 281 (let ( 282 (actk (actualk mdps)) ) 279 283 (if (not desk) 280 284 (set! desk actk) … … 283 287 (error 'makebloomfilter "insufficient hash functions supplied" actk desk) ) ) ) 284 288 ;bloom filter is a multihash into a bitvector 285 (%makebloomfilter 286 0 m desk 287 (makebitvector m) 288 (map (cut makebloomfilterhasher <> m) mdps) 289 mdps) ) 289 (let ( 290 (bits (makebitvector m)) 291 (hashers (map (cut makebloomfilterhasher <> m) mdps)) ) 292 (%makebloomfilter 0 m desk bits hashers mdps) ) ) 290 293 291 294 (: bloomfilterpfalsepositive (bloomfilter > number)) … … 301 304 ; 302 305 (define (bloomfilterset! bf obj) 303 (checkbloomfilter 'bloomfilterset! bf) 304 (%bloomfilterbitsset! 305 bf 306 (bloomfilterfoldl 307 bf 308 (lambda (bits idx) (bitvectorset! bits idx #t)) 309 (%bloomfilterbits bf) 310 obj)) 311 (%bloomfilternset! bf (fx+ (%bloomfiltern bf) 1)) 312 #;(void) ) 306 (unless (bloomfilterexists? (checkbloomfilter 'bloomfilterset! bf) obj) 307 (let ( 308 (bits 309 (bloomfilterfoldl 310 bf 311 (lambda (bits idx) 312 (bitvectorset! bits idx #t) 313 bits ) 314 (%bloomfilterbits bf) 315 obj)) ) 316 (%bloomfilterbitsset! bf bits) ) 317 (%bloomfilternset! bf (fx+ (%bloomfiltern bf) 1)) ) ) 313 318 314 319 (: bloomfilterexists? (bloomfilter * > boolean)) 315 320 ; 316 321 (define (bloomfilterexists? bf obj) 317 (let ( 318 (bits (%bloomfilterbits (checkbloomfilter 'bloomfilterexists? bf)))) 319 (fx= 320 (%bloomfilterk bf) 322 (let* ( 323 (bits 324 (%bloomfilterbits 325 (checkbloomfilter 'bloomfilterexists? bf))) 326 (refs 321 327 (bloomfilterfoldl 322 328 bf 323 (lambda (cnt idx) (if (bitvectorref bits idx) (fx+ cnt 1) cnt)) 329 (lambda (cnt idx) 330 (if (bitvectorref bits idx) 331 (fx+ cnt 1) 332 cnt ) ) 324 333 0 325 obj)) ) ) 334 obj)) ) 335 (fx= (%bloomfilterk bf) refs) ) ) 326 336 327 337 ) ;module bloomfilter
Note: See TracChangeset
for help on using the changeset viewer.