面试题： 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，万一有几行数据的长度直接超过内存大小怎么办。无解吧