即时计算百分位数

Question

我用Java编程.每100毫秒,我的程序获得一个新号码.

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

每100毫秒,我想重复计算有多少个较小数字的过程,并删除最旧的数字.

我应该使用哪种算法？我想优化计算速度,因为它不是唯一计算在100毫秒上的东西.

Answer 1

出于实际原因和合理的值,n您最好使用原始s 的环形缓冲区int(以跟踪最旧的条目),并使用线性扫描来确定有多少值小于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 GHz笔记本电脑上,该解决方案在大约13秒内执行1,000,000次迭代(即一次迭代大约需要0.013 ms,远低于100 ms).

Answer 2

您可以保留一个包含180个数字的数组,并将索引保​​存到最旧的数字,这样当一个新数字出现时,您将覆盖最旧索引处的数字并将索引模数增加180(由于您需要特殊的数据,它会比这更复杂一些前180个数字的行为).

至于计算多少个数字较小,我会使用强力方式(迭代所有数字和计数).

编辑:我觉得很有趣的是,"优化"版本比这个简单的实现慢了五倍(感谢@Eiko的分析).我认为这是因为当你使用树和地图时,你会丢失数据局部性并且有更多的内存错误(更不用说内存分配和垃圾收集)了.