[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[tor-commits] [metrics-web/release] Compute percentiles in connbidirect module using linear interpolation.



commit cda16c857e942a822df6b28f23518fc087bbc0f4
Author: Karsten Loesing <karsten.loesing@xxxxxxx>
Date:   Sat May 19 21:11:49 2018 +0200

    Compute percentiles in connbidirect module using linear interpolation.
    
    So far we computed percentiles in the connbidirect module using our
    own formula that picked existing values for median and quartiles.
    
    Now we're using Apache Commons Math with method R_7 which uses linear
    interpolation when a percentile lies between two data points.
    
    Implements the last part of #26035.
---
 .../metrics/stats/connbidirect/Main.java           | 31 ++++++++--
 .../metrics/stats/connbidirect/MainTest.java       | 71 +++++++++++++++++++---
 2 files changed, 88 insertions(+), 14 deletions(-)

diff --git a/src/main/java/org/torproject/metrics/stats/connbidirect/Main.java b/src/main/java/org/torproject/metrics/stats/connbidirect/Main.java
index b2dc1b6..468ffba 100644
--- a/src/main/java/org/torproject/metrics/stats/connbidirect/Main.java
+++ b/src/main/java/org/torproject/metrics/stats/connbidirect/Main.java
@@ -8,6 +8,8 @@ import org.torproject.descriptor.DescriptorReader;
 import org.torproject.descriptor.DescriptorSourceFactory;
 import org.torproject.descriptor.ExtraInfoDescriptor;
 
+import org.apache.commons.math3.stat.descriptive.rank.Percentile;
+
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -22,7 +24,6 @@ import java.io.StringReader;
 import java.text.DateFormat;
 import java.text.SimpleDateFormat;
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import java.util.SortedMap;
@@ -455,19 +456,39 @@ public class Main {
       }
     }
     final String[] quantiles = new String[] { "0.25", "0.5", "0.75" };
-    final int[] centiles = new int[] { 25, 50, 75 };
+    final double[] centiles = new double[] { 25.0, 50.0, 75.0 };
     for (Map.Entry<String, List<Short>> e
         : fractionsByDateAndDirection.entrySet()) {
       String dateAndDirection = e.getKey();
       List<Short> fractions = e.getValue();
-      Collections.sort(fractions);
+      SortedMap<Double, Short> computedPercentiles
+          = computePercentiles(fractions, centiles);
       for (int i = 0; i < quantiles.length; i++) {
         String dateDirectionAndQuantile = dateAndDirection + ","
             + quantiles[i];
-        short fraction = fractions.get((centiles[i] * fractions.size())
-            / 100);
+        short fraction = computedPercentiles.get(centiles[i]);
         aggregateStats.put(dateDirectionAndQuantile, fraction);
       }
     }
   }
+
+  /** Compute percentiles (greater than 0.0 and smaller than or equal 100.0) for
+   * the given list of values, and return a map with percentiles as keys and
+   * computed values as values. If the list of values is empty, the returned map
+   * contains all zeros. */
+  static SortedMap<Double, Short> computePercentiles(List<Short> valueList,
+      double ... percentiles) {
+    SortedMap<Double, Short> computedPercentiles = new TreeMap<>();
+    double[] valueArray = new double[valueList.size()];
+    for (int i = 0; i < valueList.size(); i++) {
+      valueArray[i] = valueList.get(i).doubleValue();
+    }
+    Percentile percentile = new Percentile()
+        .withEstimationType(Percentile.EstimationType.R_7);
+    percentile.setData(valueArray);
+    for (double p : percentiles) {
+      computedPercentiles.put(p, (short) Math.floor(percentile.evaluate(p)));
+    }
+    return computedPercentiles;
+  }
 }
diff --git a/src/test/java/org/torproject/metrics/stats/connbidirect/MainTest.java b/src/test/java/org/torproject/metrics/stats/connbidirect/MainTest.java
index 255cccf..69001da 100644
--- a/src/test/java/org/torproject/metrics/stats/connbidirect/MainTest.java
+++ b/src/test/java/org/torproject/metrics/stats/connbidirect/MainTest.java
@@ -11,6 +11,8 @@ import org.junit.Test;
 
 import java.io.ByteArrayOutputStream;
 import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.SortedMap;
 import java.util.SortedSet;
 import java.util.TreeMap;
@@ -242,15 +244,15 @@ public class MainTest {
   @Test
   public void testUpdateAggregateStatsTwoRawStat() {
     SortedMap<String, Short> expectedAggregateStats = new TreeMap<>();
-    expectedAggregateStats.put("2015-08-18,read,0.25", (short) 32);
-    expectedAggregateStats.put("2015-08-18,read,0.5", (short) 42);
-    expectedAggregateStats.put("2015-08-18,read,0.75", (short) 42);
-    expectedAggregateStats.put("2015-08-18,write,0.25", (short) 22);
-    expectedAggregateStats.put("2015-08-18,write,0.5", (short) 32);
-    expectedAggregateStats.put("2015-08-18,write,0.75", (short) 32);
-    expectedAggregateStats.put("2015-08-18,both,0.25", (short) 12);
-    expectedAggregateStats.put("2015-08-18,both,0.5", (short) 22);
-    expectedAggregateStats.put("2015-08-18,both,0.75", (short) 22);
+    expectedAggregateStats.put("2015-08-18,read,0.25", (short) 34);
+    expectedAggregateStats.put("2015-08-18,read,0.5", (short) 37);
+    expectedAggregateStats.put("2015-08-18,read,0.75", (short) 39);
+    expectedAggregateStats.put("2015-08-18,write,0.25", (short) 24);
+    expectedAggregateStats.put("2015-08-18,write,0.5", (short) 27);
+    expectedAggregateStats.put("2015-08-18,write,0.75", (short) 29);
+    expectedAggregateStats.put("2015-08-18,both,0.25", (short) 14);
+    expectedAggregateStats.put("2015-08-18,both,0.5", (short) 17);
+    expectedAggregateStats.put("2015-08-18,both,0.75", (short) 19);
     SortedSet<Main.RawStat> rawStats = new TreeSet<>();
     rawStats.add(new Main.RawStat(DATE_A, FPR_A, (short) 32, (short) 22,
         (short) 12));
@@ -258,4 +260,55 @@ public class MainTest {
         (short) 22));
     assertStatsCanBeAggregated(expectedAggregateStats, rawStats);
   }
+
+  @Test
+  public void testComputePercentilesZeroValues() {
+    List<Short> valueList = new ArrayList<>();
+    SortedMap<Double, Short> computedPercentiles = Main.computePercentiles(
+        valueList, 25.0, 50.0, 75.0);
+    assertEquals(0, computedPercentiles.get(25.0).shortValue());
+    assertEquals(0, computedPercentiles.get(50.0).shortValue());
+    assertEquals(0, computedPercentiles.get(75.0).shortValue());
+  }
+
+  @Test
+  public void testComputePercentilesTenValues() {
+    List<Short> valueList = new ArrayList<>();
+    valueList.add((short) 3);
+    valueList.add((short) 6);
+    valueList.add((short) 7);
+    valueList.add((short) 8);
+    valueList.add((short) 8);
+    valueList.add((short) 10);
+    valueList.add((short) 13);
+    valueList.add((short) 15);
+    valueList.add((short) 16);
+    valueList.add((short) 20);
+    SortedMap<Double, Short> computedPercentiles = Main.computePercentiles(
+        valueList, 25.0, 50.0, 75.0);
+    assertEquals(7, computedPercentiles.get(25.0).shortValue());
+    assertEquals(9, computedPercentiles.get(50.0).shortValue());
+    assertEquals(14, computedPercentiles.get(75.0).shortValue());
+  }
+
+  @Test
+  public void testComputePercentilesElevenValues() {
+    List<Short> valueList = new ArrayList<>();
+    valueList.add((short) 3);
+    valueList.add((short) 6);
+    valueList.add((short) 7);
+    valueList.add((short) 8);
+    valueList.add((short) 8);
+    valueList.add((short) 9);
+    valueList.add((short) 10);
+    valueList.add((short) 13);
+    valueList.add((short) 15);
+    valueList.add((short) 16);
+    valueList.add((short) 20);
+    SortedMap<Double, Short> computedPercentiles = Main.computePercentiles(
+        valueList, 25.0, 50.0, 75.0);
+    assertEquals(7, computedPercentiles.get(25.0).shortValue());
+    assertEquals(9, computedPercentiles.get(50.0).shortValue());
+    assertEquals(14, computedPercentiles.get(75.0).shortValue());
+  }
 }



_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits