使用 Java 流的 MinMaxPriorityQueue

Question

我正在 Java 中寻找一种内存高效的方法来从一个巨大的集合中找到前 n 个元素。例如，我有一个词、一个 distance() 方法和 "all" 个词的集合。我实现了一个 class 对，它实现了 compareTo() 以便对按它们的值排序。

使用流，我天真的解决方案如下所示：

double distance(String word1, String word2){
  ...
}

Collection<String> words = ...;
String word = "...";

words.stream()
  .map(w -> new Pair<String, Double>(w, distance(word, w)))
  .sorted()
  .limit(n);

据我了解，这将处理每个元素并将其临时存储在单词中，以便在应用 limit() 之前对其进行排序。然而，存储 n 个元素的集合更节省内存，每当添加新元素时，它都会删除最小的元素（根据可比较对象的自然顺序），因此永远不会大于 n（或 n+1 ).

这正是 Guava MinMaxPriorityQueue 所做的。因此，我目前对上述问题的最佳解决方案是：

Queue<Pair<String, Double>> neighbours = MinMaxPriorityQueue.maximumSize(n).create();
words.stream()
  .forEach(w -> neighbours.add(new Pair<String, Double>(w, distance(word, w)));

在将队列转换为流或列表后，仍然需要对前 n 个元素进行排序，但这不是问题，因为 n 相对较小。

我的问题是：有没有办法使用流来做同样的事情？

Answer 1

基于堆的结构当然比对整个巨大的列表进行排序更有效率。幸运的是，流库非常乐意让您在必要时使用专门的集合：

MinMaxPriorityQueue<Pair<String, Double>> topN = words.stream()
    .map(w -> new Pair<String, Double>(w, distance(word, w)))
    .collect(toCollection(
            () -> MinMaxPriorityQueue.maximumSize(n).create()
    ));

这比 .forEach 解决方案更好，因为它易于并行化并且更惯用 java8。

请注意，() -> MinMaxPriorityQueue.maximumSize(n).create() 应该可以替换为 MinMaxPriorityQueue.maximumSize(n)::create，但由于某些原因，在某些情况下无法编译（请参阅下面的评论）。

使用 Java 流的 MinMaxPriorityQueue

MinMaxPriorityQueue using Java streams

java

sorting

guava

java-8

java-stream