java - 使用 Java 流的 MinMaxPriorityQueue

Question

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

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

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 但是，出于某种原因，在某些条件下无法编译(请参阅下面的评论)。