动态计算百分位数

出于实际原因和合理的价值 n 你最擅长的是 环形缓冲区 原始的 int s(跟踪最早的条目)和a 线性扫描 用于确定有多少值小于 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.8GHz笔记本电脑上,这个解决方案在大约13秒的时间内执行1000000次迭代(即一次迭代大约需要0.013 ms,远低于100 ms)。

您可以保留一个180个数字的数组,并将索引保存到最旧的一个,这样当新的数字出现时,您可以在 最老的 索引并增加索引模块180(比这要复杂一些,因为您需要对前180个数字进行特殊的操作)。

至于计算有多少个数字较小,我将使用蛮力的方法(迭代所有的数字和计数)。

编辑: 我觉得很有趣看到 "optimized" version 运行速度比这个简单的实现慢五倍(由于 @Eiko 用于分析)。我认为这是因为当您使用树和映射时,您会丢失数据位置,并有更多的内存错误(更不用说内存分配和垃圾收集)。

把你的号码加到一张单子上。如果尺寸大于180,请删除第一个数字。 计数只是迭代180个元素,这可能足够快。很难从性能上击败对手。

您可以使用LinkedList实现。

使用此结构,您可以轻松地操作列表的第一个和最后一个元素。 (addfirst,removefirst,…) 对于算法(找出有多少个数字是低/大的),列表上的一个简单循环就足够了,并且会在180的元素列表中给出少于100毫秒的结果。

您可以尝试自定义链接列表数据结构,其中每个节点维护下一个/上一个引用以及排序后的下一个/上一个引用。然后插入变成了一个两阶段的过程,首先总是在尾部插入节点,然后插入排序,插入排序将返回小于x的数字计数。删除只是移除头部。

下面是一个例子,注:这是 非常讨厌 Java,它是纯粹的演示代码的示例代码。你明白了!另外,我只添加了一些项目,但它应该让您了解它的工作原理……最糟糕的情况是通过排序链接列表进行完整的迭代——我想这不会比上面的例子更糟吧?

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

让缓存成为一个列表,这样您就可以在开始时插入,并让最旧的缓存在结束时删除。

然后在每次插入之后,只需扫描整个列表并计算所需的数字。

看看 commons-math 执行 DescriptiveStatistics class ( Percentile.java )

180个值不多,是一个简单的数组,暴力搜索和system.arraycopy()的速度应该超过1微秒(1/1000毫秒),并且不会引发GC。使用更复杂的收藏可能会更快。

我建议你保持简单,并在假设你需要优化它之前测量时间。