Java:来自流源的top-n元素

Question

假设您从“流”源读取数据项和相关分数(即，不可能随机访问或多次通过)。

在任何时候，最好的方法是只保留到目前为止在内存中遇到的权重最低的元素。我感兴趣的是"Java“的方式，习惯用法越短越好，而不是算法(”使用搜索树，插入新元素，如果超过大小则删除最大值“)。

下面是我想出的解决方案，但是我发现它有点冗长，而且有些行为可能是意想不到的(相同的项目有不同的分数可能会被保留多次，而相同的项目加上相同的分数只会保留一次)。我也觉得这应该有一些存在的东西。

import java.util.AbstractMap.SimpleEntry;
import java.util.Map.Entry;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * Stores the n smallest (by score) elements only.
 */
public class TopN<T extends Comparable<T>> {
  private TreeSet<Entry<T, Double>> elements;
  private int n;

  public TopN(int n) {
    this.n = n;
    this.elements = new TreeSet<Entry<T, Double>>(
        new Comparator<Entry<T, Double>>() {
          @Override
          public int compare(Entry<T, Double> o1, Entry<T, Double> o2) {
            if (o1.getValue() > o2.getValue()) return 1;
            if (o1.getValue() < o2.getValue()) return -1;
            return o1.getKey() == null ? 1 : o1.getKey().compareTo(o2.getKey());
          }
    });
  }

  /**
   * Adds the element if the score is lower than the n-th smallest score.
   */
  public void add(T element, double score) {
    Entry<T, Double> keyVal = new SimpleEntry<T, Double>(element,score);
    elements.add(keyVal);
    if (elements.size() > n) {
      elements.pollLast();
    }
  }

  /**
   * Returns the elements with n smallest scores.
   */
  public TreeSet<Entry<T, Double>> get() {
    return elements;
  }
}

还有一个类似的问题，但它不包括流源/内存需求：Find top N elements in an Array

Answer 1

使用“堆”数据结构。Java有一个内置的：PriorityQueue。只需将比较器定义为“最佳”，并将流中的所有数据输入到优先级队列中。

编辑：

为了给这个答案增加一点色彩，你可能需要这样做：

• 定义一个与你想要的相反的比较器(即偏爱你想要丢弃的项)-或者定义一个正确的比较器，然后用Collections.reverseOrder(...)
• Iterate将它包裹在你的数据上，并将每个元素放入pqueue。
• 每次插入，如果pqueue的大小大于n，使用poll()从堆中删除“
• ”元素-因为你的比较器，它实际上是“最差的”元素。

剩下的是一个包含n个元素的pqueue，其中的元素是“最好的”。

Answer 2

您可以使用guava的Comparators类来获得所需的结果。请看下面的示例，它获得了前5个数字。接口可以在here上找到。

import java.util.Comparator;
import java.util.List;
import java.util.stream.Collector;

import org.junit.Test;

import com.google.common.collect.Comparators;
import com.google.common.collect.Lists;

public class TestComparator {

    @Test
    public void testTopN() {
        final List<Integer> numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0);
        final Collector<Integer, ?, List<Integer>> collector = Comparators.greatest(5,
                Comparator.<Integer>naturalOrder());
        final List<Integer> top = numbers.stream().collect(collector);
        System.out.println(top);
    }

}

输出: 9、8、7、6、5