使用Java流的MinMaxPriorityQueue

Question

我正在寻找一种内存有效的Java方法来从庞大的集合中找到前n个元素.例如,我有一个单词,distance()方法和"all"单词的集合.我已经实现了一个实现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

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

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但是，由于某种原因，在某些条件下不会编译（请参阅下面的评论）。