Package com.tdunning.math.stats
Class ArrayDigest
java.lang.Object
com.tdunning.math.stats.TDigest
com.tdunning.math.stats.AbstractTDigest
com.tdunning.math.stats.ArrayDigest
Array based implementation of a TDigest.
This implementation is essentially a one-level b-tree in which nodes are collected into
pages typically with 32 values per page. Commonly, an ArrayDigest contains 500-3000
centroids. With 32 values per page, we have about 32 values per page and about 30 pages
which seems to give a nice balance for speed. Sizes from 4 to 100 are plausible, however.
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
static final int
static final int
static final int
Fields inherited from class com.tdunning.math.stats.AbstractTDigest
gen, recordAllData
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
add
(double x, int w) Adds a sample to a histogram.Iterator<com.tdunning.math.stats.ArrayDigest.Index>
allAfter
(double x) Iterator<com.tdunning.math.stats.ArrayDigest.Index>
allBefore
(double x) Returns an iterator which will give each element <= to x in non-increasing order.void
asBytes
(ByteBuffer buf) Outputs a histogram as bytes using a particularly cheesy encoding.void
asSmallBytes
(ByteBuffer buf) Serialize this TDigest into a byte buffer.int
byteSize()
Returns an upper bound on the number bytes that will be required to represent this histogram.double
cdf
(double x) Returns the fraction of all points added which are <= x.com.tdunning.math.stats.ArrayDigest.Index
ceiling
(double x) int
The number of centroids currently in the TDigest.An iterable that lets you go through the centroids in ascending order by mean.void
compress()
Re-examines a t-digest to determine whether some centroids are redundant.void
double
Returns the current compression factor.int
count
(com.tdunning.math.stats.ArrayDigest.Index index) com.tdunning.math.stats.ArrayDigest.Index
floor
(double x) Returns a cursor pointing to the first element <= x.static ArrayDigest
fromBytes
(ByteBuffer buf) Reads a histogram from a byte bufferlong
headSum
(com.tdunning.math.stats.ArrayDigest.Index limit) com.tdunning.math.stats.ArrayDigest.Index
increment
(com.tdunning.math.stats.ArrayDigest.Index x, int delta) double
mean
(com.tdunning.math.stats.ArrayDigest.Index index) double
quantile
(double q) Returns an estimate of the cutoff such that a specified fraction of the data added to this TDigest would be less than or equal to the cutoff.long
size()
Returns the number of points that have been added to this TDigest.int
Returns an upper bound on the number of bytes that will be required to represent this histogram in the tighter representation.Methods inherited from class com.tdunning.math.stats.AbstractTDigest
add, add, createCentroid, decode, encode, interpolate, isRecording, merge, recordAllData
Methods inherited from class com.tdunning.math.stats.TDigest
checkValue, createArrayDigest, createArrayDigest, createTreeDigest
-
Field Details
-
VERBOSE_ENCODING
public static final int VERBOSE_ENCODING- See Also:
-
SMALL_ENCODING
public static final int SMALL_ENCODING- See Also:
-
VERBOSE_ARRAY_DIGEST
public static final int VERBOSE_ARRAY_DIGEST- See Also:
-
SMALL_ARRAY_DIGEST
public static final int SMALL_ARRAY_DIGEST- See Also:
-
-
Constructor Details
-
ArrayDigest
public ArrayDigest(int pageSize, double compression)
-
-
Method Details
-
add
public void add(double x, int w) Description copied from class:TDigest
Adds a sample to a histogram. -
headSum
public long headSum(com.tdunning.math.stats.ArrayDigest.Index limit) -
mean
public double mean(com.tdunning.math.stats.ArrayDigest.Index index) -
count
public int count(com.tdunning.math.stats.ArrayDigest.Index index) -
compress
public void compress()Description copied from class:TDigest
Re-examines a t-digest to determine whether some centroids are redundant. If your data are perversely ordered, this may be a good idea. Even if not, this may save 20% or so in space. The cost is roughly the same as adding as many data points as there are centroids. This is typically < 10 * compression, but could be as high as 100 * compression. This is a destructive operation that is not thread-safe. -
compress
- Specified by:
compress
in classAbstractTDigest
-
size
public long size()Description copied from class:TDigest
Returns the number of points that have been added to this TDigest. -
cdf
public double cdf(double x) Description copied from class:TDigest
Returns the fraction of all points added which are <= x. -
quantile
public double quantile(double q) Description copied from class:TDigest
Returns an estimate of the cutoff such that a specified fraction of the data added to this TDigest would be less than or equal to the cutoff. -
centroidCount
public int centroidCount()Description copied from class:TDigest
The number of centroids currently in the TDigest.- Specified by:
centroidCount
in classTDigest
- Returns:
- The number of centroids
-
centroids
Description copied from class:TDigest
An iterable that lets you go through the centroids in ascending order by mean. Centroids returned will not be re-used, but may or may not share storage with this TDigest. -
allAfter
-
floor
public com.tdunning.math.stats.ArrayDigest.Index floor(double x) Returns a cursor pointing to the first element <= x. Exposed only for testing.- Parameters:
x
- The value used to find the cursor.- Returns:
- The cursor.
-
ceiling
public com.tdunning.math.stats.ArrayDigest.Index ceiling(double x) -
allBefore
Returns an iterator which will give each element <= to x in non-increasing order.- Parameters:
x
- The upper bound of all returned elements- Returns:
- An iterator that returns elements in non-increasing order.
-
increment
public com.tdunning.math.stats.ArrayDigest.Index increment(com.tdunning.math.stats.ArrayDigest.Index x, int delta) -
compression
public double compression()Description copied from class:TDigest
Returns the current compression factor.- Specified by:
compression
in classTDigest
- Returns:
- The compression factor originally used to set up the TDigest.
-
byteSize
public int byteSize()Returns an upper bound on the number bytes that will be required to represent this histogram. -
smallByteSize
public int smallByteSize()Returns an upper bound on the number of bytes that will be required to represent this histogram in the tighter representation.- Specified by:
smallByteSize
in classTDigest
- Returns:
- The number of bytes required.
-
asBytes
Outputs a histogram as bytes using a particularly cheesy encoding. -
asSmallBytes
Description copied from class:TDigest
Serialize this TDigest into a byte buffer. Some simple compression is used such as using variable byte representation to store the centroid weights and using delta-encoding on the centroid means so that floats can be reasonably used to store the centroid means.- Specified by:
asSmallBytes
in classTDigest
- Parameters:
buf
- The byte buffer into which the TDigest should be serialized.
-
fromBytes
Reads a histogram from a byte buffer- Returns:
- The new histogram structure
-