从包含10亿整数的文件中显示前100个整数的最有效方法。内存最多可容纳100万个整数

文件中存储10亿个整数。每个整数一行。内存一次可以支持一百万个整数的加载。我们需要显示100个最大的整数。从包含10亿整数的文件中显示前100个整数的最有效方法。内存最多可容纳100万个整数

我的想法：

这是了解优先级队列的时间。 – MBo

@MBo：我想过优先队列。它在一个堆数据结构中实现。我能读到前100万个电话号码的最大堆，但接下来呢？ –

解释回答 – MBo

你只需要遍历文件一次：

编辑：插入一个新的号码进入前100 为O（n）如果你使用一个排序的列表和O（日志（n））如果您使用堆。因此，如果进程的性能取决于插入，则使用堆是有意义的。如果它主要取决于阅读文件，那么它并不重要。

2016-04-21 08:59:54 fafl

你将最终以这种方式进行1000亿次比较。应至少保持结构的顺序，以便您可以比较最低的条目。 –

你只能比较最低的元素。 – fafl

只要它是一个有序的结构，是的。刚才在我的评论中写道。 –

构建min-heap为前100个元素。

对于每个新元素检查 - 如果它比堆顶部大，删除顶部，插入新元素。

堆大小始终是100 所以整体复杂度为O（N *日志（100））= O（N）
（在k个值顶部常见的情况 - O（N日志k））的

Million只是用作从文件中读取的最大块大小，然后遍历它。

2016-04-21 09:13:11 MBo

一般的解法是O（n log k），当'k'相对于n'很小时，本质上是O（n）。 –

回答