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

Question

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

- Badger

---

一个长度为5的int数组。 - Elliott Frisch

如果前五个数字中有重复的，应该怎么处理？ - 4castle

如果位置5上有重复的值，那么可以毫不犹豫地将其丢弃。 - Badger

如果最高的数字有重复怎么办？我基本上是在问一个 Set 是否适用于此。 - 4castle

哦，那样的话，Set就不适用了，因为我想要分别存储两个值。 - Badger

Answer 1

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

算法基本上是这样的：

   对于每个解析的项
      如果堆中包含少于n个项，
         将新项添加到堆中
      否则
         如果新项“大于”堆中的“最小”项，
            删除最小项并用新项替换它

完成后，您可以从小到大从堆中弹出元素。

或者，具体地说：

  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）更快。

对于非常短的五个元素的列表，遍历数组可能更快。但如果“热门搜索结果”集合的大小增长，这种基于堆的方法将获胜。

- erickson

Answer 2

我会使用一个TreeSet（基本上是一个排序集合），每次添加到集合中时删除first（最低）元素。 这将丢弃重复项。

SortedSet<Integer> set = new TreeSet<>();
for (...) {
    ...
    if (set.size() < 5) {
        set.add(num);
    } else if (num > set.first()) {
        set.remove(set.first());
        set.add(num);
    }
}

- 4castle

---

set.last()将返回最高的数字。您确定要删除它吗？ - dnault

@dnault 谢谢，我应该仔细看看。 - 4castle

@oopexpert，你能解释一下吗？我不明白那是怎么回事。 - 4castle

@oopexpert 不用担心，我找到了一篇文章。有趣的是，在这种情况下我们是安全的，因为Integer#compareTo“符合等式”。文章链接：http://www.codelord.net/2010/11/24/liskov-substitution-principle-violation-spotted-in-the-wild/。 - 4castle

禁止使用SortedSet实现是极端的。它们非常有用，而且很容易通过遵循简单、易懂、广泛记录和直觉的实践方法——使equals()与compareTo()保持一致来减轻它们的缺点。 - erickson

Answer 3

你可以使用带有排序顺序的LinkedList进行插入。每个新的整数，您需要检查结尾以确保它在最大值内。如果是，则按降序迭代，如果新的整数>节点的整数，则在那里插入新的整数，然后删除最后一个元素以保持长度为5。

数组也可以使用，但您需要进行洗牌。

- waltron

Answer 4

Guava库有一个Ordering.greatestOf方法，可以在O(N)时间和O(K)空间内从Iterable中返回最大的K个元素。

实现在一个包私有的TopKSelector类中。

- Daniel Pryden

---

我猜他们不想把所有数字一次性加载到单个“可迭代对象”中。 - 4castle

“Iterable” 不需要一次性将所有元素加载到内存中，所以我认为这没有问题。 - dnault