面试题： 8G 内存， 100G 文件

[liujianwei]

今天去面试，面试的人问了一道题：8G 的内存，有个 100G 的文件（文本文件，每一行都是一个独立的字符串），如何读取文件里的内容，并按行字符串排序，然后将排序后的结果保存到另一个文件里？

没答上来……这里涉及计算机的那个范畴的知识？

[winglight2016]

@dl2k 没那么复杂呀，每行只读取第一个字符就好，真的有两行前 4G 内容都一样，也有虚拟内存帮忙啦

[814084764]

sleep 排序

[gamexg]

忘了名了，
分开排序在合并就行。

[yangxin0]

先读 N 行, 保证内存 8G 以内, 然后排序, 然后写入文件. 以此类推, 最后归并排序

[jmc891205]

最近刚好做了这样的项目
你可以先把 100g 文件分割成 13 个有序的 fragment files
然后把每个文件的第一条数据读进内存 建一个最小堆
每次把堆顶出堆写到输出文件里 再把它对应的下一条数据入堆
如此循环直到堆变空 最后的输出文件就是排好序的 100g 文件了

楼上有些朋友提到了这个方法 我稍微多写了一些细节
手机打字 如有错别字多多包涵

[zhuziyi]

经济不好的时候就开始讨论算法了。

[icyalala]

直接 mmap 然后。。

[hisenyuan]

归并排序了解一下。

[PandaRun]

可以转字符集排序吗

[xdlucky]

虚拟内存+1，这属于 x86 的基础知识...

[fsafdasfsdafsd]

多路归并

[mingl0280]

暴力一点，直接按 2-3G 拆一个文件，排序子文件，然后子文件有序以后归并到 100G。

[LokiSharp]

硬盘上写个文件当缓存就行了

[luozic]

數據庫的各種算法都支持這麽玩。

[fengmenggaokao]

https://www.cnblogs.com/chengxiao/p/6194356.html

[specita]

我当年毕业找工作面某公司就被问到过这个问题

[liaokaime]

给您买 100G 内存可以让我入职吗？

[qsbaq]

感觉 linux 命令行可以搞定。