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

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

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

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

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