今天去面试，面试的人问了一道题：8G 的内存，有个 100G 的文件（文本文件，每一行都是一个独立的字符串），如何读取文件里的内容，并按行字符串排序，然后将排序后的结果保存到另一个文件里？
没答上来……这里涉及计算机的那个范畴的知识？
没答上来……这里涉及计算机的那个范畴的知识？
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2758 days ago, the information mentioned may be changed or developed.
 |
KiriyaApr 17, 2019
1
计算机基础
|
 |
2
就是归并排序啊
|
1 |
goodleixiaoApr 17, 2019
3
计算机算法之外部排序
|
 |
jasonyang9Apr 17, 2019
4
这个问题 OS 的虚拟内存技术会帮你解决的？
|
 |
geekc3tApr 17, 2019
5
感觉跟我以前遇到过的,36 匹马,6 个跑道.找出最快 6 匹马,差不多
|
 |
ninja911Apr 17, 2019
6
fread 设置 buffer 长度，不晓得是不是想问这样的骚操作
|
 |
enenaaaApr 17, 2019
7
用堆排序求出 Top N， 再从剩余的数据中求出 Top N ~ 2N， 如此往复。
|
 |
pmispigApr 17, 2019
8
首先假设全是字母，当然不是字母是 ascii 字符也可以
|
|
pmispigApr 17, 2019
9
我想到一个笨办法，先根据每行第一个字母把文件进行拆分为 36 个文件，如果单个文件还太大，可以根据第 2 个字母进行二次拆分以及多次拆分，然后读取单个文件到内存用语言的内置排序方法进行排序后再整合成一个文件。
|
 |
10
外部排序嘛，多路归并
|
 |
11
数据结构：外部排序 / 内存外排序。
|
 |
murmurApr 17, 2019
12
mapreduce
|
 |
mytryApr 17, 2019
13
又没问算法，不如直接来个 SQL 算了- -
|
 |
reusApr 17, 2019
14
按行读入几 G，排序后写入临时文件
重复上一步，直到处理完 100G 读所有临时文件，做归并，写入最终文件 |
 |
acrossApr 17, 2019 via iPhone
15
就是考察算法的应用....
好像最早看到人发的是 qq 还是微信的题目 |
 |
q4336431Apr 17, 2019
16
8g 内存，100g 文件，每一行都是一个独立的字符串。。。linux sort 命令
|
 |
VegetableApr 17, 2019
17
说一下我之前是怎么做的,当时我们是有一个几十个 G 的文本文件,内部是 md5 值的.对这个进行排序.
我采用的方法很见到 先根据前三个或者前两个字符进行分类,就会得到 16*16 或者 16*16*16 个文件,将他们直接读入内存,排序,写会文件,再将缓存文件连接成一个文件,结果就是排序完毕的了. |
 |
quereApr 17, 2019
18
mapreduce spark ???
|
 |
dl2kApr 17, 2019
20
算法很多样 map reduce 或者分类计算都可以，但是其实还是需要其他空间 这个题其实有 bug，万一有几行数据的长度直接超过内存大小怎么办。无解吧
|
 |
winglight2016Apr 17, 2019
21
@dl2k 没那么复杂呀，每行只读取第一个字符就好，真的有两行前 4G 内容都一样，也有虚拟内存帮忙啦
|
 |
814084764Apr 17, 2019
22
sleep 排序
|
 |
gamexgApr 17, 2019 via Android
23
忘了名了，
分开排序在合并就行。 |
 |
yangxin0Apr 17, 2019
24
先读 N 行, 保证内存 8G 以内, 然后排序, 然后写入文件. 以此类推, 最后归并排序
|
 |
jmc891205Apr 17, 2019 via iPhone
25
最近刚好做了这样的项目
你可以先把 100g 文件分割成 13 个有序的 fragment files 然后把每个文件的第一条数据读进内存 建一个最小堆 每次把堆顶出堆写到输出文件里 再把它对应的下一条数据入堆 如此循环直到堆变空 最后的输出文件就是排好序的 100g 文件了 楼上有些朋友提到了这个方法 我稍微多写了一些细节 手机打字 如有错别字多多包涵 |
 |
26
经济不好的时候就开始讨论算法了。
|
 |
icyalalaApr 17, 2019
27
直接 mmap 然后。。
|
 |
hisenyuanApr 17, 2019
28
归并排序了解一下。
|
 |
PandaRunApr 17, 2019 via Android
29
可以转字符集排序吗
|
 |
xdluckyApr 17, 2019 via iPhone
30
虚拟内存+1，这属于 x86 的基础知识...
|
 |
fsafdasfsdafsdApr 17, 2019
31
多路归并
|
 |
mingl0280Apr 18, 2019
32
暴力一点，直接按 2-3G 拆一个文件，排序子文件，然后子文件有序以后归并到 100G。
|
 |
LokiSharpApr 18, 2019 via iPhone
33
硬盘上写个文件当缓存就行了
|
 |
luozicApr 18, 2019
34
數據庫的各種算法都支持這麽玩。
|
 |
fengmenggaokaoApr 18, 2019
35
|
 |
specitaApr 18, 2019
36
我当年毕业找工作面某公司就被问到过这个问题
|
 |
liaokaimeApr 18, 2019
37
给您买 100G 内存可以让我入职吗？
|
 |
qsbaqApr 18, 2019
38
感觉 linux 命令行可以搞定。
|
Select Language