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(... )
• 遍历您的数据并将每个元素放入 pqueue。
• 每次插入时，如果 pqueue 的大小 >n，使用 poll() 从堆中移除“顶部”元素 - 由于您的比较器，它实际上将是“最差”一个。

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