Вычисление Percentiles на лету

Ответ 1

По практическим соображениям и разумным значениям n вам лучше всего использовать кольцевой буфер примитивного int (для отслеживания самой старой записи) и linear сканировать для определения того, сколько значений меньше x.

Чтобы это было в O(log n), вам нужно было бы использовать что-то вроде Guavas TreeMultiset. Вот схема того, как она будет выглядеть.

class Statistics {

    private final static int N = 180;
    Queue<Integer> queue = new LinkedList<Integer>();
    SortedMap<Integer, Integer> counts = new TreeMap<Integer, Integer>();

    public int insertAndGetSmallerCount(int x) {

        queue.add(x);                                // O(1)
        counts.put(x, getCount(x) + 1);              // O(log N)

        int lessCount = 0;                           // O(N), unfortunately
        for (int i : counts.headMap(x).values())     // use Guavas TreeMultiset
            lessCount += i;                          // for O(log n)

        if (queue.size() > N) {                      // O(1)
            int oldest = queue.remove();             // O(1)
            int newCount = getCount(oldest) - 1;     // O(log N)
            if (newCount == 0)
                counts.remove(oldest);               // O(log N)
            else
                counts.put(oldest, newCount);        // O(log N)
        }

        return lessCount;
    }

    private int getCount(int x) {
        return counts.containsKey(x) ? counts.get(x) : 0;
    }

}

На моем ноутбуке с тактовой частотой 1,8 ГГц это решение выполняет около 1 000 000 итераций примерно на 13 секунд (например, одна итерация занимает около 0,013 мс, менее 100 мс).

Ответ 2

Вы можете сохранить массив из 180 чисел и сохранить индекс до самого старого, чтобы при входе нового номера вы перезаписывали номер в самом старом индексе и увеличивали индекс по модулю 180 (это немного сложнее, чем с тех пор вам нужно специальное поведение для первых 180 чисел).

Как для вычисления количества чисел меньше, я бы использовал метод грубой силы (итерировать все числа и количество).

Изменить: Мне смешно видеть, что "оптимизированная" версия работает в пять раз медленнее, чем эта тривиальная реализация (благодаря @Eiko для анализа). Я думаю, это связано с тем, что, когда вы используете деревья и карты, вы теряете локальность данных и имеете много ошибок памяти (не говоря уже о распределении памяти и сборе мусора).

Ответ 3

Добавьте свои номера в список. Если размеp > 180, удалите первый номер. Подсчет просто повторяется над 180 элементами, которые, вероятно, достаточно быстры. Трудно побить производительность.

Ответ 4

Вы можете использовать реализацию LinkedList.

С помощью этой структуры вы можете легко манипулировать первым и последним элементами списка.  (addFirst, removeFirst,...) Для алгоритма (найти количество чисел ниже/больше) достаточно простого цикла в списке и даст вам результат менее чем за 100 мс в списке 180 элементов.

Ответ 5

Вы можете попробовать создать структуру данных с привязанным списком, где каждая node поддерживает следующую/предыдущую, а также отсортированную следующую/предыдущую ссылку. Затем вставка становится двухфазным процессом, сначала всегда вставляйте node в хвост, а сортировку вставки, а сортировка вставки возвращает количество чисел меньше x. Удаление - просто удаление головы.

Вот пример, ЗАМЕЧАНИЕ: ЭТО ОЧЕНЬ НАСТОЯЩЕЕ ДЖАВ, ЭТО ПРИМЕР КОДА, ЧТОБЫ ПОЛУЧИТЬ ДЕМОНСТРАЦИЮ ИДЕИ. Вы поняли!;) Кроме того, я добавляю только несколько элементов, но это должно дать вам представление о том, как это будет работать... Худший случай для этого - полная итерация через отсортированный связанный список - что не хуже примеров выше, я думаю?

import java.util.*;

class SortedLinkedList {

  public static class SortedLL<T>
  {
    public class SortedNode<T>
    {
      public SortedNode(T value)
      {
        _value = value;
      }

      T _value;

      SortedNode<T> prev;
      SortedNode<T> next;

      SortedNode<T> sortedPrev;
      SortedNode<T> sortedNext;
    }

    public SortedLL(Comparator comp)
    {
      _comp = comp;
      _head = new SortedNode<T>(null);
      _tail = new SortedNode<T>(null);
      // Setup the pointers
      _head.next = _tail;
      _tail.prev = _head;
      _head.sortedNext = _tail;
      _tail.sortedPrev = _head;
      _sortedHead = _head;
      _sortedTail = _tail;      
    }

    int insert(T value)
    {
      SortedNode<T> nn = new SortedNode<T>(value);

      // always add node at end
      nn.prev = _tail.prev;
      nn.prev.next = nn;
      nn.next = _tail;
      _tail.prev = nn;

      // now second insert sort through..
      int count = 0;
      SortedNode<T> ptr = _sortedHead.sortedNext;
      while(ptr.sortedNext != null)
      {
        if (_comp.compare(ptr._value, nn._value) >= 0)
        {
          break;
        }
        ++count;
        ptr = ptr.sortedNext;
      }  

      // update the sorted pointers..
      nn.sortedNext = ptr;
      nn.sortedPrev = ptr.sortedPrev;
      if (nn.sortedPrev != null)
        nn.sortedPrev.sortedNext = nn;
      ptr.sortedPrev = nn;

      return count;            
    }

    void trim()
    {
      // Remove from the head...
      if (_head.next != _tail)
      {
        // trim.
        SortedNode<T> tmp = _head.next;
        _head.next = tmp.next;
        _head.next.prev = _head;

        // Now updated the sorted list
        if (tmp.sortedPrev != null)
        {
          tmp.sortedPrev.sortedNext = tmp.sortedNext;
        }
        if (tmp.sortedNext != null)
        {
          tmp.sortedNext.sortedPrev = tmp.sortedPrev;
        }
      }
    }

    void printList()
    {
      SortedNode<T> ptr = _head.next;
      while (ptr != _tail)
      {
        System.out.println("node: v: " + ptr._value);
        ptr = ptr.next;
      }      
    }

    void printSorted()
    {
      SortedNode<T> ptr = _sortedHead.sortedNext;
      while (ptr != _sortedTail)
      {
        System.out.println("sorted: v: " + ptr._value);
        ptr = ptr.sortedNext;
      }      
    }

    Comparator _comp;

    SortedNode<T> _head;
    SortedNode<T> _tail;    

    SortedNode<T> _sortedHead;
    SortedNode<T> _sortedTail;    

  }

  public static class IntComparator implements Comparator
  {
    public int compare(Object v1, Object v2){
      Integer iv1 = (Integer)v1;
      Integer iv2 = (Integer)v2;
      return iv1.compareTo(iv2);
    }
  }


  public static void main(String[] args){

    SortedLL<Integer> ll = new SortedLL<Integer>(new IntComparator());
    System.out.println("inserting: " + ll.insert(1));
    System.out.println("inserting: " + ll.insert(3));
    System.out.println("inserting: " + ll.insert(2));
    System.out.println("inserting: " + ll.insert(5));
    System.out.println("inserting: " + ll.insert(4));
    ll.printList();
    ll.printSorted();    

    System.out.println("inserting new value");
    System.out.println("inserting: " + ll.insert(3));
    ll.trim();
    ll.printList();
    ll.printSorted();    
  }
}

Ответ 6

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

Затем после каждой вставки просто сканируйте весь список и вычислите нужное число.

Ответ 7

Взгляните на commons-math реализацию класса DescriptiveStatistics (Percentile.java)

Ответ 8

180 значений не так много и простой массив, который ищет грубую силу и System.arraycopy() должен быть быстрее, чем 1 микросекунда (1/1000 миллисекунды), и не берет GC. Это может быть быстрее, чем игра с более сложными коллекциями.

Я предлагаю вам сделать это простым и измерить, сколько времени займет до того, как вы захотите его оптимизировать.