7

我在大量数据上使用java。

[我尽量简化问题]

实际上我有一个小类（元素），包含一个 int KEY 和一个双 WEIGHT（带有 getter 和 setter）。

我从一个文件中读取了很多这些对象，我必须得到最好的（最重的）M 个对象。

实际上，我正在使用带有 Comparator 的 PriorityQueue 来比较两个元素，它可以工作，但是太慢了。

你知道（我知道你知道）有什么更快的方法吗？

谢谢

4

4 回答 4

7

基于堆的优先级队列是解决这个问题的一个很好的数据结构。就像完整性检查一样，验证您是否正确使用了队列。

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

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

一些堆具有用于替换堆顶部的快捷 API，但 JavaQueue没有。即便如此，big-O 复杂度是相同的。

于 2009-08-31T19:55:21.110 回答
6

除了建议的“peek at the top of the heap”算法（它为您提供 O(n log m) 复杂度以获得 n 个项目的 top-m ）之外，这里还有两个解决方案。

解决方案 1：使用斐波那契堆。

JDK 的 PriorityQueue 实现是一个平衡的二叉堆。您应该能够从斐波那契堆实现中挤出更多性能。它将具有摊销的常数时间插入，而插入二进制堆的复杂度为 Ω(log n) 的堆大小。如果你对每个元素都这样做，那么你就在 Ω(n log n)。使用 Fib 堆查找 n 个项目中的 top-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) 时间内获得集合中的前 m 个对象，对于足够大的 n 和足够小的 m，这将严格小于 n log n。例如，在所有其他条件相同的情况下，获得超过一百万个项目的前 10 名将花费使用二进制堆优先级队列的一半时间。

于 2009-09-01T06:20:24.020 回答
2

如果 M 适当小，那么对所有元素进行排序可能会浪费大量计算时间。您只能将前 M 个对象放入优先级队列（例如堆，顶部的最小元素），然后遍历其余元素：每次元素大于堆顶部时，删除顶部并推送新元素元素进入堆。

或者，您可以遍历整个数组一次以找到一个统计阈值，您可以非常确定有超过 M 个具有较大值的对象（将需要对这些值进行一些假设，例如，如果它们是正态分布的）。然后，您可以将排序限制为具有较大值的所有元素。

于 2009-08-31T19:53:58.100 回答
0

@Tnay：您有一点关于不进行比较的观点。不幸的是，您的示例代码仍然执行一个。这解决了问题：

public int compare(ListElement i, ListElement j) {
    return i.getValue() - j.getValue();
}

此外，您的方法和 BigGs 的比较方法都不是严格正确的，因为它们从不返回 0。这可能是某些排序算法的问题，这是一个非常棘手的错误，因为它只会在您切换到另一个实现时出现。

来自Java 文档：

实现者必须确保所有 x 和 y 的 sgn(compare(x, y)) == -sgn(compare(y, x))。

这可能会或可能不会执行显着的常数因子加速。如果将此与埃里克森的解决方案结合起来，可能很难更快地做到这一点（取决于 M 的大小）。如果 M 很大，最有效的解决方案可能是使用 Java 内置的 qsort 对数组进行排序，最后将数组的一端截掉。

于 2009-08-31T20:12:41.637 回答