Java - 寻找比PriorityQueue更快的东西

Question

我在大量数据上使用java.

[我试图尽可能地简化问题]

实际上我有一个小类(元素)包含一个int KEY和一个双重WEIGHT(带有getter和setter).

我从文件中读取了很多这些对象,我必须得到最好的(最重量级)M对象.

实际上我正在使用一个PriorityQueue和一个Comparator来比较两个Element,它可以工作,但它太慢了.

你知道(我知道你这样做)更快的方法吗？

谢谢

Answer 1

基于堆的优先级队列是解决此问题的良好数据结构.正如完整性检查一样,验证您是否正确使用了队列.

如果您想要最高权重的项目,请使用min -queue,其中堆的顶部是最小的项目.将每个项目添加到最大队列并M在完成后检查顶部项目效率不高.

对于每个项目,如果M队列中的项目少于,则添加当前项目.否则,偷看堆顶部.如果它小于当前项目,则丢弃它,然后添加当前项目.否则,丢弃当前项目.处理完所有项目后,队列将包含M权重最高的项目.

有些堆具有用于替换堆顶部的快捷API,但Java Queue没有.即便如此,大O的复杂性也是一样的.

Answer 2

除了建议的"查看堆顶部"算法,它为您提供了获得n个项目的前m个的O(n log m)复杂度,这里还有两个解决方案.

解决方案1:使用Fibonacci堆.

JDK的PriorityQueue实现是一个平衡的二进制堆.您应该能够从Fibonacci堆实现中挤出更多性能.它将具有分摊的常量时间插入,而插入二进制堆的堆的大小具有复杂度Ω(log n).如果你为每个元素做这个,那么你就是Ω(n log n).使用Fib堆查找n个项目的前m个具有复杂度O(n + m log n).将此与仅将m个元素插入堆中的建议相结合,并且您具有O(n + m log m),这与您将要获得的线性时间接近.

解决方案2:遍历列表M次.

您应该能够在O(n)时间内获取集合中的第k个最大元素.只需将所有内容都读入列表并执行以下操作:

kthLargest(k, xs)
  Pick a random pivot element p from the list
    (the first one will do if your list is already random).
  Go over the set once and group it into two lists.
     Left: smaller than p. 
     Right: Larger or equal to p.
  If the Right list is shorter than k, return kthLargest(k - right.size, Left)
  If the Right list is longer than k, return kthLargest(k, right)
  Otherwise, return p.

这给你O(n)时间.运行m次,您应该能够在时间O(nm)中获得集合中的top-m对象,对于足够大的n和足够小的m,它将严格小于n log n.例如,在使用二进制堆优先级队列时,获得超过一百万个项目的前10个将花费一半,所有其他条件相同.