2

假设您从“流”源读取数据项和相关分数（即不可能进行随机访问或多次传递）。

什么是在任何时候只保留内存中迄今为止遇到的权重最低的那些元素的最佳方法。我会对“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

4

2 回答 2

6

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

编辑：

要为这个答案添加更多颜色，您可能需要执行以下操作：

  • 定义一个与你想要的东西相反的比较器（即有利于你想扔掉的物品） - 或者定义一个以正确方式工作的比较器，然后用Collections.reverseOrder(...)
  • 遍历您的数据并将每个元素放入 pqueue。
  • 每次插入时，如果 pqueue 的大小 >n，则使用poll()从堆中删除“顶部”元素 - 由于您的比较器，这实际上将是“最差”的元素。

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

于 2012-03-06T10:01:23.930 回答
1

你可以通过 guava 的Comparators类来获得想要的结果。请参阅下面的示例，该示例获得前 5 个数字。Api 可以在这里找到。

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]

于 2017-06-28T08:12:42.213 回答