TDigest implements IQuantiles<Double> { public static TDigest merge(double compression, Iterable<TDigest> subData) { Preconditions.checkArgument(subData.iterator().hasNext(), "Can't merge 0 digests"); List<TDigest> elements = Lists.newArrayList(subData); int n = Math.max(1, elements.size() / 4); TDigest r = new TDigest(compression, elements.get(0).gen); if (elements.get(0).recordAllData) { r.recordAllData(); } for (int i = 0; i < elements.size(); i += n) { if (n > 1) { r.add(merge(compression, elements.subList(i, Math.min(i + n, elements.size())))); } else { r.add(elements.get(i)); } } return r; } TDigest(double compression);  TDigest(double compression, Random random); void add(double x); void add(double x, int w); void add(TDigest other); static TDigest merge(double compression, Iterable<TDigest> subData); void compress(); int size(); double cdf(double x); double quantile(double q); int centroidCount(); Iterable<? extends Group> centroids(); double compression(); TDigest recordAllData(); int byteSize(); int smallByteSize(); void asBytes(ByteBuffer buf); void asSmallBytes(ByteBuffer buf); static void encode(ByteBuffer buf, int n); static int decode(ByteBuffer buf); static TDigest fromBytes(ByteBuffer buf); void offer(Double value); Double getQuantile(double q); final static int VERBOSE_ENCODING; final static int SMALL_ENCODING; }
@Test public void testMerge() { Random gen = RandomUtils.getRandom(); for (int parts : new int[]{2, 5, 10, 20, 50, 100}) { List<Double> data = Lists.newArrayList(); TDigest dist = new TDigest(100, gen); dist.recordAllData(); List<TDigest> many = Lists.newArrayList(); for (int i = 0; i < 100; i++) { many.add(new TDigest(100, gen).recordAllData()); } List<TDigest> subs = Lists.newArrayList(); for (int i = 0; i < parts; i++) { subs.add(new TDigest(50, gen).recordAllData()); } for (int i = 0; i < 100000; i++) { double x = gen.nextDouble(); data.add(x); dist.add(x); subs.get(i % parts).add(x); } dist.compress(); Collections.sort(data); List<Double> data2 = Lists.newArrayList(); for (TDigest digest : subs) { for (TDigest.Group group : digest.centroids()) { Iterables.addAll(data2, group.data()); } } Collections.sort(data2); assertEquals(data.size(), data2.size()); Iterator<Double> ix = data.iterator(); for (Double x : data2) { assertEquals(ix.next(), x); } TDigest dist2 = TDigest.merge(50, subs); for (double q : new double[]{0.001, 0.01, 0.1, 0.2, 0.3, 0.5}) { double z = quantile(q, data); double e1 = dist.quantile(q) - z; double e2 = dist2.quantile(q) - z; System.out.printf("quantile\t%d\t%.6f\t%.6f\t%.6f\t%.6f\t%.6f\n", parts, q, z - q, e1, e2, Math.abs(e2) / q); assertTrue(String.format("parts=%d, q=%.4f, e1=%.5f, e2=%.5f, rel=%.4f", parts, q, e1, e2, Math.abs(e2) / q), Math.abs(e2) / q < 0.1); assertTrue(String.format("parts=%d, q=%.4f, e1=%.5f, e2=%.5f, rel=%.4f", parts, q, e1, e2, Math.abs(e2) / q), Math.abs(e2) < 0.015); } for (double x : new double[]{0.001, 0.01, 0.1, 0.2, 0.3, 0.5}) { double z = cdf(x, data); double e1 = dist.cdf(x) - z; double e2 = dist2.cdf(x) - z; System.out.printf("cdf\t%d\t%.6f\t%.6f\t%.6f\t%.6f\t%.6f\n", parts, x, z - x, e1, e2, Math.abs(e2) / x); assertTrue(String.format("parts=%d, x=%.4f, e1=%.5f, e2=%.5f", parts, x, e1, e2), Math.abs(e2) < 0.015); assertTrue(String.format("parts=%d, x=%.4f, e1=%.5f, e2=%.5f", parts, x, e1, e2), Math.abs(e2) / x < 0.1); } } }