Changeset 35233 in project


Ignore:
Timestamp:
03/04/18 05:38:37 (7 months ago)
Author:
kon
Message:

add types, fix bloom-filter-p-false-positive (+inf.0 loop)

Location:
release/4/bloom-filter/trunk
Files:
2 edited

Legend:

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

    r35023 r35233  
    4141
    4242(import scheme chicken)
    43 
    4443(use
    4544  lolevel
     
    5655;;;
    5756
     57(define-type message-digest-primitive (struct message-digest-primitive))
     58(define-type message-digest-primitives (list-of message-digest-primitive))
     59
    5860;;
    5961
     
    8587
    8688;;; Record Type
     89
     90(define-type bloom-filter (struct bloom-filter))
    8791
    8892(define-record-type-variant bloom-filter (unsafe unchecked inline)
     
    158162;; Returns the upper-bound
    159163
     164(: optimum-size (number number --> fixnum fixnum))
     165;
    160166;n : capacity, p : probability of false-positive
    161167;=> m : bits, k : hashes
     
    164170    (values m (inexact->exact (ceiling (/ (* m LN2) n)))) ) )
    165171
     172(: optimum-k (number number --> fixnum))
     173;
    166174(define (optimum-k n m)
    167175  (inexact->exact (ceiling (* LN2 (/ m n)))) )
    168176
     177(: optimum-m (number number --> fixnum))
     178;
    169179(define (optimum-m k n)
    170180  (inexact->exact (ceiling (/ (* n k) LN2))) )    ;Similar to above
    171181
     182(: p-random-one-bit (number number number --> number))
     183;
    172184(define (p-random-one-bit k n m)
    173185  (- 1 (expt (- 1 (/ 1 m)) (* k n))) )
    174186
     187(: p-false-positive (number number number --> number))
     188;
    175189(define (p-false-positive k n m)
    176190  (expt (p-random-one-bit k n m) k) )
    177191
     192(: desired-m (number fixnum #!optional fixnum --> fixnum fixnum number))
     193;
    178194(define (desired-m p n . opt-k)
    179195  (check-positive-fixnum 'desired-m n)
    180196  (let loop ((m n))
    181197    (let* (
    182       (k (optional opt-k (optimum-k n m)) )
    183       (calc-p (p-false-positive k n m) ) )
     198      (k (optional opt-k (optimum-k n m)))
     199      (calc-p (p-false-positive k n m)) )
    184200      (cond
    185201        ((<= calc-p p)
     
    191207          (loop (fx+ m n)) ) ) ) ) )
    192208
     209(: actual-k (message-digest-primitives --> fixnum))
     210;
    193211(define (actual-k mdps)
    194212  (fold
     
    200218;;; Bloom Filter
    201219
     220(: bloom-filter? (* -> boolean : bloom-filter))
     221;
    202222(define (bloom-filter? obj)
    203223  (%bloom-filter? obj) )
     
    205225(define-check+error-type bloom-filter %bloom-filter?)
    206226
     227(: bloom-filter-algorithms (bloom-filter -> message-digest-primitives))
     228;
    207229(define (bloom-filter-algorithms bf)
    208230  (list-copy
     
    210232      (check-bloom-filter 'bloom-filter-algorithms bf))) )
    211233
     234(: bloom-filter-n (bloom-filter -> fixnum))
     235;
    212236(define (bloom-filter-n bf)
    213237  (%bloom-filter-n (check-bloom-filter 'bloom-filter-n bf)) )
    214238
     239(: bloom-filter-m (bloom-filter -> fixnum))
     240;
    215241(define (bloom-filter-m bf)
    216242  (%bloom-filter-m (check-bloom-filter 'bloom-filter-m bf)) )
    217243
     244(: bloom-filter-k (bloom-filter -> fixnum))
     245;
    218246(define (bloom-filter-k bf)
    219247  (%bloom-filter-k (check-bloom-filter 'bloom-filter-k bf)) )
    220248
     249;FIXME make-bloom-filter type is ugh
     250(: make-bloom-filter ((or fixnum number) (or fixnum message-digest-primitives) #!optional (or fixnum message-digest-primitives) -> bloom-filter))
     251;
    221252;( p n mdps) | ( m mdps [k])
    222253(define (make-bloom-filter m mdps #!optional des-k)
     
    249280    mdps) )
    250281
     282(: bloom-filter-p-false-positive (bloom-filter -> number))
     283;
    251284(define (bloom-filter-p-false-positive bf . n)
    252285  (check-bloom-filter 'bloom-filter-p-false-positive bf)
    253   (bloom-filter-p-false-positive
     286  (p-false-positive
    254287    (%bloom-filter-k bf)
    255288    (optional n (%bloom-filter-n bf))
    256289    (%bloom-filter-m bf)) )
    257290
     291(: bloom-filter-set! (bloom-filter * -> void))
     292;
    258293(define (bloom-filter-set! bf obj)
    259294  (check-bloom-filter 'bloom-filter-set! bf)
     
    268303  #;(void) )
    269304
     305(: bloom-filter-exists? (bloom-filter * --> boolean))
     306;
    270307(define (bloom-filter-exists? bf obj)
    271308  (let (
  • release/4/bloom-filter/trunk/bloom-filter.setup

    r35021 r35233  
    55(verify-extension-name "bloom-filter")
    66
    7 (setup-shared+static-extension-module 'bloom-filter (extension-version "1.2.0")
     7(setup-shared+static-extension-module 'bloom-filter (extension-version "1.2.1")
    88  #:inline? #t
    99  #:types? #t
Note: See TracChangeset for help on using the changeset viewer.