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

Question

我正在逐行解析一个大文件,读取每行中的子串.我将从每个子字符串中获取一个整数值,每行约30个,并且需要从文件中返回最高的5个值.什么样的数据结构最有效地跟踪5个最大值？

Answer 1

这个问题通常用堆来解决,但是(可能是反直觉地)你使用最小堆(最小的元素是堆的"顶部").

算法基本上是这样的:

   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

完成后,您可以将堆中的元素从最小到最大弹出.

或者,具体地说:

  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;
  }

您可以有效地将新项目与堆栈顶部进行比较,并且您不需要始终严格按顺序保留所有元素,因此这比完全有序的集合更快TreeSet.

对于五个元素的非常短的列表,迭代数组可能更快.但是如果"热门命中"集合的大小增加,这种基于堆的方法将会胜出.