3

我需要在大量数据中找到 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 
    }
    ...
    
  • 去除尾部:去除优先队列的尾部元素

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

4

5 回答 5

7

对此有几点想法。

此任务非常适合使用多个处理器。您可以将页面拆分到一个线程池中,然后在它们完成时组合结果。

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

这是一个简单的示例,在 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);
于 2017-03-14T13:22:31.737 回答
3

我会坚持使用 PriorityQueue 并在它大于必要时删除项目。

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(1, 10, 2, 9, 3, 7, 4, 6, 5, 7, 7, 7);

    findNHighest(list, 3);
    findNHighest(list, 1);
    findNHighest(list, 4);

}

private static void findNHighest(List<Integer> list, int n) {
    Queue<Integer> nthHighest = new PriorityQueue<>();

    for (Integer each : list) {
        nthHighest.add(each);
        if (nthHighest.size() > n) {
            nthHighest.poll();
        }
    }
    System.out.println(nthHighest);
}

输出

[7, 9, 10]
[10]
[7, 7, 9, 10]
于 2017-03-14T13:30:26.613 回答
1

可以使用 SortedSet 实现来完成这项工作

class PQsort implements Comparator<Item> {

  public int compare(Item one, Item two) {
    return two.getValue() - one.getValue();
  }
}

...

Comparator<Item> itemComparator = new PQSort();
SortedSet<Item> top100 = new TreeSet<Item>(100, itemComparator);
Item smallestOfTheTop100 = null;

// Page through big data
List<Item> items = getNextPage(pageSize);
while (items.size() > 0) {

  for (Item current : items) {
    if (smallestOfTheLargest == null || itemComparator.compare(smallestOfTheTop100, current) > 0) {
         top100.add(item); // the current item is larger than the end of our top 100 list, so add it to the set.
         top100.remove(top100.first()); // remove the 101th element of the set - it is now extra. 
         smallestOfTheTop100 = top100.first(); 
    }
  }

  // Move to next page
  items = getNextPage(pageSize);
}

正如 sprinter 在他的回答中所说,它也可以在并行实现中重新设计 - 例如使用 Streams。

于 2017-03-14T13:29:09.430 回答
1

要构建优先级队列,它需要MlogM,其中 M 是项目总数,然后弹出 N 个项目将需要额外的 NlogM。这比使用MlogM对数组进行排序然后选择 N 中的最后 N 个项目贵一些。

如果 N 很小,只需将数组迭代 N 次,每次取下一个最佳最大值。

Standard solution would be Quick Select with average linear time, here is the implementation by Profesor Robert Sedgewick. If you need 100 largest items, select largest 100th element, all the elements to the right of the item will be greater. The profesor has a nice video lecture on the topic.

Relevant part:

/***************************************************************************
*  Rearranges the elements in a so that a[k] is the kth smallest element,
*  and a[0] through a[k-1] are less than or equal to a[k], and
*  a[k+1] through a[n-1] are greater than or equal to a[k].
***************************************************************************/
public static <Key extends Comparable<Key>> Key select(Key[] a, int k) {
    if (k < 0 || k >= a.length) {
        throw new IndexOutOfBoundsException("Selected element out of bounds");
    }
    StdRandom.shuffle(a);
    int lo = 0, hi = a.length - 1;
    while (hi > lo) {
        int i = partition(a, lo, hi);
        if      (i > k) hi = i - 1;
        else if (i < k) lo = i + 1;
        else return a[i];
    }
    return a[lo];
}
于 2017-03-14T13:35:05.117 回答
0

我会largestList<Item>. 在您的循环中,您可以执行以下操作:

largest.add(current);
bubbleSort(largest);
if ( largest.size() > 100 ) {
  largest.remove(0);
}

通过使用冒泡排序,您可以保持O(n)复杂性,因为冒泡排序的特征之一是,如果只有一个条目不合适,它会O(n)及时执行。

我把它留给学生来实施bubbleSort

于 2017-03-14T13:24:57.677 回答