futurice/haskell-tdigest

Name: haskell-tdigest

Owner: Futurice

Description: On-line accumulation of rank-based statistics such as quantiles and trimmed means

Created: 2016-11-01 23:32:28.0

Updated: 2018-05-20 15:50:20.0

Pushed: 2018-05-21 05:52:52.0

Homepage: null

Size: 317

Language: Haskell

GitHub Committers

User	Most Recent Commit	# Commits

Other Committers

User	Email	Most Recent Commit	# Commits

README

tdigest

A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means.

See original paper: “Computing extremely accurate quantiles using t-digest” by Ted Dunning and Otmar Ertl

Synopsis

ata.TDigest > median (tdigest [1..1000] :: TDigest 3)
 499.0090729817737

Benchmarks

Using 50M exponentially distributed numbers:

• average: 16s; incorrect approximation of median, mostly to measure prng speed
• sorting using vector-algorithms: 33s; using 1000MB of memory
• sparking t-digest (using some par): 53s
• buffered t-digest: 68s
• sequential t-digest: 65s

Example histogram

est-simple -m tdigest -d standard -s 100000 -c 10 -o output.svg -i 34
utput.svg example.svg
cape --export-png=example.png --export-dpi=80 --export-background-opacity=0 --without-gui example.svg