Calculating Percentiles on the fly

Question

I'm programming in Java. Every 100 ms my program gets a new number.

It has a cache with contains the history of the last n = 180 numbers. When I get a new number x I want to calculate how many numbers there are in the cache which are smaller than x. Afterwards I want to delete the oldest number in the cache.

Every 100 ms I want to repeat the process of calculating how many smaller numbers there are and delete the oldest number.

Which algorithm should I use? I would like to optimize for making the calculation fast as it's not the only thing that calculated on those 100 ms.

Answer 1

Add your numbers to a list. If size > 180, remove the first number. Counting is just iterating over the 180 elements which is probably fast enough. It's hard to beat performance wise.

Answer 2

Let the cache be a list, so you can insert at the start and let the oldest be at the end and be removed.

Then after every insertion just scan the whole list and calculate the number you need.

Answer 3

You can use a LinkedList implementation.

With this structure, you can easily manipulate the first and the last elements of the List. (addFirst, removeFirst, ...) For the algorithm (find how many numbers are lower/greater), a simple loop on the list is enough, and will give you the result in less than 100ms on a 180's element list.

Answer 4

You can keep an array of 180 numbers and save an index to the oldest one so that when a new number comes in you overwrite the number at the oldest index and increment the index modulo 180 (it's a bit more complex than that since you need special behaviour for the first 180 numbers).

As for calculating how many numbers are smaller I would use the brute force way (iterate all the numbers and count).

---

Edit: I find it funny to see that the "optimized" version runs five times slower than this trivial implementation (thanks to @Eiko for the analysis). I think this is due to the fact that when you use trees and maps you lose data locality and have many more memory faults (not to mention memory allocation and garbage collection).

Answer 5

For practical reasons and reasonable values of n you're best of with a ring-buffer of primitive ints (to keep track of oldest entry), and a linear scan for determining how many values are smaller than x.

In order for this to be in O(log n) you would have to use something like Guavas TreeMultiset. Here is an outline of how it would look.

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

}

On my 1.8 GHz laptop, this solution performs 1,000,000 iterations on about 13 seconds (i.e. one iteration takes about 0.013 ms, well under 100 ms).

Answer 6

You could try a custom linked list data structure where each node maintains next/prev as well as sorted next/prev references. Then inserting becomes a two phase process, first always insert node at tail, and the insert sort, and the insert sort will return the count of numbers less than x. Deleting is simply removing the head.

Here is an example, NOTE: THIS IS VERY NASTY JAVA, IT IS EXAMPLE CODE TO PURELY DEMONSTRATE THE IDEA. You get the idea! ;) Also, I'm only adding a few items, but it should give you an idea of how it would work... The worst case for this is a full iteration through the sorted linked list - which is no worse than the examples above I guess?

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();    
  }
}

Answer 7

Take a look at the commons-math implementation of the DescriptiveStatistics class (Percentile.java)

Answer 8

180 values is not many and a simple array which a brute force search and System.arraycopy() should be faster than 1 micro-second (1/1000 milli-second) and incurs no GC. It could be faster that playing with more complex collections.

I suggest you keep it simple and measure how long ti takes before assuming you need to optimise it.