提取列表中给定数量的最高值

Question

我正在寻求根据各自的权重（由 Integer 表示）在网页上显示固定数量的项目。找到这些项目的列表实际上可以是任何大小。

我想到的第一个解决方案是执行 Collections.sort() 并通过遍历 List 逐项获取项目。有没有更优雅的解决方案可以用来准备前八项？

Answer 1

只需使用 Collections.sort(..) 即可。它足够高效。

该算法提供有保证的 n log(n) 性能。

如果您知道列表的一些独特属性，您可以尝试为您的具体情况实现更有效的东西，但这是不合理的。此外，例如，如果您的列表来自数据库，您可以对其进行LIMIT在那里订购而不是在代码中订购。

Answer 2

您的选择：

1. 进行线性搜索，保留沿途找到的前N个权重。 如果由于某种原因，您无法在显示页面之间重复使用排序结果（例如列表变化很快），这应该比对冗长的列表进行排序更快。

   更新：我纠正了线性搜索必然比排序更好的观点。请参阅维基百科文章“Selection_algorithm - 选择 k 个最小或最大元素”以获得更好的选择算法。

2. 手动维护一个按权重顺序排序的列表（原始列表或并行列表）。您可以使用诸如 Collections.binarySearch() 来确定在何处插入每个新项目。

3. 通过调用 Collections.sort() 每次修改、批量修改或就在显​​示之前（可能维护修改标志以避免对已排序的列表进行排序）。

4. 使用为您维护排序权重顺序的数据结构：优先级队列，树set 等。您还可以创建自己的数据结构。

5. 手动维护前 N 个项目的第二个（可能是按权重排序的）数据结构。每当原始数据结构被修改时，该数据结构就会被更新。您可以创建自己的数据结构，将原始列表和“前 N 个缓存”包装在一起。

Answer 3

您可以使用最大堆。

如果您的数据源自数据库，请在该列上放置索引，并使用 ORDER BY 和 TOP 或 LIMIT 仅获取需要显示的记录。

Answer 4

或者优先级队列。

Answer 5

使用dollar：

List<Integer> topTen = $(list).sort().slice(10).toList();

不使用dollar，你应该sort()它使用Collections.sort()，然后使用list.sublist(0, n)获取前n个项目。

Answer 6

既然你说从中提取前 N 个项目的列表可能是任意大小，所以我认为可能很大，所以我会补充上面简单的 sort() 答案（这完全是适合合理大小的输入），建议这里的大部分工作是找到前 N 个——然后对这些 N 进行排序就很简单了。也就是说：

Queue<Integer> topN = new PriorityQueue<Integer>(n);
for (Integer item : input) {
  if (topN.size() < n) {
    topN.add(item);        
  } else if (item > topN.peek()) {
    topN.add(item);          
    topN.poll();
  }
}

List<Integer> result = new ArrayList<Integer>(n);
result.addAll(topN);
Collections.sort(result, Collections.reverseOrder());

这里的堆（最小堆）的大小至少是有限的。没有必要将所有物品堆成一堆。

Answer 7

不，不是真的。至少不使用Java的内置方法。

有一些巧妙的方法可以比 O(n*log(n)) 操作更快地从列表中获取最高（或最低）N 个项目，但这需要您通过以下方式编写此解决方案：手。如果项目数量保持相对较低（不超过几百），则使用 Collections.sort() 对它进行排序，然后获取前 N 个数字是我认为的最佳方法。

Answer 8

取决于有多少。让我们将 n 定义为按键总数，将 m 定义为您希望显示的数字。
对整个事物进行排序：O(nlogn)
每次扫描数组寻找下一个最大数字：O(n*m)
所以问题是 - n 和 m 之间的关系是什么？
如果m < log n，扫描效率会更高。
否则，m >= log n，这意味着排序会更好。 （因为对于 m = log n 的边缘情况，这实际上并不重要，但排序也会给你带来好处，嗯，对数组进行排序，这总是很好的。

Answer 9

如果列表的大小为N，要检索的项目数为K，则需要对列表调用Heapify，它将列表（必须可索引，例如数组）转换为优先级队列。 （参见 http://en.wikipedia.org/wiki/Heapsort 中的 heapify 函数

）堆顶部的项目（最大项目）需要 O (lg N) 时间。所以你的总时间将是：

O(N + k lg N) ，

这比 O (N lg N) 更好，假设 k 比 N 小得多。

Answer 10

如果无法保留排序数组或使用不同的数据结构，您可以尝试如下操作。 O 时间类似于对大数组进行排序，但实际上这应该更有效。

small_array = big_array.slice( number_of_items_to_find );
small_array.sort();
least_found_value = small_array.get(0).value;

for ( item in big_array ) {  // needs to skip first few items
  if ( item.value > least_found_value ) {
    small_array.remove(0);
    small_array.insert_sorted(item);
    least_found_value = small_array.get(0).value;
  }
}

small_array 可以是一个 Object[]，内部循环可以通过交换来完成，而不是实际删除和插入到数组中。