prob/tdigest
TDigest
(defstruct TDigest [means : (Vec float) counts : (Vec int) compression : float])
a t-digest with parallel centroid arrays and compression.
Since: probabilistic-spice-plan C3
tdigest-compression
(tdigest-compression [^borrow td : TDigest] :)
the compression parameter (delta).
Since: probabilistic-spice-plan C3
tdigest-num-centroids
(tdigest-num-centroids [^borrow td : TDigest] :)
the number of centroids.
Since: probabilistic-spice-plan C3
tdigest-count
(tdigest-count [^borrow td : TDigest] :)
the total count (sum of all centroid counts).
Since: probabilistic-spice-plan C3
tdigest-new
(tdigest-new [compression : float] :)
create an empty t-digest.
| compression | the delta parameter (higher = more centroids = more accuracy) |
A new empty t-digest.
(let [td (tdigest-new 100.0)] ...)
Since: probabilistic-spice-plan C3
tdigest-free
(tdigest-free [td : TDigest] :)
release the centroid arrays.
Since: probabilistic-spice-plan C3
tdigest-add!
(tdigest-add! [^borrow td : TDigest value : float] :)
add a value to the t-digest.
| td | the t-digest (mutated in place) | |
| value | the float value to add |
nil
Since: probabilistic-spice-plan C3
tdigest-quantile
(tdigest-quantile [^borrow td : TDigest q : float] :)
approximate value at quantile q.
| td | the t-digest | |
| q | the quantile in [0, 1] |
The approximate value at quantile q. For q=0.5, the median. Returns 0.0 if the t-digest is empty.
Since: probabilistic-spice-plan C3
tdigest-merge
(tdigest-merge [^borrow a : TDigest ^borrow b : TDigest] :)
merge two t-digests into a new one.
| a | first t-digest | |
| b | second t-digest (should have the same compression) |
A new TDigest containing all centroids from both a and b, re-compressed. Both inputs remain valid.
Since: probabilistic-spice-plan C3
Internal definitions
__td-sum-counts-- internal: sum the counts array.__td-scale-- the k1 scale function.__td-insert-- internal: insert element at position i into sorted [0, i].__td-sort-loop-- internal: insertion sort outer loop over [1, n).__td-insertion-sort-- internal: sort parallel arrays by mean.__td-can-merge-- internal: can two adjacent centroids merge?__td-merge-absorb-- internal: try to absorb subsequent centroids.__td-merge-advance-- internal: start a new merged centroid at read-idx.__td-truncate-- internal: remove elements [write-idx, n) from both arrays.__td-compress-- internal: sort and merge centroids in place.__td-quantile-walk-- internal: find the centroid containing target rank.__td-copy-all-- internal: copy all centroids from src to dst.__td-eq-loop-- internal: are all centroids equal (means within tol)?Eq[TDigest]-- same number of centroids, same means and counts.default-td-compression-- default compression for bottom.JoinSemilattice[TDigest]-- join is merge.BoundedJoin[TDigest]-- the empty t-digest is bottom.