xhist1.def is a template to make a histogram type for univariate/1D data monotonically transformed over (0,+Inf) to bin via any integer-keyed backing histo. The backing histo is itself generic over time weighting kernels (flat, linear, exponential) & those over their counter types (exponential time-decay needs SomeFloat). Finally, a xhist1.defMove template makes a wrapper type of a histo type that enables easy "only add & quantile query" use. An example program at the bottom of the module should mostly show how to use these.
This generalizes adix/lghisto. Quantile error is bounded by quantization error which is <~1/2 transformed bin width - eg. ~10^(log10(b/a)/n) w/X=log. Space-time trade-offs depend on how boundable data ranges are, but underflows & overflows are at least counted (until counters saturate!).
Definitions made by templates are not marked for export - xhist1.exportDefs if you want that. Also, I am aware that dynamic dispatch could be useful here, but that adds a noticeable overhead in tight loops over big data.
Templates
template def(T, X, X⁻¹, H; Hini: typed = false; Harg = 0.0)
-
Here T is the type that will be defined along with an init T, H is the type of histogram (e.g. Bist[uint32]), X is an expression transforming monotonically over (0, +Inf) some input x, e.g. ln, while X⁻¹ is its inverse function expression, e.g. exp. So, def Histo,ln,exp,Bist[uint32] is one instantiation. Besides defining the type, this also defines routines documented in detail over in https://c-blake.github.io/adix/adix/lghisto.html
- func underflows(s: T): type(s.hist.cdf 0) # bin0
- func overflows(s: T) : type(s.hist.cdf 0) # bin^1
- func low(s: T): float # .a
- func high(s: T): float # .b
- func nBin(s: T): int # .n - 2n+1 is num.bins * func hist(s: T): H # `.hist` - backing histo * proc init(s: var T, a=1e-16, b=1e20, n=8300) # init w/2n+1 bins
- proc initT(a=1e-16, b=1e20, n=8300): T # Same, but w/TypeName
- func space(s: T): int # Est.of total bytes used
- func tot(s: T): auto # Total count weight
- func toIx[F](s: T, x: F): int # x -> bin index
- func fromIx[F](s: T, i: int, offset: F=0.5): F # bin index -> bin center
- func binAB[F](s: T, x: F): (float, float) # whole range for bin(x)
- func add[F](s: var T, x: F, w: type(s.hist.cdf 0) = 1) # inc wt by w
- func pop[F](s: var T, x: F, w: type(s.hist.cdf 0) = 1) # dec wt by w
- iterator bins(s: T): (float, float, type(s.hist.cdf 0)) # yield (lo,hi,cnt)
- func $(s: T, nonZero=true): string # format histo
- func quantile[F](s: T, q: F): F # Basic quantile
- func cdf[F](s: T, x: F): type(s.hist.cdf 0) # Raw count; Callers /s.tot
- func merge(dst: var T, src: T) # Cnts from src into dst
template exportDefs(T)
- Source Edit