Java:N个最高元素的集合

Question

我需要在大量数据中找到N个最大元素.

我有:

• 外部数据库(Cassandra)中数亿项的集合

• 迭代这些项并找到具有最大值的项的作业

  Item largest = null;
  
  // Page through big data
  List<Item> items = getNextPage(pageSize);
  while (items.size() > 0) {
  
    // Update largest item based on values from current page
    for (Item current : items) {
      if (largest == null || largest.getValue() < current.getValue()) {
        largest = current;
      }
    }
  
    // Move to next page
    items = getNextPage(pageSize);
  }
  

我需要:

• 扩展此作业以保持具有最高值的N(简称100)元素

我的方法:

• 我正在考虑像固定大小的优先级队列

  class PQsort implements Comparator<Item> {
  
    public int compare(Item one, Item two) {
      return two.getValue() - one.getValue();
    }
  }
  
  PriorityQueue<Item> pq = new PriorityQueue<Item>(101, new PQsort());
  
  ...while...for...
  
  pq.offer(current);
  if (pq.size() == 101) {
    // Remove the tail somehow 
  }
  ...
  

• 删除尾部:删除优先级队列的尾部元素

这项任务的最佳解决方案是什么？

Answer 1

对此有几点想法.

此任务非常适合使用多个处理器.您可以在线程池中拆分页面,然后在完成时合并结果.

插入每个值是不必要的,允许集合排序然后删除最小值.更快的方法是检查每个项目是否大于集合中最小的(即最后一个)项目.

这是一个简单的例子,可以找到10,000个随机整数数组中的100个最大整数.

    Queue<Integer> largest = new PriorityQueue<>(100);

    for (int item : new Random().ints(10000, 0, 100).toArray()) {
        if (largest.size() < 100 || largest.peek() < item) {
            if (largest.size() == 100)
                largest.remove();
            largest.add(item);
        }
    }
    System.out.println(largest);