如何给100亿个数字排序?
今天要给100亿个数字排序,100亿个 int 型数字放在文件里面大概有 37.2GB,非常大,内存一次装不下了。那么肯定是要拆分成小的文件一个一个来处理,最终在合并成一个排好序的大文件。
NetSmell 出品
今天要给100亿个数字排序,100亿个 int 型数字放在文件里面大概有 37.2GB,非常大,内存一次装不下了。那么肯定是要拆分成小的文件一个一个来处理,最终在合并成一个排好序的大文件。
实现思路
1.把这个37GB的大文件,用哈希分成1000个小文件,每个小文件平均38MB左右(理想情况),把100亿个数字对1000取模,模出来的结果在0到999之间,每个结果对应一个文件,所以我这里取的哈希函数是 h = x % 1000,哈希函数取得”好”,能使冲突减小,结果分布均匀。
2.拆分完了之后,得到一些几十MB的小文件,那么就可以放进内存里排序了,可以用快速排序,归并排序,堆排序等等。
3.1000个小文件内部排好序之后,就要把这些内部有序的小文件,合并成一个大的文件,可以用二叉堆来做1000路合并的操作,每个小文件是一路,合并后的大文件仍然有序。
- 首先遍历1000个文件,每个文件里面取第一个数字,组成 (数字, 文件号) 这样的组合加入到堆里(假设是从小到大排序,用小顶堆),遍历完后堆里有1000个 (数字,文件号) 这样的元素
- 然后不断从堆顶拿元素出来,每拿出一个元素,把它的文件号读取出来,然后去对应的文件里,加一个元素进入堆,直到那个文件被读取完。拿出来的元素当然追加到最终结果的文件里。
- 按照上面的操作,直到堆被取空了,此时最终结果文件里的全部数字就是有序的了。
最后我用c++写了个实验程序,具体代码在这里可以看到。
如何拆分大文件?
一个32G的大文件,用fopen()打开不会全部加载到内存的,然后for循环遍历啊,把每个数字对1000取模,会得到0到999种结果,然后每种结果在写入到新的文件中,就拆分了
显示余下内容
相关文章:
奥斯卡最大黑马?全片无台词的电影凭什么!
剧版《史密斯夫妇》瞎改经典,全网抵制,打脸了?
2024必看神作!《首尔之春》太敢拍了!
韩剧《共助》从头爽到尾,这部谍战电影帅爆了!
地狱客栈 第一季 8.6,该动画已屏蔽全体儿童
《杀人者的购物中心》又来一部王炸爽剧,杀疯了
《12年级的失败》神片来袭,印度版“小镇做题家”太上头!
《地狱客栈》第一季单集9.0分,千年等一回,这神仙动画我爱了
《荒野》马东锡血浆片,虽烂但爽
韩剧《观相》豪华阵容 狂飙演技,宋康昊首部古装大片!
电影「花千骨」怒冲3.5,「开年第一烂」出现了!
《好久没做》韩国情色片已经进化到地步了吗
《魅惑之人》王位争夺 一集入坑,2024最新古装复仇大剧!
《命案》必看的华语大尺度电影
《好久没做》少儿不宜,这部韩剧尺度也太大了吧
「临时劫案」超级烂片,天王也救不了
《绝境盟约》提名奥斯卡,挑战观影极限,一年难出一部
《绝境盟约》震撼全球的真实事件,这电影尺度太逆天
《请和我的老公结婚》开年第一部韩剧,血压爆表、狗血至极!
《临时劫案》卡司阵容强大却换来口碑暴跌,谢谢有被雷到!
发表回复