Moduletdigest-0.3.1Haskell2010

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

Contents

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

Synopsis

data TDigest
value getCentroids
value totalWeight
value size
value minimumValue
value maximumValue
value emptyTDigest
value combineDigest
value insertCentroid
value node
value balanceR
value balanceL
value node'
value singNode
value combinedCentroid
value threshold
value compress
value forceCompress
value toMVector
value relMaxSize
value absMaxSize
value balOmega
value balAlpha
value debugPrint
value valid
value validate
value insert
value insert'
value singleton
value tdigest

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

datadata TDigest (compression :: Nat)

Source#

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.1 · Data.TDigest.Tree.Internal
Both cons and snoc are insert
Show (TDigest compression)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
KnownNat comp => Semigroup (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
KnownNat comp => Monoid (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
NFData (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
TDigest has only strict fields.
KnownNat comp => Binary (TDigest comp)Defined in tdigest-0.3.1 · 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.1 · Data.TDigest.Tree.Internal

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

valuegetCentroids :: TDigest comp -> [Centroid]

valuetotalWeight :: TDigest comp -> Weight

Source#

Total count of samples.

Example1 expression

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

valuesize :: TDigest comp -> Int

valueminimumValue :: TDigest comp -> Mean

Source#

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

Source#

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

Source#

Constructor which calculates size and total weight.

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

Source#

Balance after right insertion.

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

Source#

Balance after left insertion.

valuenode'

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

Source#

Alias to Node

valuesingNode :: Mean -> Weight -> TDigest comp

Source#

Create singular node.

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

Source#

Add two weighted means together.

valuethreshold

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

Source#

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

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

Source#

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

Source#

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

Source#

Relative size parameter. Hard-coded value: 25.

valueabsMaxSize :: Int

Source#

Absolute size parameter. Hard-coded value: 1000.

valuebalOmega :: Int

valuebalAlpha :: Int

valuedebugPrint :: TDigest comp -> IO ()

Source#

Output the TDigest tree.

valuevalid :: TDigest comp -> Bool

Source#

isRight . validate

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

Source#

Check various invariants in the TDigest tree.

valueinsert

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

Source#

Insert single value into TDigest.

valueinsert'

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

Source#

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

Source#

Make a TDigest of a single data point.

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

Source#

Strict foldl' over Foldable structure.

Example1 expression

>>> :set -XDataKinds