Moduletdigest-0.3Haskell2010

Data.TDigest.Tree.Internal

Internals of TDigest.

Tree implementation is based on Adams’ Trees Revisited by Milan Straka http://fox.ucw.cz/papers/bbtree/bbtree.pdf

1 type
29 values

Packagetdigest-0.3
Exports30
LanguageHaskell2010
LicenceBSD-3-Clause
SourceInternal.hs

datadata TDigest (compression :: Nat)

TDigest is a tree of centroids.

compression is a 1/δ. The greater the value of compression the less likely value merging will happen.

Constructors

Node !Size !Mean !Weight !Weight !(TDigest compression) !(TDigest compression)
Tree node
Nil
Empty tree

Instances7Reducer, Show, Semigroup, Monoid, NFData, Binary, …

KnownNat comp => Reducer Double (TDigest comp)Defined in tdigest-0.3 · Data.TDigest.Tree.Internal
Both cons and snoc are insert
Show (TDigest compression)Defined in tdigest-0.3 · Data.TDigest.Tree.Internal
KnownNat comp => Semigroup (TDigest comp)Defined in tdigest-0.3 · Data.TDigest.Tree.Internal
KnownNat comp => Monoid (TDigest comp)Defined in tdigest-0.3 · Data.TDigest.Tree.Internal
NFData (TDigest comp)Defined in tdigest-0.3 · Data.TDigest.Tree.Internal
TDigest has only strict fields.
KnownNat comp => Binary (TDigest comp)Defined in tdigest-0.3 · Data.TDigest.Tree.Internal
TDigest isn't compressed after de-serialisation, but it can be still smaller.
HasHistogram (TDigest comp) MaybeDefined in tdigest-0.3 · Data.TDigest.Tree.Internal

But*, the benefit vs. code explosion is not yet worth.

29 declarations

valuegetCentroids :: TDigest comp -> [Centroid]

valuetotalWeight :: TDigest comp -> Weight

Total count of samples.

Example1 expression

>>> totalWeight (tdigest [1..100] :: TDigest 5)100.0

valuesize :: TDigest comp -> Int

valueminimumValue :: TDigest comp -> Mean

Center of left-most centroid. Note: may be different than min element inserted.

Example1 expression

>>> minimumValue (tdigest [1..100] :: TDigest 3)1.0

valuemaximumValue :: TDigest comp -> Mean

Center of right-most centroid. Note: may be different than max element inserted.

Example1 expression

>>> maximumValue (tdigest [1..100] :: TDigest 3)99.0

valueemptyTDigest :: TDigest comp

valuecombineDigest

:: KnownNat comp
=> TDigest comp
-> TDigest comp
-> TDigest comp

valueinsertCentroid :: KnownNat comp => Centroid -> TDigest comp -> TDigest comp

valuenode :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp

Constructor which calculates size and total weight.

valuebalanceR :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp

Balance after right insertion.

valuebalanceL :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp

Balance after left insertion.

valuenode'

:: Int
-> Mean
-> Weight
-> Weight
-> TDigest comp
-> TDigest comp
-> TDigest comp

Alias to Node

valuesingNode :: Mean -> Weight -> TDigest comp

Create singular node.

valuecombinedCentroid :: Mean -> Weight -> Mean -> Weight -> Centroid

Add two weighted means together.

valuethreshold

:: Double
total weight
-> Double
quantile
-> Double
compression (1/δ)
-> Double

Calculate the threshold, i.e. maximum weight of centroid.

valuecompress :: KnownNat comp => TDigest comp -> TDigest comp

Compress TDigest.

Reinsert the centroids in "better" order (in original paper: in random) so they have opportunity to merge.

Compression will happen only if size is both: bigger than relMaxSize * comp and bigger than absMaxSize.

valueforceCompress :: KnownNat comp => TDigest comp -> TDigest comp

Perform compression, even if current size says it's not necessary.

valuetoMVector

:: KnownNat comp
=> TDigest comp
t-Digest
-> ST s (MVector s (Centroid, Double))
return also a "space left in the centroid" value for "shuffling"

valuerelMaxSize :: Int

Relative size parameter. Hard-coded value: 25.

valueabsMaxSize :: Int

Absolute size parameter. Hard-coded value: 1000.

valuebalOmega :: Int

valuebalAlpha :: Int

valuedebugPrint :: TDigest comp -> IO ()

Output the TDigest tree.

valuevalid :: TDigest comp -> Bool

isRight . validate

valuevalidate :: TDigest comp -> Either String (TDigest comp)

Check various invariants in the TDigest tree.

valueinsert

:: KnownNat comp
=> Double
element
-> TDigest comp
-> TDigest comp

Insert single value into TDigest.

valueinsert'

:: KnownNat comp
=> Double
element
-> TDigest comp
-> TDigest comp

Insert single value, don't compress TDigest even if needed.

For sensibly bounded input, it makes sense to let TDigest grow (it might grow linearly in size), and after that compress it once.

valuesingleton :: KnownNat comp => Double -> TDigest comp

Make a TDigest of a single data point.

valuetdigest :: (Foldable f, KnownNat comp) => f Double -> TDigest comp

Strict foldl' over Foldable structure.

Example1 expression

>>> :set -XDataKinds