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

大文件定位某一行?

  •  2
     
  •   kaiser1992 · 2017-08-22 19:13:37 +08:00 · 8682 次点击
    这是一个创建于 2629 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现有一个很大的文件(比如 40G 的文本),假如我随机定位某一行,怎么样实现最快(时间和空间)?
    希望 V 友们想什么说什么,畅所欲言
    第 1 条附言  ·  2017-08-23 09:46:19 +08:00
    看了各位 V 友们的回答,谢谢大家。
    大家的看法大致总结如下:
    1.采用 linux 自带的文本查询工具 grep 指令和 awk 指令来实现。但是这个需求不能借助系统的命令工具。
    2.构建索引的思想,扫描一遍文本,将行数和换行符构建索引,这样构建完索引之后,搜索查询是快,可是前期扫面文件需要的时间不能不考虑。

    现重新把题目再明确一下:
    1.文本中每行的数据是不固定的,不能够直接计算偏移量来直接定位。
    2.假定一个具体场景,假如文本中每行只存储长度不定的数字 Id(比如 8,9,10...位等),现在我随机指定某行数,要实现将该行对应的数字 ID 读出来。
    第 2 条附言  ·  2017-08-23 15:16:42 +08:00
    谢谢大家的回答,我还是没有找到良好的解决办法。
    现实中大家的确不会遇到这么大的文件,由于目前正在做搜索这方面的工作,涉及到的数据量特别大,当然 40G 有点大的不合理,一般情况下是几个 G 的文本内容,上面说到文本内容只有数字的话,可否在数字特征规律上下功夫呢?
    .....个人感觉建索引是挺好的...... 逃:)
    81 条回复    2017-08-30 11:13:33 +08:00
    ashfinal
        1
    ashfinal  
       2017-08-22 19:18:29 +08:00
    40 G …… 这,这
    15015613
        2
    15015613  
       2017-08-22 19:20:18 +08:00 via Android
    查找内容的话,grep
    输出特定行,sed
    kaiser1992
        3
    kaiser1992  
    OP
       2017-08-22 19:22:26 +08:00
    @15015613 grep 是顺序查找太慢,sed 也需要遍历
    Fishdrowned
        4
    Fishdrowned  
       2017-08-22 19:41:13 +08:00 via Android
    要是打开没规律的文本文件,你倒是说什么算法不用遍历?判断行数难道不用先知道前面有几行?
    jfcherng
        5
    jfcherng  
       2017-08-22 19:42:52 +08:00   ❤️ 1
    https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

    grep 其實用了很多黑科技的,速度不是一般快。
    Fishdrowned
        6
    Fishdrowned  
       2017-08-22 19:47:20 +08:00 via Android
    优化方法估计只能多核并行遍历了。如果文件内容不会变化,遍历完之后可以缓存结果
    chunk
        7
    chunk  
       2017-08-22 19:50:19 +08:00
    dd
    sofs
        8
    sofs  
       2017-08-22 19:51:57 +08:00 via Android
    40G 的文本我不敢去操作
    qian19876025
        9
    qian19876025  
       2017-08-22 20:32:19 +08:00
    @Fishdrowned 除非大部分读进内存 不然你没法 并行
    sun1991
        10
    sun1991  
       2017-08-22 20:35:49 +08:00
    先扫描一遍, 获取所有行的 pos, 保存起来.
    reus
        11
    reus  
       2017-08-22 20:38:33 +08:00
    加索引
    Fishdrowned
        12
    Fishdrowned  
       2017-08-22 20:42:04 +08:00 via Android
    @qian19876025 当然可以并行。按文件大小设置几个断点,然后每个线程从断点处开始遍历,找到换行符就记录一下位置,并不需要多少内存。全部完成后汇总,每一行的位置都出来了
    FanWall
        13
    FanWall  
       2017-08-22 20:47:41 +08:00 via Android
    @Fishdrowned 最坏的情况缓存大小是文件大小的四倍
    Fishdrowned
        14
    Fishdrowned  
       2017-08-22 20:56:27 +08:00 via Android
    缓存大不用怕,因为缓存是有组织的,内存不够就放磁盘,快速查找不难实现。
    0ZXYDDu796nVCFxq
        15
    0ZXYDDu796nVCFxq  
       2017-08-22 20:58:38 +08:00 via iPhone
    只查找少数几次:调用 grep,如果你实现了一个比 grep 更快的算法,那牛逼大了
    经常查找:扫一遍,建个索引存下来
    lululau
        16
    lululau  
       2017-08-22 21:45:53 +08:00
    扫描一遍文件,把每一个换行符的索引记录下来,然后 dd 就可以了,不知道 dd 就 man 2 lseek
    webster
        17
    webster  
       2017-08-22 21:54:26 +08:00
    用 grep 找过 30G 的文件 感觉真的很科技 很快
    privil
        18
    privil  
       2017-08-22 22:14:30 +08:00
    gouchaoer
        19
    gouchaoer  
       2017-08-22 22:23:10 +08:00 via Android
    ls 的回答都是什么啊,lz 需求是定位某一行
    fseek 可以访问文件偏移量,但是行是以换行符确定的,你需要遍历整个文件

    要以常数时间定位某一行的话自己建立一个索引就 ok 了,先遍历文件遇到换行符就记录这是第几行,以及当前 fseek 偏移量
    kaiser1992
        20
    kaiser1992  
    OP
       2017-08-22 22:29:33 +08:00
    @gstqc 建索引需要时间,存索引需要的空间最后貌似比源文件都大了把
    EchoUtopia
        21
    EchoUtopia  
       2017-08-22 22:31:24 +08:00 via iPhone
    awk
    rrfeng
        22
    rrfeng  
       2017-08-22 22:34:54 +08:00
    随机定位是什么鬼?

    你随机给个数字,我输出行号等于这个数字的行?
    0ZXYDDu796nVCFxq
        23
    0ZXYDDu796nVCFxq  
       2017-08-22 22:47:53 +08:00 via iPhone
    @kaiser1992 索引表怎么可能比原文件大
    你要建立的是行数和偏移量两个值
    ynyounuo
        24
    ynyounuo  
       2017-08-22 23:17:18 +08:00
    Ctags
    不过 40G ???这是什么文本啊
    am241
        25
    am241  
       2017-08-22 23:28:24 +08:00 via Android
    扫一遍,记录下每个换行符的位置,然后二分搜索就够了
    qian19876025
        26
    qian19876025  
       2017-08-23 00:19:43 +08:00
    @Fishdrowned 那你还是要把东西大部分读进内存啊 难不成你不用? 难不成你知道硬盘中怎么存储的? 不读进内存你来搞
    qian19876025
        27
    qian19876025  
       2017-08-23 00:23:16 +08:00
    当然如果你的数据是 线性排序 或者 hash 固定 没有冲突的 那是另外的话了
    qian19876025
        28
    qian19876025  
       2017-08-23 00:25:41 +08:00
    如果每行数据是 固定大小的 或者能直接算出偏移值的 那也可以直接取出
    watzds
        29
    watzds  
       2017-08-23 00:28:15 +08:00 via Android
    顺序读取文件似乎每秒几百兆,30g 遍历大概得几分钟吧。
    还有个问题,30g 文件中间加一行会怎样?😁
    什么需求需要单机存储 30g 大文件?可能一开始就不应该这么存
    FanWall
        30
    FanWall  
       2017-08-23 00:38:06 +08:00 via Android
    @gstqc #23 都不用想最坏情况了,假设一个字节一行,换行符是\n,40G 光记录偏移值就要 160G 了(UL 是装不下的),如果再考虑全部空行…… 320G ?

    @qian19876025 #26 我觉得他是对的,索引是有组织的,是可以计算的,只读需要的一小段就行了。
    Fishdrowned
        31
    Fishdrowned  
       2017-08-23 01:31:54 +08:00 via Android
    @qian19876025 #26 大哥,我不知道你是怎么理解的,遍历的时候,读一小段文字进内存,获取到换行位置之后就可以释放了然后读下一段了啊,难道你要一直放在内存里?
    Fishdrowned
        32
    Fishdrowned  
       2017-08-23 01:48:13 +08:00 via Android
    打个比方,楼主有一本一万页的书,想随机精确地定位到第几个段落。

    我一个人数太慢,于是叫来 20 个人(多线 /进程),每人撕走 2000 页,让他们各自统计自己的 2000 页里面各有多少段。

    然后我等这 20 个人数完了,汇总整理一下做个索引,我不就知道这本书有几段了?

    每个线程做的事情没有什么花巧,就是遍历,只不过是适合并行计算,把时间分摊了。

    至于内存,每个人都不用把 2000 页背下来啊,他只要知道每个段落位置分布在哪里就可以了,内存不够就拿笔写下来。
    t6attack
        33
    t6attack  
       2017-08-23 02:48:02 +08:00
    “随机定位某一行” ,, 究竟是 “随机定位一行”?还是 “定位某一行”?
    前者其实简单多了,用 64 位文件指针,随便定位个位置,向前、向后找到换行符就是了。感觉实际应用中,需要的应该就是前者。
    t6attack
        34
    t6attack  
       2017-08-23 02:51:10 +08:00
    也不对。这样结果并不随机。内容多的行更容易被定位到。
    ufjfeng
        35
    ufjfeng  
       2017-08-23 04:54:11 +08:00 via iPhone
    知道行号的话,awk 就行,性能不详

    awk 'NR=n {print $0}'

    n 是行号
    ufjfeng
        36
    ufjfeng  
       2017-08-23 04:55:02 +08:00 via iPhone
    awk 'NR=n {print $0}' filename

    楼上忘了写文件名
    linux40
        37
    linux40  
       2017-08-23 07:15:24 +08:00 via Android
    40g 为什么是一个文件呢。。。
    libook
        38
    libook  
       2017-08-23 08:29:30 +08:00
    定位某一行就是定位某一个换行符,和定位某一个字母 a 或定位某一个数字 1 是一样的,都需要遍历整个文件,除非是像数据库一样做索引优化。
    个人以为 linux 提供的指令效率极高,如果还是满足不了需求的话建议想办法建起换行符的索引。
    wangyucn
        39
    wangyucn  
       2017-08-23 08:36:53 +08:00
    @kaiser1992 建索引需要时间,存索引需要的空间最后貌似比源文件都大了把

    不会,索引不一定是完全的。可以每隔 1000 行建一个索引。查找时先用索引定位到文件偏移,然后稍微做一点遍历。
    wangyucn
        40
    wangyucn  
       2017-08-23 08:40:32 +08:00
    索引例子:
    行数(单位千) 文件偏移
    1 456789 (第 1000 行的文件偏移)
    2 1234567 (第 2000 行的文件偏移)
    3 2345678 (第 2000 行的文件偏移)
    4
    wangyucn
        41
    wangyucn  
       2017-08-23 08:41:57 +08:00
    囧,正在编辑不小心发出去了。凑合看吧。 索引做成外挂式的,不需要改原文件。
    90safe
        42
    90safe  
       2017-08-23 08:53:34 +08:00
    grep 是个黑科技
    huangfs
        43
    huangfs  
       2017-08-23 09:14:46 +08:00
    rg
    kaiser1992
        44
    kaiser1992  
    OP
       2017-08-23 09:24:53 +08:00
    @wangyucn 谢谢,前期构建索引需要遍历字符位置,感觉太耗时间了
    kaiser1992
        45
    kaiser1992  
    OP
       2017-08-23 09:29:38 +08:00
    @lululau 换行符都是\n 或者\r\n 相同符号如何构建索引?
    kaiser1992
        46
    kaiser1992  
    OP
       2017-08-23 09:33:46 +08:00
    @lululau 我明白你意思了,你是要对每一行换行符的位置做一个索引
    Hozzz
        47
    Hozzz  
       2017-08-23 09:43:37 +08:00
    还不如将整个文件先拆成多个小文件,然后再并行查询(如果是构建索引,遇到频繁更新的文件,效率仍然不高)
    kaiser1992
        48
    kaiser1992  
    OP
       2017-08-23 09:50:01 +08:00
    @Hozzz 不考虑并行的方式,拆分重写小文件,需要的时间也不少,还没有考虑之后查询的时间。
    mhycy
        49
    mhycy  
       2017-08-23 09:54:18 +08:00
    楼上有人提到并行,但实际应用中可行性不大,因为数据是从磁盘顺序读取的。

    构建索引只需要记录所有\r\n or \n 的偏移量,构建时间约等于读取 40G 文件所需的时间。
    (如果 CPU 足够快的话)

    如果 CPU 在判断字符过程中消耗过大(基本不可能,除非 IO 太快)
    那么可考虑缓冲区读取多线程并行分析,但考虑到多线程开销,似乎还是单线程更靠谱。

    注意:因为 IO 的限制,没有比这个更快的定位不定长数据行的办法。
    xou130
        50
    xou130  
       2017-08-23 09:56:03 +08:00 via Android
    40G 这个大小该上 hadoop 了
    qian19876025
        51
    qian19876025  
       2017-08-23 10:07:24 +08:00
    @Fishdrowned 不管你怎么样你翻书还是串行的 除非读进内存你这就是延迟而已
    luoqeng
        52
    luoqeng  
       2017-08-23 10:15:33 +08:00
    vjnjc
        53
    vjnjc  
       2017-08-23 10:39:18 +08:00
    借楼问一下中文件你们都是怎么操作的?
    有一个 sql 文件,大概 100MB,我在 mac 下用 vim 打开都花了一分钟了。。。
    Hozzz
        54
    Hozzz  
       2017-08-23 10:47:04 +08:00
    @kaiser1992 可以在存入文件之前就对数据进行拆分,或者用个额外的进程不停对该文件进行拆分
    Hozzz
        55
    Hozzz  
       2017-08-23 10:51:23 +08:00
    @kaiser1992 另外 head 和 tail 命令不会遍历整个文件
    Fishdrowned
        56
    Fishdrowned  
       2017-08-23 11:13:09 +08:00 via Android
    @qian19876025 #51 麻烦你了解一下磁盘寻址,我已经知道某行的偏移量在哪里了,找个 offset 还要串行?
    Fishdrowned
        57
    Fishdrowned  
       2017-08-23 11:16:05 +08:00 via Android
    @kaiser1992 #44 这个时间(遍历整个文件)是必须付出的,没有捷径。
    realpg
        58
    realpg  
       2017-08-23 11:21:58 +08:00
    @vjnjc #53
    你只是需要一个对大文件友好的编辑器

    一个 10G 文本 windows 下用普通编辑器打开可能用好久,用 ultraedit 之类基本秒开,他是部分读取缓冲区的
    v2orz
        59
    v2orz  
       2017-08-23 11:46:02 +08:00
    6 楼+16 楼应该已经可以解决问题了
    popok
        60
    popok  
       2017-08-23 11:47:29 +08:00
    传说中的社工库吗
    shyling
        61
    shyling  
       2017-08-23 12:31:15 +08:00
    2333,先把它分成多个文件啊。。。例如 n 行一个文件。。。
    sola97
        62
    sola97  
       2017-08-23 12:39:00 +08:00 via Android
    社工库的既视感
    Fishdrowned
        63
    Fishdrowned  
       2017-08-23 13:22:09 +08:00 via Android
    其实并行只是理论上的优化方法,实际上 cpu 处理的速度应该是高于磁盘的吞吐量的(几百 MB/s,不考虑随机读的 iops 是因为这个可以规避)
    wangyucn
        64
    wangyucn  
       2017-08-23 13:52:08 +08:00
    @kaiser1992 `不建索引`等于`每次查询都要浪费一次建索引的时间`

    想想如果你的要定位的行在文件靠后的位置,因为每行长度不固定,没索引势必要遍历整个文件。

    我看不出不建索引有什么优势。也许你的意思是你这个查询只需要做一次?如果只做一次就直接遍历吧。
    ashfinal
        65
    ashfinal  
       2017-08-23 14:21:32 +08:00
    @realpg ultraedit 如果要搜索的话,还要遍历整个文件。这是不是意味着搜索的时候特别慢?
    realpg
        66
    realpg  
       2017-08-23 14:25:47 +08:00
    @ashfinal #65
    具体没试过啊 我是没那种在几十个 G 的文本文件里找一个东西的需求 你可以自己试试
    sampeng
        67
    sampeng  
       2017-08-23 14:29:15 +08:00
    从应用场景来说,如果只是达成这个目的。。我可能直接先把文件分成 n 个小文件。比如 1G 一个。。然后再算 seek 的目标在哪个文件里面。
    只是做而做,感觉没有啥意义。。再快也没什么卵用
    ashfinal
        68
    ashfinal  
       2017-08-23 14:39:21 +08:00
    @realpg 我没有 windows,没有 ultraedit,也没有大文件……
    billlee
        69
    billlee  
       2017-08-23 14:41:30 +08:00
    @Fishdrowned #6 如果是一块硬盘,并发只会更慢
    SlipStupig
        70
    SlipStupig  
       2017-08-23 17:27:12 +08:00
    elastic search
    rogerchen
        71
    rogerchen  
       2017-08-23 17:53:40 +08:00 via Android
    kv 数据库不就是为楼主而生。
    michael2016
        72
    michael2016  
       2017-08-23 17:55:31 +08:00
    楼主,抬出我的意大利炮。。。
    lybtongji
        73
    lybtongji  
       2017-08-23 18:15:00 +08:00
    倍增法
    ashfinal
        74
    ashfinal  
       2017-08-23 18:48:33 +08:00
    @vjnjc MacVim 打开 227.6 MB 的文件也就 1s 左右,可以尝试禁用插件、关闭高亮等法子试试。
    ![]( )

    @realpg 我知道了!搜索是不耗时的,但是统计匹配项绝壁卡爆(因为需要遍历)。期待有人实验下证实我的想法。
    chunk
        75
    chunk  
       2017-08-23 19:56:19 +08:00
    很多人关注点都在建索引上,但建索引的算法很依赖于数据的 pattern(比如如果是日志文件,每行的长度差不多)
    elvodn
        76
    elvodn  
       2017-08-23 20:14:10 +08:00
    让给文件那边直接给原生 int 数组二进制文件方便
    kotokz
        77
    kotokz  
       2017-08-23 20:21:04 +08:00   ❤️ 1
    比 grep 快的当然有
    the silver search, ag
    ripgrep, rg

    ripgrep 是 rust 写的,vsc 最近版本也集成了,蛮火
    kaiser1992
        78
    kaiser1992  
    OP
       2017-08-24 10:09:17 +08:00
    @ashfinal 搜索不耗时??
    ashfinal
        79
    ashfinal  
       2017-08-29 18:40:01 +08:00
    @kaiser1992 只搜索屏幕内容,而不是整个文件。

    耗时小到不计。
    kaiser1992
        80
    kaiser1992  
    OP
       2017-08-30 09:20:47 +08:00
    @ashfinal 你的 MacVim 读取文件是直接都读到内存了吧,你看看能否打开上 10G 的文件?
    ashfinal
        81
    ashfinal  
       2017-08-30 11:13:33 +08:00
    @kaiser1992 嗯 Vim 是默认读到内存的。不过我平时 200 MB 以上的文件都遇不到两个。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2730 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 54ms · UTC 12:34 · PVG 20:34 · LAX 05:34 · JFK 08:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.