dmitrygusev online: January 2010

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


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 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

dmitrygusev online

Monday, January 25, 2010

Histogram-based median search

Friday, January 15, 2010

Adobe Reader Team!