Add support for PERCENTILE_CONT semantics #380
Labels
Milestone
Comments
|
I'm trying out my suggested solution. I think that a function like this could be passed into a modified copy of Agg.percentileBy, to cover import java.util.function.Function;
@FunctionalInterface
public interface PercentileFunction<T,U> {
T apply(T t0, // value at index before percentile position
T t1, // next indexed value
double indexFraction,
Function<? super T, ? extends U> function); // to avoid need for two functions, for Tuple2<T,U> and T values
} |
|
I note that the https://infogalactic.com/info/Percentile does mention that linear interpolation is an option, just-like https://infogalactic.com/info/Median, for the median value of sorted, even length, numeric values. |
|
This seems to work, with the above function: // imports
public class Agg2 {
public static <T, U> Collector<T, ?, Optional<T>>
percentileBy(double percentile,
Function<? super T, ? extends U> mapper,
Comparator<? super U> comparator,
PercentileFunction<T, U> percentileFunction) {
if (percentile < 0.0 || percentile > 1.0)
throw new IllegalArgumentException("Percentile must be between 0.0 and 1.0");
return Collector.of(
(Supplier<ArrayList<Tuple2<T, U>>>) ArrayList::new,
(l, v) -> l.add(tuple(v, mapper.apply(v))),
(l1, l2) -> {
l1.addAll(l2);
return l1;
},
l -> {
final int size = l.size();
if (size == 0)
return Optional.empty();
else if (size == 1)
return Optional.of(l.get(0).v1);
l.sort(Comparator.comparing(t -> t.v2, comparator)); // Compare U
if (percentile == 0d)
return Optional.of(l.get(0).v1);
if (percentile == 1d)
return Optional.of(l.get(size - 1).v1);
// Limit fraction size, to stop common errors for double percentile values e.g. 2E-16.
// 0.5 is added because actual percentile value can be between values.
final double dIndex = ((double) Math.round(size * percentile * 1.0E6d) * 1.0E-6d) - 0.5d;
int index = (int) dIndex; // floor, for before or exact index
if (index >= size)
return Optional.of(l.get(size - 1).v1);
final Tuple2<T, U> t0 = l.get(index); // before or exact value
final double indexFraction = dIndex - index;
// If end or exact index, return t0 value.
if (++index == size || indexFraction == 0d)
return Optional.of(t0.v1);
final Tuple2<T, U> t1 = l.get(index); // after value
// Only call percentile function if t*.v1 values are different.
return (t0.v1.equals(t1.v1))
? Optional.of(t0.v1)
: Optional.of(percentileFunction.apply(t0.v1, t1.v1, indexFraction, mapper));
});
}Test code class Test {
public void main(String[] args) {
final Double[] values = {0d, 10d, 20d, 30d, 40d, 50d, 60d, 70d, 80d, 90d};
final PercentileFunction<Double, Double> floor = (t0, t1, f, m) -> {
double v0 = m.apply(t0);
double v1 = m.apply(t1);
return v0;
};
final PercentileFunction<Double, Double> ceil = (t0, t1, f, m) -> {
double v0 = m.apply(t0);
double v1 = m.apply(t1);
return v1;
};
final PercentileFunction<Double, Double> halfUp = (t0, t1, f, m) -> {
double v0 = m.apply(t0);
double v1 = m.apply(t1);
return f < 0.5d ? v0 : v1;
};
final PercentileFunction<Double, Double> interpolate = (t0, t1, f, m) -> {
double v0 = m.apply(t0);
double v1 = m.apply(t1);
return v0 - (v0 * f) + (v1 * f); // Linear interpolation
};
final String header = "percentile -> | Agg | floor | halfUp | interpolate | ceil";
System.out.println(header);
for (double p = 0d; p <= 1.00d; p += 0.05d) {
System.out.printf(" %5.3f -> | %4.1f | %4.1f | %4.1f | %4.1f | %4.1f%n",
p,
Seq.of(values).percentile(p).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), floor)).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), halfUp)).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), interpolate)).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), ceil)).orElseThrow());
}
System.out.println(header);
}
}Results: |
|
Thanks a lot for your analysis, @rwperrott. I'll look into this next week. |
lukaseder
changed the title
|
The current implementations implement the equivalent of SQL's Of course, we should offer |
|
The function parameter in PercentileFunction, thus U, now look redundant because function is unlikely to be useful for percentileBy operations, so can be simplified to this: public interface PercentileFunction<T> {
T apply(T t0,
T t1,
double indexFraction); // mapper proved to be redundant!
static <T> PercentileFunction<T> floor() {
return (t0, t1, f) -> t0;
}
static <T> PercentileFunction<T> ceil() {
return (t0, t1, f) -> t1;
}
static <T> PercentileFunction<T> halfUp() {
return (t0, t1, f) -> f < 0.5d ? t0 : t1;
}
static PercentileFunction<Double> interpolateDouble() {
return (t0, t1, f) -> t0 - (t0 * f) + (t1 * f);
}
}It is pointless collecting Tuple2<T,U> just to get a U result, so a list collection only needs to collect U, and be wrapped in collector which maps T to U. And example classes (not tested): // imports
public class Agg2 {
public static <T, U> Collector<T, ?, Optional<T>>
percentileBy(double percentile,
Function<? super T, ? extends U> mapper,
Comparator<? super U> comparator,
PercentileFunction<T> percentileFunction) {
if (percentile < 0.0 || percentile > 1.0)
throw new IllegalArgumentException("Percentile must be between 0.0 and 1.0");
return Collector.of(
(Supplier<ArrayList<Tuple2<T, U>>>) ArrayList::new,
(l, v) -> l.add(tuple(v, mapper.apply(v))),
(l1, l2) -> {
l1.addAll(l2);
return l1;
},
l -> {
final int size = l.size();
if (size == 0)
return Optional.empty();
else if (size == 1)
return Optional.of(l.get(0).v1);
l.sort(Comparator.comparing(t -> t.v2, comparator)); // Compare U
if (percentile == 0d)
return Optional.of(l.get(0).v1);
if (percentile == 1d)
return Optional.of(l.get(size - 1).v1);
// Limit fraction size, to stop common errors for double percentile values e.g. 2E-16.
// 0.5 is added because actual percentile value can be between values.
final double dIndex = ((double) Math.round(size * percentile * 1.0E6d) * 1.0E-6d) - 0.5d;
int index = (int) dIndex; // floor, for before or exact index
if (index >= size)
return Optional.of(l.get(size - 1).v1);
final Tuple2<T, U> t0 = l.get(index); // before or exact value
final double indexFraction = dIndex - index;
// If end or exact index, return t0 value.
if (++index == size || indexFraction == 0d)
return Optional.of(t0.v1);
final Tuple2<T, U> t1 = l.get(index); // after value
// Only call percentile function if t*.v1 values are different.
return (t0.v1.equals(t1.v1))
? Optional.of(t0.v1)
: Optional.of(percentileFunction.apply(t0.v1, t1.v1, indexFraction));
});
}import static PercentileFunction.*; // for static PercentileFunction provider methods.
class Test {
public void main(String[] args) {
final Double[] values = {0d, 10d, 20d, 30d, 40d, 50d, 60d, 70d, 80d, 90d};
final String header = "percentile -> | Agg | floor | halfUp | interpolate | ceil";
System.out.println(header);
for (double p = 0d; p <= 1.00d; p += 0.05d) {
System.out.printf(" %5.3f -> | %4.1f | %4.1f | %4.1f | %4.1f | %4.1f%n",
p,
Seq.of(values).percentile(p).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), floor())).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), halfUp())).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), interpolateDouble())).orElseThrow(),
Seq.of(values).collect(Agg2.percentile(p, Comparator.naturalOrder(), ceil())).orElseThrow());
}
System.out.println(header);
}
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Expected behavior and actual behavior:
Re: Median definition.
See code examples below.
The Agg.percentileBy method incorrectly assumes that index rounding is enough, but isn't when the the (size * percentile) still has an effectively non-zero factional part, and the floor indexed value and the next value are not equal.
I appreciate that not all Comparable types can be, or easily, added and divided, so I suggest that a modified percentile method, and median method, be added, accepting a type specific function, with parameters for the floor indexed value, the next indexed value and the fractional part of the index, to allow returning a more correct value. The function would only need to be called when the index has an effectively non-zero fractional part and the relevant indexed values are different. Any such new functionally should also exposed anywhere else the existing median and percentile* methods are also exposed e.g. Window.
Steps to reproduce the problem:
e.g. for median
prints 4.0, which is correct, because the exact middle value is 4.0,
prints 4.0 which is apparently incorrect, because the middle values are 4 and 5, so should print (4 + 5) / 2 = 4.5
Versions:
The text was updated successfully, but these errors were encountered: