fxQuantile · fxQuantileBy
The median, a p95, or any percentile — found in linear time, without sorting everything.
Lecture
The usual way to read a percentile is to sort a copy and index it:
sorted[((n - 1) * q).round()]. That is
O(n log n) to read one position.
fxQuantile(q, xs) returns the same value by
quickselect, which only partitions until that one
position is settled — O(n) on average, and median-of-three
pivots keep already-sorted and reversed input, the common real shapes,
linear too. The input is never reordered; the work happens on a copy.
The rank is nearest rank: the value at index
((n - 1) * q).round() of the sorted input. So
q = 0 is the minimum, 1 the maximum and
0.5 the median — the upper of the two middle values when
the length is even. Nothing is interpolated: the answer is always one of
the inputs. Empty input returns null; a q
outside [0, 1] throws ArgumentError.
fxQuantileBy(q, f, xs) ranks by a numeric key and returns
the element — the median-priced product, not the median price.
f runs once per element. On the chain they are
fx(numbers).quantile(q) and
fx(items).quantileBy(q, f). fxdart extension (not part of
FxTS).
Demo 1 · Median and percentiles
Demo 2 · quantileBy returns the element
Try it yourself
Exercise: replace the sort-and-index with one call.