V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
liujianwei
V2EX  ›  程序员

面试题: 8G 内存, 100G 文件

  •  
  •   liujianwei ·
    jianliuwei · 2019-04-17 16:02:20 +08:00 · 9015 次点击
    这是一个创建于 1807 天前的主题,其中的信息可能已经有所发展或是发生改变。
    今天去面试,面试的人问了一道题:8G 的内存,有个 100G 的文件(文本文件,每一行都是一个独立的字符串),如何读取文件里的内容,并按行字符串排序,然后将排序后的结果保存到另一个文件里?

    没答上来……这里涉及计算机的那个范畴的知识?
    38 条回复    2019-04-18 14:17:22 +08:00
    Kiriya
        1
    Kiriya  
       2019-04-17 16:05:54 +08:00
    计算机基础
    earendil1412
        2
    earendil1412  
       2019-04-17 16:07:17 +08:00 via Android   ❤️ 1
    就是归并排序啊
    goodleixiao
        3
    goodleixiao  
       2019-04-17 16:08:07 +08:00
    计算机算法之外部排序
    jasonyang9
        4
    jasonyang9  
       2019-04-17 16:11:24 +08:00
    这个问题 OS 的虚拟内存技术会帮你解决的?
    geekc3t
        5
    geekc3t  
       2019-04-17 16:15:16 +08:00
    感觉跟我以前遇到过的,36 匹马,6 个跑道.找出最快 6 匹马,差不多
    ninja911
        6
    ninja911  
       2019-04-17 16:20:39 +08:00
    fread 设置 buffer 长度,不晓得是不是想问这样的骚操作
    enenaaa
        7
    enenaaa  
       2019-04-17 16:23:28 +08:00
    用堆排序求出 Top N, 再从剩余的数据中求出 Top N ~ 2N, 如此往复。
    pmispig
        8
    pmispig  
       2019-04-17 16:23:32 +08:00
    首先假设全是字母,当然不是字母是 ascii 字符也可以
    pmispig
        9
    pmispig  
       2019-04-17 16:27:49 +08:00
    我想到一个笨办法,先根据每行第一个字母把文件进行拆分为 36 个文件,如果单个文件还太大,可以根据第 2 个字母进行二次拆分以及多次拆分,然后读取单个文件到内存用语言的内置排序方法进行排序后再整合成一个文件。
    Luckyray
        10
    Luckyray  
       2019-04-17 16:28:29 +08:00   ❤️ 1
    外部排序嘛,多路归并
    Tianao
        11
    Tianao  
       2019-04-17 16:30:28 +08:00 via iPhone   ❤️ 1
    数据结构:外部排序 / 内存外排序。
    murmur
        12
    murmur  
       2019-04-17 16:33:38 +08:00
    mapreduce
    mytry
        13
    mytry  
       2019-04-17 16:33:54 +08:00
    又没问算法,不如直接来个 SQL 算了- -
    reus
        14
    reus  
       2019-04-17 16:35:30 +08:00
    按行读入几 G,排序后写入临时文件
    重复上一步,直到处理完 100G
    读所有临时文件,做归并,写入最终文件
    across
        15
    across  
       2019-04-17 16:38:29 +08:00 via iPhone
    就是考察算法的应用....
    好像最早看到人发的是 qq 还是微信的题目
    q4336431
        16
    q4336431  
       2019-04-17 16:49:55 +08:00
    8g 内存,100g 文件,每一行都是一个独立的字符串。。。linux sort 命令
    Vegetable
        17
    Vegetable  
       2019-04-17 17:10:06 +08:00
    说一下我之前是怎么做的,当时我们是有一个几十个 G 的文本文件,内部是 md5 值的.对这个进行排序.
    我采用的方法很见到
    先根据前三个或者前两个字符进行分类,就会得到 16*16 或者 16*16*16 个文件,将他们直接读入内存,排序,写会文件,再将缓存文件连接成一个文件,结果就是排序完毕的了.
    quere
        18
    quere  
       2019-04-17 17:17:04 +08:00
    mapreduce spark ???
    stebest
        19
    stebest  
       2019-04-17 17:23:26 +08:00
    @q4336431 这么骚面试官怎么敢要
    dl2k
        20
    dl2k  
       2019-04-17 17:47:39 +08:00
    算法很多样 map reduce 或者分类计算都可以,但是其实还是需要其他空间 这个题其实有 bug,万一有几行数据的长度直接超过内存大小怎么办。无解吧
    winglight2016
        21
    winglight2016  
       2019-04-17 17:54:34 +08:00
    @dl2k 没那么复杂呀,每行只读取第一个字符就好,真的有两行前 4G 内容都一样,也有虚拟内存帮忙啦
    814084764
        22
    814084764  
       2019-04-17 18:18:46 +08:00
    sleep 排序
    gamexg
        23
    gamexg  
       2019-04-17 19:14:00 +08:00 via Android
    忘了名了,
    分开排序在合并就行。
    yangxin0
        24
    yangxin0  
       2019-04-17 19:19:35 +08:00
    先读 N 行, 保证内存 8G 以内, 然后排序, 然后写入文件. 以此类推, 最后归并排序
    jmc891205
        25
    jmc891205  
       2019-04-17 19:23:32 +08:00 via iPhone
    最近刚好做了这样的项目
    你可以先把 100g 文件分割成 13 个有序的 fragment files
    然后把每个文件的第一条数据读进内存 建一个最小堆
    每次把堆顶出堆写到输出文件里 再把它对应的下一条数据入堆
    如此循环直到堆变空 最后的输出文件就是排好序的 100g 文件了

    楼上有些朋友提到了这个方法 我稍微多写了一些细节
    手机打字 如有错别字多多包涵
    zhuziyi
        26
    zhuziyi  
       2019-04-17 19:28:10 +08:00 via iPhone   ❤️ 3
    经济不好的时候就开始讨论算法了。
    icyalala
        27
    icyalala  
       2019-04-17 19:36:28 +08:00
    直接 mmap 然后。。
    hisenyuan
        28
    hisenyuan  
       2019-04-17 19:51:49 +08:00
    归并排序了解一下。
    PandaRun
        29
    PandaRun  
       2019-04-17 20:27:00 +08:00 via Android
    可以转字符集排序吗
    xdlucky
        30
    xdlucky  
       2019-04-17 20:30:49 +08:00 via iPhone
    虚拟内存+1,这属于 x86 的基础知识...
    fsafdasfsdafsd
        31
    fsafdasfsdafsd  
       2019-04-17 21:09:07 +08:00
    多路归并
    mingl0280
        32
    mingl0280  
       2019-04-18 02:28:26 +08:00
    暴力一点,直接按 2-3G 拆一个文件,排序子文件,然后子文件有序以后归并到 100G。
    LokiSharp
        33
    LokiSharp  
       2019-04-18 08:03:07 +08:00 via iPhone
    硬盘上写个文件当缓存就行了
    luozic
        34
    luozic  
       2019-04-18 09:15:00 +08:00
    數據庫的各種算法都支持這麽玩。
    fengmenggaokao
        35
    fengmenggaokao  
       2019-04-18 10:27:45 +08:00
    specita
        36
    specita  
       2019-04-18 11:07:10 +08:00
    我当年毕业找工作面某公司就被问到过这个问题
    liaokaime
        37
    liaokaime  
       2019-04-18 12:49:08 +08:00
    给您买 100G 内存可以让我入职吗?
    qsbaq
        38
    qsbaq  
       2019-04-18 14:17:22 +08:00
    感觉 linux 命令行可以搞定。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3442 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 11:11 · PVG 19:11 · LAX 04:11 · JFK 07:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.