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

[liujianwei]

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

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

[Kiriya]

计算机基础

[earendil1412]

就是归并排序啊

[goodleixiao]

计算机算法之外部排序

[jasonyang9]

这个问题 OS 的虚拟内存技术会帮你解决的？

[geekc3t]

感觉跟我以前遇到过的,36 匹马,6 个跑道.找出最快 6 匹马,差不多

[ninja911]

fread 设置 buffer 长度，不晓得是不是想问这样的骚操作

[enenaaa]

用堆排序求出 Top N， 再从剩余的数据中求出 Top N ~ 2N， 如此往复。

[pmispig]

首先假设全是字母，当然不是字母是 ascii 字符也可以

[pmispig]

我想到一个笨办法，先根据每行第一个字母把文件进行拆分为 36 个文件，如果单个文件还太大，可以根据第 2 个字母进行二次拆分以及多次拆分，然后读取单个文件到内存用语言的内置排序方法进行排序后再整合成一个文件。

[Luckyray]

外部排序嘛，多路归并

[Tianao]

数据结构：外部排序 / 内存外排序。

[murmur]

mapreduce

[mytry]

又没问算法，不如直接来个 SQL 算了- -

[reus]

按行读入几 G，排序后写入临时文件
重复上一步，直到处理完 100G
读所有临时文件，做归并，写入最终文件

[across]

就是考察算法的应用....
好像最早看到人发的是 qq 还是微信的题目

[q4336431]

8g 内存，100g 文件，每一行都是一个独立的字符串。。。linux sort 命令

[Vegetable]

说一下我之前是怎么做的,当时我们是有一个几十个 G 的文本文件,内部是 md5 值的.对这个进行排序.
我采用的方法很见到
先根据前三个或者前两个字符进行分类,就会得到 16*16 或者 16*16*16 个文件,将他们直接读入内存,排序,写会文件,再将缓存文件连接成一个文件,结果就是排序完毕的了.

[quere]

mapreduce spark ???

[stebest]

@q4336431 这么骚面试官怎么敢要

[dl2k]

算法很多样 map reduce 或者分类计算都可以，但是其实还是需要其他空间 这个题其实有 bug，万一有几行数据的长度直接超过内存大小怎么办。无解吧

[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 命令行可以搞定。