|
精华帖 (1) :: 良好帖 (0) :: 新手帖 (11) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-10-12
最后修改：2009-10-13
J-catTeam 写道 云中苍月 写道 云中苍月 写道 如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
自己犯傻，被2G内存的条件忽悠了。 其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。 这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。 朋友 你这样好像是不可行的 1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间? 2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间 我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？ 当然，你的思路和别人不一样哈 最小堆，复杂度3000W*lg50 http://leon-a.iteye.com/blog/483918 |
| 返回顶楼 | |
|
发表时间：2009-10-15
这个题目可以抽象为这样：
一个数据文件，有3000W行，每行有一个id号，文件内容无任何排序。 现在让你把id前 TOP 位取出来, TOP = 50. 要求：你的程序最多能吃2G的内存，其他不限，要求考虑io/cup最优。 解决思路： 1 建一个top_array, 长度为50. 2 再建一个buffer, 长度为2^20 (1G) 3 循环开始 4 读取文件到buffer，直到buffer满为止 5 将Buffer的前50位读到top_array 7 将top_array排序，按照id升序 6 循环开始 7 接着读取buffer的下一位 如果比最后一个还大，next; 否则，插入到top_array相应位置，并删除最后一个。 循环到Buffer全部读完为止 9 循环到文件读完为止 |
| 返回顶楼 | |
|
发表时间：2009-10-15
dazuiba 写道 这个题目可以抽象为这样：
一个数据文件，有3000W行，每行有一个id号，文件内容无任何排序。 现在让你把id前 TOP 位取出来, TOP = 50. 要求：你的程序最多能吃2G的内存，其他不限，要求考虑io/cup最优。 解决思路： 1 建一个top_array, 长度为50. 2 再建一个buffer, 长度为2^20 (1G) 3 循环开始 4 读取文件到buffer，直到buffer满为止 5 将Buffer的前50位读到top_array 7 将top_array排序，按照id升序 6 循环开始 7 接着读取buffer的下一位 如果比最后一个还大，next; 否则，插入到top_array相应位置，并删除最后一个。 循环到Buffer全部读完为止 9 循环到文件读完为止 和我的思路基本一致。楼主思考时请摆脱“数据库”“SQL”之类的干扰条件。 |
| 返回顶楼 | |
|
发表时间：2009-10-15
云中苍月 写道 dazuiba 写道 这个题目可以抽象为这样：
一个数据文件，有3000W行，每行有一个id号，文件内容无任何排序。 现在让你把id前 TOP 位取出来, TOP = 50. 要求：你的程序最多能吃2G的内存，其他不限，要求考虑io/cup最优。 解决思路： 1 建一个top_array, 长度为50. 2 再建一个buffer, 长度为2^20 (1G) 3 循环开始 4 读取文件到buffer，直到buffer满为止 5 将Buffer的前50位读到top_array 7 将top_array排序，按照id升序 6 循环开始 7 接着读取buffer的下一位 如果比最后一个还大，next; 否则，插入到top_array相应位置，并删除最后一个。 循环到Buffer全部读完为止 9 循环到文件读完为止 和我的思路基本一致。楼主思考时请摆脱“数据库”“SQL”之类的干扰条件。 谢谢~~ |
| 返回顶楼 | |
