logo标签列表

实时计算百分位数

javaalgorithmstatistics
11

我正在使用Java编程。每100毫秒，我的程序会得到一个新数字。

它有一个缓存，包含过去n = 180个数字的历史记录。 当我得到一个新数字x时，我想计算在缓存中有多少个数字小于x。 然后，我想删除缓存中最旧的数字。

每100毫秒，我希望重复计算有多少较小的数字并删除最旧的数字。

哪种算法应该使用？我想优化计算速度，因为这不是那100毫秒内唯一要计算的事情。

8个回答
10

出于实际考虑和合理的 n 值，您最好使用原始的 int 类型的 环形缓冲区 （以跟踪最旧条目）和 线性扫描（以确定小于 x 的值的数量）。

为了使其达到 O(log n)，您需要使用类似于 Guava 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 GHz笔记本电脑上，这个解决方案大约需要13秒完成100万次迭代（即每次迭代约需要0.013毫秒，远远低于100毫秒）。

@CodeInChaos，我认为使用列表不会使其更易读。此外，谁说180是铸成石头的？;) - aioobe
3
我对180个案例进行了性能测试-插入了100万个条目：队列+树1380毫秒，仅队列1300毫秒，普通int[]环形缓冲区210毫秒。 - Eiko
@Eiko，现在用越来越大的值对n进行重复测试 :-) - aioobe
1
除了性能问题，TreeSet 还会遇到重复数字的问题。(虽然你可以使用 STL 的 multiset，但会牺牲更多性能。不确定 multiset 是否提供排序功能) - Nikita Rybak
我认为sorted.headSet.size的时间复杂度是O(N)而不是O(log N)。返回元素的数量是随机的，因此平均为N/2。计算N/2个元素的时间复杂度是O(N)。 - mb14
显示剩余8条评论
6
你可以保留一个包含180个数字的数组，并保存最老数字的索引，当有新的数字进来时，你会覆盖在最老索引处的数字，并将该索引加1取模180（需要特殊处理前180个数字）。
至于计算比某个数字小的数字数量，我会使用暴力方法（遍历所有数字并计数）。
编辑：我觉得很有趣的是，"优化"版本的运行速度比这个简单的实现慢了五倍（感谢@Eiko进行分析）。我认为这是因为当你使用树和映射时，会失去数据局部性并且会有更多的内存故障（更不用说内存分配和垃圾回收了）。
1
  1. 环形缓冲区比ArrayList和LinkedList更好。而且通过完整迭代获取百分位数似乎也不错。
 - Thilo
但是他的缓存应该只保存180个（+1）数字。 - Eiko
@Eiko，我不明白你的意思。缓存中保存了180个元素，就像问题描述的那样，而+1是参数。 - Motti
啊，抱歉...我没注意到环形缓冲区。我以为你想要保留每个元素的年龄。 - Eiko
一个理论上更好的算法在小数据集上表现得更慢并不令人惊讶。 - Aryabhatta
显示剩余4条评论
3

将您的数字添加到列表中。如果大小>180，则删除第一个数字。 计数只是迭代180个元素，这可能足够快。从性能上来说很难超越。

很好，也很简单 :) 对于这样小的数组，O(n)并不重要。 - CodesInChaos
1

您可以尝试使用自定义的链表数据结构，其中每个节点都维护next/prev以及排序后的next/prev引用。然后插入变成了一个两阶段的过程，首先总是将节点插入到尾部，然后进行插入排序，插入排序将返回小于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();    
  }
}
1

你可以使用LinkedList实现。

有了这个结构，你可以轻松地操作List的第一个和最后一个元素。 （addFirst，removeFirst，...） 对于算法（查找比某个数小/大的数字数量），只需在列表上简单循环即可，在180个元素的列表上可以在不到100毫秒内得出结果。

0
让缓存成为一个列表，这样你就可以在开头插入数据，并保持最老的在末尾并且被移除。
然后每次插入后，只需扫描整个列表并计算所需要的数量。
0
就我所见，这个类没有一个函数来忘记最旧的值。 - Christian
在DescriptiveStatistics类中，您可以设置“窗口大小”。addValue()方法的Javadoc：将值添加到数据集中。如果数据集已达到最大大小（即，存储的元素数量等于当前配置的windowSize），则数据集中的第一个（最旧的）元素将被丢弃以为新值腾出空间。 http://commons.apache.org/math/apidocs/src-html/org/apache/commons/math/stat/descriptive/DescriptiveStatistics.html#line.150 - axelclk
0

180个值不算多，一个简单的数组，采用暴力搜索和System.arraycopy()应该比1微秒(1/1000毫秒)更快，并且不会产生垃圾回收。这可能比使用更复杂的集合更快。

我建议你保持简单，先测量一下所需时间，再考虑是否需要优化。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接