从一百万条记录中获取前 10 名和后 10 名

Question

我有一份报告显示 2-4 百万条记录。我从 oracle 获取记录到 java 并将其推送到 excel 报告。这一切都已经完成了！

现在，我还需要添加一个包含前 10 条记录和最后 10 条记录的新选项卡。最好的方法是什么？

我应该在 java 中使用 PriorityQueue 实现还是使用二叉树来跟踪前 10 名和最后 10 名。我不需要在数据结构中存储十亿条记录。我一次只需要存10个。例如：

PriorityQueue<DataObject> queueTop10 = new PriorityQueue<DataObject>(10, topComparator);
PriorityQueue<DataObject> queueLast10 = new PriorityQueue<DataObject>(10, leastComparator);
    while (data is coming from database)
    {
    // push to excel stuff here
    queueTop10 .add(dataObject);   OR binarytreeTop.insert(dataObject)
    queueLast10.add(dataObject);   OR binarytreeLeast.insert(dataObject)
    }

如果我也可以使用其他数据结构，请告诉我。

谢谢

Answer 1

您可以使用优先级队列，因为它在 Java 中的作用类似于堆。参见 How does Java's PriorityQueue differ from a min-heap? If no difference, then why was it named PriorityQueue and not Heap?

Answer 2

热门算法使用最小堆（PriorityQueue in Java），但您的算法中应该有一些大小检查。假设每个项目都有一个分数，你想收集分数最高的 10 个项目。 PriorityQueue 有效地公开了最低分数的项目：

PriorityQueue<DataObject> top = new PriorityQueue(10, comparator);
for (DataObject item : items) {
  if (top.size() < 10) top.add(item);
  else if(comparator.compare(top.peek(), item) < 0) {
    top.remove();
    top.add(item);
  }
}

Answer 3

PriorityQueue<T> 将无法按原样使用您的代码，因为构造函数中的 10 是初始容量；你的队列将随着你的增长而增长到 1B 项。

但是，TreeSet<T> 只需稍作修改即可。您需要添加代码，每当队列超过 10 时删除第 11 个项目：

TreeSet<DataObject> top10 = new TreeSet<DataObject>(topComparator);
TreeSet<DataObject> bottom10 = new TreeSet<DataObject>(leastComparator);
while (data is coming from database) {
    top10.add(dataObject);
    if (top10.size() == 11) {
        top10.pollLast();
    }
    bottom10.add(dataObject);
    if (bottom10.size() == 11) {
        bottom10.pollLast();
    }
}

Answer 4

excel 电子表格中有 40 亿条记录？不，你没有 https://superuser.com/questions/366468/what-is-the-maximum-allowed-rows-in-a-microsoft-excel-xls-or-xlsx

您应该在数据库上执行此操作，而不是依赖 java 实现。对于如此多的记录，它的效率必然低于优化的数据库查询。

从一百万条记录中获取前 10 名和后 10 名

Get top 10 and last 10 from a million records

java

binary-tree

priority-queue

binary-search-tree