java - 跟踪在 Java 中解析流时找到的最多 5 个值的最佳方法

Question

我正在逐行解析一个大文件，读取每行中的子字符串。我将从每个子字符串中获取一个整数值，每行约 30 个，并且需要从文件中返回最高的 5 个值。哪种数据结构最有效地跟踪遍历过程中的 5 个最大值？

Answer 1

这个问题通常用 heap, 解决。但是(也许违反直觉)你使用了一个最小堆(最小的元素是堆的“顶部”)。

算法基本上是这样的:

   for each item parsed
      if the heap contains less than n items, 
         add the new item to the heap
      else
         if the new item is "greater" than the "smallest" item in the heap
            remove the smallest item and replace it with the new item

When you are done, you can pop the elements off the heap from least to greatest.

Or, concretely:

  static <T extends Comparable<T>> List<T> top(Iterable<? extends T> items, int k) {
    if (k < 0) throw new IllegalArgumentException();
    if (k == 0) return Collections.emptyList();
    PriorityQueue<T> top = new PriorityQueue<>(k);
    for (T item : items) {
      if (top.size() < k) top.add(item);
      else if (item.compareTo(top.peek()) > 0) {
        top.remove();
        top.add(item);
      }
    }
    List<T> hits = new ArrayList<>(top.size());
    while (!top.isEmpty())
      hits.add(top.remove());
    Collections.reverse(hits);
    return hits;
  }

您可以将新项目与 top of the heap efficiently, 进行比较并且您不需要始终保持所有元素严格排序，因此这比完全有序的集合(如 TreeSet)更快。

对于包含五个元素的非常短的列表，遍历数组可能会更快。但是，如果“top hits”集合的大小增长，这种基于堆的方法将会胜出。