大文件定位某一行？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2661 天前的主题，其中的信息可能已经有所发展或是发生改变。

现有一个很大的文件(比如 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

2017-08-22 19:18:29 +08:00

40 G …… 这，这

15015613

2017-08-22 19:20:18 +08:00 via Android

查找内容的话，grep
输出特定行，sed

kaiser1992

2017-08-22 19:22:26 +08:00

@15015613 grep 是顺序查找太慢，sed 也需要遍历

Fishdrowned

2017-08-22 19:41:13 +08:00 via Android

要是打开没规律的文本文件，你倒是说什么算法不用遍历？判断行数难道不用先知道前面有几行？

jfcherng

2017-08-22 19:42:52 +08:00

https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

grep 其實用了很多黑科技的，速度不是一般快。

Fishdrowned

2017-08-22 19:47:20 +08:00 via Android

优化方法估计只能多核并行遍历了。如果文件内容不会变化，遍历完之后可以缓存结果

chunk

2017-08-22 19:50:19 +08:00

sofs

2017-08-22 19:51:57 +08:00 via Android

40G 的文本我不敢去操作

qian19876025

2017-08-22 20:32:19 +08:00

@Fishdrowned 除非大部分读进内存不然你没法并行

sun1991

2017-08-22 20:35:49 +08:00

先扫描一遍, 获取所有行的 pos, 保存起来.

reus

2017-08-22 20:38:33 +08:00

加索引

Fishdrowned

2017-08-22 20:42:04 +08:00 via Android

@qian19876025 当然可以并行。按文件大小设置几个断点，然后每个线程从断点处开始遍历，找到换行符就记录一下位置，并不需要多少内存。全部完成后汇总，每一行的位置都出来了

FanWall

2017-08-22 20:47:41 +08:00 via Android

@Fishdrowned 最坏的情况缓存大小是文件大小的四倍

Fishdrowned

2017-08-22 20:56:27 +08:00 via Android

缓存大不用怕，因为缓存是有组织的，内存不够就放磁盘，快速查找不难实现。

0ZXYDDu796nVCFxq

2017-08-22 20:58:38 +08:00 via iPhone

只查找少数几次：调用 grep，如果你实现了一个比 grep 更快的算法，那牛逼大了
经常查找：扫一遍，建个索引存下来

lululau

2017-08-22 21:45:53 +08:00

扫描一遍文件，把每一个换行符的索引记录下来，然后 dd 就可以了，不知道 dd 就 man 2 lseek

webster

2017-08-22 21:54:26 +08:00

用 grep 找过 30G 的文件感觉真的很科技很快

privil

2017-08-22 22:14:30 +08:00

用多核心加速 grep 试试看 http://www.vaikan.com/use-multiple-cpu-cores-with-your-linux-commands/

gouchaoer

2017-08-22 22:23:10 +08:00 via Android

ls 的回答都是什么啊，lz 需求是定位某一行
fseek 可以访问文件偏移量，但是行是以换行符确定的，你需要遍历整个文件

要以常数时间定位某一行的话自己建立一个索引就 ok 了，先遍历文件遇到换行符就记录这是第几行，以及当前 fseek 偏移量

kaiser1992

2017-08-22 22:29:33 +08:00

@gstqc 建索引需要时间，存索引需要的空间最后貌似比源文件都大了把

EchoUtopia

2017-08-22 22:31:24 +08:00 via iPhone

awk

rrfeng

2017-08-22 22:34:54 +08:00

随机定位是什么鬼？

你随机给个数字，我输出行号等于这个数字的行？

0ZXYDDu796nVCFxq

2017-08-22 22:47:53 +08:00 via iPhone

@kaiser1992 索引表怎么可能比原文件大
你要建立的是行数和偏移量两个值

ynyounuo

2017-08-22 23:17:18 +08:00

Ctags
不过 40G ？？？这是什么文本啊

am241

2017-08-22 23:28:24 +08:00 via Android

扫一遍，记录下每个换行符的位置，然后二分搜索就够了

qian19876025

2017-08-23 00:19:43 +08:00

@Fishdrowned 那你还是要把东西大部分读进内存啊难不成你不用？难不成你知道硬盘中怎么存储的？不读进内存你来搞

qian19876025

2017-08-23 00:23:16 +08:00

当然如果你的数据是线性排序或者 hash 固定没有冲突的那是另外的话了

qian19876025

2017-08-23 00:25:41 +08:00

如果每行数据是固定大小的或者能直接算出偏移值的那也可以直接取出

watzds

2017-08-23 00:28:15 +08:00 via Android

顺序读取文件似乎每秒几百兆，30g 遍历大概得几分钟吧。
还有个问题，30g 文件中间加一行会怎样？😁
什么需求需要单机存储 30g 大文件？可能一开始就不应该这么存

FanWall

2017-08-23 00:38:06 +08:00 via Android

@gstqc #23 都不用想最坏情况了，假设一个字节一行，换行符是\n，40G 光记录偏移值就要 160G 了(UL 是装不下的)，如果再考虑全部空行…… 320G ？

@qian19876025 #26 我觉得他是对的，索引是有组织的，是可以计算的，只读需要的一小段就行了。

Fishdrowned

2017-08-23 01:31:54 +08:00 via Android

@qian19876025 #26 大哥，我不知道你是怎么理解的，遍历的时候，读一小段文字进内存，获取到换行位置之后就可以释放了然后读下一段了啊，难道你要一直放在内存里？

Fishdrowned

2017-08-23 01:48:13 +08:00 via Android

打个比方，楼主有一本一万页的书，想随机精确地定位到第几个段落。

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

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

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

至于内存，每个人都不用把 2000 页背下来啊，他只要知道每个段落位置分布在哪里就可以了，内存不够就拿笔写下来。

t6attack

2017-08-23 02:48:02 +08:00

“随机定位某一行” ，，究竟是 “随机定位一行”？还是 “定位某一行”？
前者其实简单多了，用 64 位文件指针，随便定位个位置，向前、向后找到换行符就是了。感觉实际应用中，需要的应该就是前者。

t6attack

2017-08-23 02:51:10 +08:00

也不对。这样结果并不随机。内容多的行更容易被定位到。

ufjfeng

2017-08-23 04:54:11 +08:00 via iPhone

知道行号的话，awk 就行，性能不详

awk 'NR=n {print $0}'

n 是行号

ufjfeng

2017-08-23 04:55:02 +08:00 via iPhone

awk 'NR=n {print $0}' filename

楼上忘了写文件名

linux40

2017-08-23 07:15:24 +08:00 via Android

40g 为什么是一个文件呢。。。

libook

2017-08-23 08:29:30 +08:00

定位某一行就是定位某一个换行符，和定位某一个字母 a 或定位某一个数字 1 是一样的，都需要遍历整个文件，除非是像数据库一样做索引优化。
个人以为 linux 提供的指令效率极高，如果还是满足不了需求的话建议想办法建起换行符的索引。

wangyucn

2017-08-23 08:36:53 +08:00

@kaiser1992 建索引需要时间，存索引需要的空间最后貌似比源文件都大了把

不会，索引不一定是完全的。可以每隔 1000 行建一个索引。查找时先用索引定位到文件偏移，然后稍微做一点遍历。

wangyucn

2017-08-23 08:40:32 +08:00

索引例子：
行数（单位千) 文件偏移
1 456789 （第 1000 行的文件偏移）
2 1234567 （第 2000 行的文件偏移）
3 2345678 （第 2000 行的文件偏移）
4

wangyucn

2017-08-23 08:41:57 +08:00

囧，正在编辑不小心发出去了。凑合看吧。索引做成外挂式的，不需要改原文件。

90safe

2017-08-23 08:53:34 +08:00

grep 是个黑科技

huangfs

2017-08-23 09:14:46 +08:00

kaiser1992

2017-08-23 09:24:53 +08:00

@wangyucn 谢谢，前期构建索引需要遍历字符位置，感觉太耗时间了

kaiser1992

2017-08-23 09:29:38 +08:00

@lululau 换行符都是\n 或者\r\n 相同符号如何构建索引?

kaiser1992

2017-08-23 09:33:46 +08:00

@lululau 我明白你意思了，你是要对每一行换行符的位置做一个索引

Hozzz

2017-08-23 09:43:37 +08:00

还不如将整个文件先拆成多个小文件，然后再并行查询（如果是构建索引，遇到频繁更新的文件，效率仍然不高）

kaiser1992

2017-08-23 09:50:01 +08:00

@Hozzz 不考虑并行的方式，拆分重写小文件，需要的时间也不少，还没有考虑之后查询的时间。

mhycy

2017-08-23 09:54:18 +08:00

楼上有人提到并行，但实际应用中可行性不大，因为数据是从磁盘顺序读取的。

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

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

注意：因为 IO 的限制，没有比这个更快的定位不定长数据行的办法。