Java:来自流源的前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;
  }
}

有一个类似的问题,但它不包括流源/内存要求: 查找数组中的前N个元素

Answer 1

使用"堆"数据结构.Java有一个内置的:PriorityQueue.只需将比较器定义为"最佳",然后将流中的所有数据提供给优先级队列.

编辑:

要为此答案添加更多颜色,您可能需要执行以下操作:

• 定义一个与你想要的方式相反的比较器(即赞成你要丢弃的项目) - 或者定义一个以正确方式工作的比较器,并用它包装它 Collections.reverseOrder(...)
• 迭代您的数据并将每个元素放入pqueue中.
• 对于每个插入,如果pqueue的大小> n,则使用poll()从堆中删除"top"元素 - 由于您的比较器,它实际上将是"最差"的元素.

你剩下的是一个有n个元素的pqueue,其中"最不好".