这是一个创建于 2072 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天去面试，面试的人问了一道题：8G 的内存，有个 100G 的文件（文本文件，每一行都是一个独立的字符串），如何读取文件里的内容，并按行字符串排序，然后将排序后的结果保存到另一个文件里？
没答上来……这里涉及计算机的那个范畴的知识？
没答上来……这里涉及计算机的那个范畴的知识？
 |
1
Kiriya 2019-04-17 16:05:54 +08:00
计算机基础
|
 |
2
earendil1412 2019-04-17 16:07:17 +08:00 via Android  1
就是归并排序啊
|
 |
3
goodleixiao 2019-04-17 16:08:07 +08:00
计算机算法之外部排序
|
 |
4
jasonyang9 2019-04-17 16:11:24 +08:00
这个问题 OS 的虚拟内存技术会帮你解决的？
|
 |
5
geekc3t 2019-04-17 16:15:16 +08:00
感觉跟我以前遇到过的,36 匹马,6 个跑道.找出最快 6 匹马,差不多
|
 |
6
ninja911 2019-04-17 16:20:39 +08:00
fread 设置 buffer 长度，不晓得是不是想问这样的骚操作
|
 |
7
enenaaa 2019-04-17 16:23:28 +08:00
用堆排序求出 Top N， 再从剩余的数据中求出 Top N ~ 2N， 如此往复。
|
 |
8
pmispig 2019-04-17 16:23:32 +08:00
首先假设全是字母，当然不是字母是 ascii 字符也可以
|
|
9
pmispig 2019-04-17 16:27:49 +08:00
我想到一个笨办法，先根据每行第一个字母把文件进行拆分为 36 个文件，如果单个文件还太大，可以根据第 2 个字母进行二次拆分以及多次拆分，然后读取单个文件到内存用语言的内置排序方法进行排序后再整合成一个文件。
|
 |
10
Luckyray 2019-04-17 16:28:29 +08:00 1
外部排序嘛，多路归并
|
 |
11
Tianao 2019-04-17 16:30:28 +08:00 via iPhone 1
数据结构：外部排序 / 内存外排序。
|
 |
12
murmur 2019-04-17 16:33:38 +08:00
mapreduce
|
 |
13
mytry 2019-04-17 16:33:54 +08:00
又没问算法，不如直接来个 SQL 算了- -
|
 |
14
reus 2019-04-17 16:35:30 +08:00
按行读入几 G，排序后写入临时文件
重复上一步，直到处理完 100G 读所有临时文件，做归并，写入最终文件 |
 |
15
across 2019-04-17 16:38:29 +08:00 via iPhone
就是考察算法的应用....
好像最早看到人发的是 qq 还是微信的题目 |
 |
16
q4336431 2019-04-17 16:49:55 +08:00
8g 内存，100g 文件，每一行都是一个独立的字符串。。。linux sort 命令
|
 |
17
Vegetable 2019-04-17 17:10:06 +08:00
说一下我之前是怎么做的,当时我们是有一个几十个 G 的文本文件,内部是 md5 值的.对这个进行排序.
我采用的方法很见到 先根据前三个或者前两个字符进行分类,就会得到 16*16 或者 16*16*16 个文件,将他们直接读入内存,排序,写会文件,再将缓存文件连接成一个文件,结果就是排序完毕的了. |
 |
18
quere 2019-04-17 17:17:04 +08:00
mapreduce spark ???
|
 |
20
dl2k 2019-04-17 17:47:39 +08:00
算法很多样 map reduce 或者分类计算都可以，但是其实还是需要其他空间 这个题其实有 bug，万一有几行数据的长度直接超过内存大小怎么办。无解吧
|
 |
21
winglight2016 2019-04-17 17:54:34 +08:00
@dl2k 没那么复杂呀，每行只读取第一个字符就好，真的有两行前 4G 内容都一样，也有虚拟内存帮忙啦
|
 |
22
814084764 2019-04-17 18:18:46 +08:00
sleep 排序
|
 |
23
gamexg 2019-04-17 19:14:00 +08:00 via Android
忘了名了，
分开排序在合并就行。 |
 |
24
yangxin0 2019-04-17 19:19:35 +08:00
先读 N 行, 保证内存 8G 以内, 然后排序, 然后写入文件. 以此类推, 最后归并排序
|
 |
25
jmc891205 2019-04-17 19:23:32 +08:00 via iPhone
最近刚好做了这样的项目
你可以先把 100g 文件分割成 13 个有序的 fragment files 然后把每个文件的第一条数据读进内存 建一个最小堆 每次把堆顶出堆写到输出文件里 再把它对应的下一条数据入堆 如此循环直到堆变空 最后的输出文件就是排好序的 100g 文件了 楼上有些朋友提到了这个方法 我稍微多写了一些细节 手机打字 如有错别字多多包涵 |
 |
26
zhuziyi 2019-04-17 19:28:10 +08:00 via iPhone 3
经济不好的时候就开始讨论算法了。
|
 |
27
icyalala 2019-04-17 19:36:28 +08:00
直接 mmap 然后。。
|
 |
28
hisenyuan 2019-04-17 19:51:49 +08:00
归并排序了解一下。
|
 |
29
PandaRun 2019-04-17 20:27:00 +08:00 via Android
可以转字符集排序吗
|
 |
30
xdlucky 2019-04-17 20:30:49 +08:00 via iPhone
虚拟内存+1，这属于 x86 的基础知识...
|
 |
31
fsafdasfsdafsd 2019-04-17 21:09:07 +08:00
多路归并
|
 |
32
mingl0280 2019-04-18 02:28:26 +08:00
暴力一点，直接按 2-3G 拆一个文件，排序子文件，然后子文件有序以后归并到 100G。
|
 |
33
LokiSharp 2019-04-18 08:03:07 +08:00 via iPhone
硬盘上写个文件当缓存就行了
|
 |
34
luozic 2019-04-18 09:15:00 +08:00
數據庫的各種算法都支持這麽玩。
|
 |
35
fengmenggaokao 2019-04-18 10:27:45 +08:00
|
 |
36
specita 2019-04-18 11:07:10 +08:00
我当年毕业找工作面某公司就被问到过这个问题
|
 |
37
liaokaime 2019-04-18 12:49:08 +08:00
给您买 100G 内存可以让我入职吗？
|
 |
38
qsbaq 2019-04-18 14:17:22 +08:00
感觉 linux 命令行可以搞定。
|
Select Language