Histogram-based median search

Реализация алгоритма поиска медианы в большом одномерном массиве чисел.
Это измененный вариант известного алгоритма Торбена.
Привожу этот алгоритм здесь, чтобы на него можно было сослаться.
Сам алгоритм приводится без пояснений, пояснения и характеристики производительности позже выложу здесь же в виде статьи.

package anjlab.cubics.aggregate.median; import java.util.Arrays; /**  * Histogram-based implementation of median search algorithm.  *   * Based on N. Devillard's implementation of Torben Mogensen's algorithm   * ({@linkplain http://ndevilla.free.fr/median/median.pdf}).  *   * @author Dmitry Gusev   */ public class HistogramBasedMedianFinder {   private final int K;  //  number of ranges to create in histogram   private final double epsilon;      public HistogramBasedMedianFinder() {     this(15, 0.000000001d);   }      public HistogramBasedMedianFinder(int k, double epsilon) {     this.K = k;     this.epsilon = epsilon;   }      public double search(double[] m) {     int n = m.length;     int correction = n % 2 == 0 ? 1 : 0;     double min, max;     min = max = m[0];     for (int i = 1; i < n; i++) {       if (m[i] < min) min = m[i];       if (m[i] > max) max = m[i];     }     long leftOutRange = 0;     long rightOutRange = 0;     Histogram histogram = new Histogram();          while (true) {       histogram.init(min, max);              for (int i = 0; i < n; i++) {         histogram.add(m[i]);       }       long countInRanges = histogram.totalCount - histogram.others;       if (countInRanges == 1) {         return histogram.recentlyAdded;       }       long incCount = 0;              for (int i = 0; i < histogram.rangeCount; i++)  {         long rangeCount = histogram.counts[i];                  incCount += rangeCount;                  long rightOutCurrentRange = (countInRanges + rightOutRange) - incCount;                if (incCount + leftOutRange >= rightOutCurrentRange - correction) {           //  Median is in this range. Repeat search in this range           min = i == 0 ? histogram.start : histogram.ranges[i - 1];           max = histogram.ranges[i];                  if (almostSame(min, max)) {             return min;           }                      leftOutRange += (incCount - rangeCount);            rightOutRange = rightOutCurrentRange;                      break;         }       }     }   }      public boolean almostSame(double a, double b) {     return Math.abs(a - b) < epsilon;   }      private class Histogram {     public double start;     public double end;     private double step;     public double[] ranges = new double[K + 1];     public long[] counts = new long[K + 1];     public double recentlyAdded;     public long totalCount;     public long others;     public int rangeCount;     public void init(double start, double end) {       this.start = start;       this.end = end;       Arrays.fill(counts, 0);       others = 0;       totalCount = 0;       if (end < start || almostSame(start, end)) {         rangeCount = 0;       } else {         this.step = (end - start) / K;         int idx = 0;         for (double i = start; i < end; i += step) {           double right = i + step;           if (right > end) {             right = end;           }           ranges[idx++] = right;         }         rangeCount = idx;       }     }     public void add(double value) {       totalCount++;       if (value < start || value > end) {         others++;         return;       }       recentlyAdded = value;       //  binary search              int low = 0;       int high = rangeCount - 1;       while (low <= high) {         int mid = (high + low) >>> 1;         if (value <= ranges[mid]) {           if (mid > 0 && value < ranges[mid - 1]) {             high = mid - 1;  //  continue search           } else {             counts[mid]++;  //  we've found the range             return;           }         } else if (value > ranges[mid]) {           low = mid + 1;         }       }     }   }   }

Adobe Reader Team!

Сегодня вышло новое обновление Adobe Reader 8.2.0.
Как обычно, тихо и незаметно.
За все время сколько пользуюсь Reader'ом (с 2000 года, как только появился первый компьютер) ни разу не заглядывал в окошко Credits. Сегодня заглянул.

Оказывается в команде Adobe Reader'а почти 1000 человек! (971 если быть точным)

Может я никогда не уделял этому внимания, но по-моему это самая большая команда, про которую я слышал. Точнее я слышал про компании с несколькими десятками/сотнями разработчиков, но как-то в общем, без конкретики.

А тут в окошке Credits расписаны все команды и упомянут каждый член команды лично!



Решил ради интереса всех пересчитать, получилось целых 42 команды!

Между прочим, судя по (с) в окошке About, Reader'у уже 26-й год! (1984-2010)
Мы с ним почти ровесники :)

Желаю им и дальше расти и процветать!

p.s.

Team	# of members
Team Engineering	141
Quality Engineering	113
Engineering Management	55
Release Engineering	5
Product Management	14
Marketing and Business Management	22
Acrobat Administration	5
Globalization	16
Prerelease Programs	5
User Interface	14
Additional Engineering	62
Additional Quality Engineering	40
Additional Engineering Management	57
Additional Product, Marketing, and Business Management	9
Core Tech Management	14
Core Tech Adobe Graphics Manager	7
Core Tech Adobe Graphics Manager Printing	7
Core Tech Adobe XML Engine	6
Core Tech Color Management	4
Core Type	8
Core Tech PDF Libraries	10
Core Tech Architecture	12
Core Tech Scripting	6
Core Tech AMT	50
Core Tech AMT Quality Engineering	18
Core Tech Metadata	4
Core Tech Sangam	4
Core Tech Quality Engineering	52
Core Tech Admins	8
Adobe Production Quality Engineering Team	20
Legal	7
Visual Design	6
Adobe Systems Japan	13
Adobe Systems China	4
Type	9
Technical and Customer Support	15
Developer Support	18
Client Services Support	26
Learning Resources	43
Information Technology	12
Packaging and Manufacturing	14
Adobe.com Web Team	16
Total	971