prob/hll
Hll
(defstruct Hll [regs : (Vec int) p : int m : int])
a HyperLogLog estimator with m = 2^p registers.
Since: probabilistic-spice-plan C1
hll-p
(hll-p [^borrow h : Hll] :)
the precision parameter.
| h | the estimator |
p, where m = 2^p is the register count.
Since: probabilistic-spice-plan C1
hll-m
(hll-m [^borrow h : Hll] :)
the register count.
| h | the estimator |
m = 2^p, the number of registers.
Since: probabilistic-spice-plan C1
hll-new
(hll-new [p : int] :)
create a HyperLogLog estimator with m = 2^p registers.
| p | precision in [4..16]; m = 2^p registers |
A new estimator with all registers zero.
(let [h (hll-new 14)] ...)
Since: probabilistic-spice-plan C1
hll-free
(hll-free [h : Hll] :)
release the register array.
| h | the estimator to free |
Since: probabilistic-spice-plan C1
hll-add!
(hll-add! [^borrow h : Hll key : int] :)
add an element to the estimator.
| h | the estimator (mutated in place) | |
| key | the integer key to add |
nil
Since: probabilistic-spice-plan C1
hll-cardinality
(hll-cardinality [^borrow h : Hll] :)
the estimated number of distinct elements.
| h | the estimator |
The estimated cardinality as a float. Uses the standard HLL raw estimate with small-range (linear counting) bias correction.
Since: probabilistic-spice-plan C1
hll-merge
(hll-merge [^borrow a : Hll ^borrow b : Hll] :)
pointwise max of two estimators' registers.
| a | first estimator | |
| b | second estimator (must have the same p) |
A new Hll whose registers are max(a[i], b[i]). Both inputs remain valid.
Since: probabilistic-spice-plan C1
Internal definitions
hash-clz-- position of the leftmost set bit in the low w bits of h.__hll-init-regs-- internal: push m zeros into the register Vec.__hll-add-update-- internal: update one register by max.__hll-zeros-loop-- internal: count zero registers.__hll-raw-sum-- internal: compute the sum of 2^(-r) as a float.__hll-merge-loop-- internal: pointwise max of registers.__hll-eq-loop-- internal: are all registers equal?Eq[Hll]-- same p and all registers equal.default-hll-p-- default precision for bottom.JoinSemilattice[Hll]-- join is pointwise max.BoundedJoin[Hll]-- the all-zero estimator of default precision is bottom.