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

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

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

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

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