关注
67.假设1亿的11位的手机号,运行空间128M,如果要进行排序,那么要怎么设计:
本问题中,可以借鉴归并排序的思路,将大文件拆成100个小文件,小文件内部排好序,然后进行100路的归并操作。
步骤
将 1. G的大文件,经过一遍按行读写的方式(迭代器模式)进行处理,拆成 100 100 100个小文件,每个小文件中存放100万个手机号。
分别将100个小文件读进内存,将手机号从小到大排序,排序结果写回对应的小文件中。
通过一个小顶堆形式的优先级队列(PriorityQueue)进行归并操作。堆中的元素是一个二元组:(手机号, 该手机号对应的小文件编号)。
一开始,将每个文件的第一个手机号读出来放到小顶堆中。由于这 100 100 100个手机号分别是各个子文件中最小的,因此,此时小顶堆堆顶的手机号就是全局最小的手机号。因此可以将堆顶元素弹出,写到最终的输出文件mobiles_sorted.txt中。
每次从堆顶弹出一个元素后,如果该元素所对应的小文件还没被处理完,就从相应小文件中读入下一个手机号,补充到堆中。
所有手机号都各自加入和弹出小顶堆一次后,排序完成,此时的mobiles_sorted.txt文件就是最终结果
查看原帖
点赞 评论
相关推荐
03-28 16:09
营口理工学院 新材料/环保技术 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习进度记录 #
154414次浏览 1719人参与
# 我的求职精神状态 #
2887次浏览 78人参与
# 平安产险科技中心求职汇总 #
244491次浏览 2613人参与
# 京东美团大战,你怎么看? #
21176次浏览 190人参与
# 好未来求职进展汇总 #
6007次浏览 46人参与
# 大家每天通勤多久? #
30944次浏览 229人参与
# Keep实习校招 #
48916次浏览 252人参与
# 大城市找工作会更容易吗 #
16409次浏览 125人参与
# 金山WPS工作体验 #
20772次浏览 133人参与
# 提前批过来人的忠告 #
97675次浏览 1092人参与
# 签约有哪些注意事项 #
27078次浏览 227人参与
# 招银网络科技工作体验 #
18829次浏览 85人参与
# 生化环材还是天坑吗 #
30031次浏览 277人参与
# 4399求职进展汇总 #
17521次浏览 139人参与
# 中兴求职进展汇总 #
579578次浏览 2614人参与
# 华为存储OD事变 #
121676次浏览 681人参与
# 京东工作体验 #
12535次浏览 88人参与
# 生物制药/化工校招攻略 #
39965次浏览 275人参与
# 校招第一份工作你干了多久? #
66753次浏览 334人参与
# 腾讯音乐求职进展汇总 #
82135次浏览 450人参与
# 小红书求职进展汇总 #
49612次浏览 441人参与
# 宁德时代求职进展汇总 #
104940次浏览 622人参与