hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a..@apache.org
Subject svn commit: r1391711 - in /hadoop/common/trunk/hadoop-common-project/hadoop-common: CHANGES.txt src/main/java/org/apache/hadoop/metrics2/util/SampleQuantiles.java
Date Sat, 29 Sep 2012 00:59:04 GMT
Author: atm
Date: Sat Sep 29 00:59:04 2012
New Revision: 1391711

URL: http://svn.apache.org/viewvc?rev=1391711&view=rev
Log:
HADOOP-8866. SampleQuantiles#query is O(N^2) instead of O(N). Contributed by Andrew Wang.

Modified:
    hadoop/common/trunk/hadoop-common-project/hadoop-common/CHANGES.txt
    hadoop/common/trunk/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/metrics2/util/SampleQuantiles.java

Modified: hadoop/common/trunk/hadoop-common-project/hadoop-common/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/common/trunk/hadoop-common-project/hadoop-common/CHANGES.txt?rev=1391711&r1=1391710&r2=1391711&view=diff
==============================================================================
--- hadoop/common/trunk/hadoop-common-project/hadoop-common/CHANGES.txt (original)
+++ hadoop/common/trunk/hadoop-common-project/hadoop-common/CHANGES.txt Sat Sep 29 00:59:04
2012
@@ -280,6 +280,9 @@ Release 2.0.3-alpha - Unreleased 
 
   OPTIMIZATIONS
 
+    HADOOP-8866. SampleQuantiles#query is O(N^2) instead of O(N). (Andrew Wang
+    via atm)
+
   BUG FIXES
 
     HADOOP-8795. BASH tab completion doesn't look in PATH, assumes path to

Modified: hadoop/common/trunk/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/metrics2/util/SampleQuantiles.java
URL: http://svn.apache.org/viewvc/hadoop/common/trunk/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/metrics2/util/SampleQuantiles.java?rev=1391711&r1=1391710&r2=1391711&view=diff
==============================================================================
--- hadoop/common/trunk/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/metrics2/util/SampleQuantiles.java
(original)
+++ hadoop/common/trunk/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/metrics2/util/SampleQuantiles.java
Sat Sep 29 00:59:04 2012
@@ -210,9 +210,12 @@ public class SampleQuantiles {
     int rankMin = 0;
     int desired = (int) (quantile * count);
 
+    ListIterator<SampleItem> it = samples.listIterator();
+    SampleItem prev = null;
+    SampleItem cur = it.next();
     for (int i = 1; i < samples.size(); i++) {
-      SampleItem prev = samples.get(i - 1);
-      SampleItem cur = samples.get(i);
+      prev = cur;
+      cur = it.next();
 
       rankMin += prev.g;
 



Mime
View raw message