Table of Contents

RunningQuantile<T> Struct

Definition

Namespace
Bodu.Numerics
Assembly
Bodu.Numerics.dll
Package
Bodu.Numerics 1.0.0
Source
RunningQuantile{T}.Properties.cs

Estimates a single quantile of a sample stream in one forward pass and constant space, using the P² algorithm of Jain and Chlamtac (1985).

public struct RunningQuantile<T> where T : INumber<T>

Type Parameters

T

The numeric type of the samples.

Inherited Members
Extension Methods

Examples

var median = RunningQuantile<double>.CreateMedian();
foreach (var sample in new[] { 0.02, 0.15, 0.74, 3.39, 0.83, 22.37, 10.15, 15.43, 38.62, 15.92,
                               34.60, 10.28, 1.47, 0.40, 0.05, 11.39, 0.27, 0.42, 0.09, 11.37 })
    median.Add(sample);

median.Estimate;   // ≈ 4.44 (exact sorted median of this stream: 2.43)

var p95 = new RunningQuantile<int>(0.95);

Remarks

The estimator maintains five markers that track the minimum, the maximum, the target quantile, and the two quantiles halfway between it and the extremes, adjusting the middle markers with piecewise-parabolic (hence "P²") interpolation as samples arrive. Each Add(T) is O(1) and the state is a fixed scalar block - the samples themselves are never stored. Samples are widened to double with CreateChecked<TOther>(TOther), so Estimate is always a floating-point estimate.

The first five samples are held exactly; while fewer than five have been observed Estimate returns the linearly interpolated empirical quantile, and from the fifth sample onward the P² markers take over. The estimate is an approximation whose accuracy improves with stream length; for exact quantiles over small data, sort and index instead.

This is a mutable value type. Store it in a mutable field or local and pass it by ref; do not capture it in a lambda or iterator that expects reference semantics - each copy accumulates independently from the point of the copy, which is also the supported way to checkpoint. The default value is a valid empty median estimator; use the constructor for any other probability.

Unlike RunningStatistics<T>, two P² estimators cannot be merged - the marker states of two partitions do not compose. Partition-and-combine workloads should carry the mergeable moments in RunningStatistics<T> and reserve this type for single-stream use. Samples must be finite: NaN and infinite values are rejected by Add(T).

Constructors

RunningQuantile(double)

Initializes a new instance of the RunningQuantile<T> struct targeting the given quantile.

public RunningQuantile(double probability)

Parameters

probability double

The quantile to estimate, strictly between 0 and 1 (for example 0.5 for the median).

Exceptions

ArgumentOutOfRangeException

probability is not greater than 0 and less than 1 (NaN is rejected).

Properties

Count

Gets the number of samples accumulated so far.

public readonly long Count { get; }

Property Value

long

The sample count; zero for the empty estimator.

Estimate

Gets the current estimated value of the target quantile for the observed sample stream.

public readonly double Estimate { get; }

Property Value

double

The exact linearly interpolated empirical quantile while fewer than five samples are held; the P² middle-marker estimate from the fifth sample onward. From that point the value is an approximation and is not guaranteed to equal the quantile obtained by sorting all observed samples.

Exceptions

InvalidOperationException

The estimator is empty.

IsEmpty

Gets a value indicating whether the estimator contains no samples.

public readonly bool IsEmpty { get; }

Property Value

bool

true when Count is zero; otherwise false.

Probability

Gets the quantile this estimator targets, strictly between 0 and 1.

public readonly double Probability { get; }

Property Value

double

The target probability; 0.5 for the default (median) estimator.

Methods

Add(T)

Adds a sample to the estimator, updating the marker state in O(1).

public void Add(T value)

Parameters

value T

The sample to accumulate. Must be finite.

Exceptions

ArgumentException

value is NaN or infinite.

OverflowException

value is finite but outside the range representable by double (possible only for unbounded integer sample types such as BigInteger).

CreateMedian()

Creates an empty estimator targeting the median (probability 0.5).

public static RunningQuantile<T> CreateMedian()

Returns

RunningQuantile<T>

An empty median estimator, equivalent to new RunningQuantile<T>(0.5).

Reset()

Resets the estimator to the empty state, discarding all samples but preserving Probability.

public void Reset()

ToString()

Returns a culture-invariant summary of the estimator state for diagnostics.

public override readonly string ToString()

Returns

string

A string such as "p = 0.5, Count = 20, Estimate = 4.44", or "p = 0.5, Count = 0" when empty.

Applies to

ProductVersions
.NET8, 10