V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 3181 days ago, the information mentioned may be changed or developed.
现有一个很大的文件(比如 40G 的文本)，假如我随机定位某一行，怎么样实现最快（时间和空间）？
希望 V 友们想什么说什么，畅所欲言
希望 V 友们想什么说什么，畅所欲言
Supplement 1 · Aug 23, 2017
看了各位 V 友们的回答，谢谢大家。
大家的看法大致总结如下：
1.采用 linux 自带的文本查询工具 grep 指令和 awk 指令来实现。但是这个需求不能借助系统的命令工具。
2.构建索引的思想，扫描一遍文本，将行数和换行符构建索引，这样构建完索引之后，搜索查询是快，可是前期扫面文件需要的时间不能不考虑。
现重新把题目再明确一下：
1.文本中每行的数据是不固定的，不能够直接计算偏移量来直接定位。
2.假定一个具体场景，假如文本中每行只存储长度不定的数字 Id(比如 8,9,10...位等)，现在我随机指定某行数，要实现将该行对应的数字 ID 读出来。
大家的看法大致总结如下：
1.采用 linux 自带的文本查询工具 grep 指令和 awk 指令来实现。但是这个需求不能借助系统的命令工具。
2.构建索引的思想，扫描一遍文本，将行数和换行符构建索引，这样构建完索引之后，搜索查询是快，可是前期扫面文件需要的时间不能不考虑。
现重新把题目再明确一下：
1.文本中每行的数据是不固定的，不能够直接计算偏移量来直接定位。
2.假定一个具体场景，假如文本中每行只存储长度不定的数字 Id(比如 8,9,10...位等)，现在我随机指定某行数，要实现将该行对应的数字 ID 读出来。
Supplement 2 · Aug 23, 2017
谢谢大家的回答，我还是没有找到良好的解决办法。
现实中大家的确不会遇到这么大的文件，由于目前正在做搜索这方面的工作，涉及到的数据量特别大，当然 40G 有点大的不合理，一般情况下是几个 G 的文本内容，上面说到文本内容只有数字的话，可否在数字特征规律上下功夫呢？
.....个人感觉建索引是挺好的...... 逃:)
现实中大家的确不会遇到这么大的文件，由于目前正在做搜索这方面的工作，涉及到的数据量特别大，当然 40G 有点大的不合理，一般情况下是几个 G 的文本内容，上面说到文本内容只有数字的话，可否在数字特征规律上下功夫呢？
.....个人感觉建索引是挺好的...... 逃:)
 |
1
ashfinal Aug 22, 2017
40 G …… 这，这
|
 |
2
15015613 Aug 22, 2017 via Android
查找内容的话，grep
输出特定行，sed |
 |
3
kaiser1992 OP @15015613 grep 是顺序查找太慢，sed 也需要遍历
|
 |
4
Fishdrowned Aug 22, 2017 via Android
要是打开没规律的文本文件，你倒是说什么算法不用遍历？判断行数难道不用先知道前面有几行？
|
 |
5
jfcherng Aug 22, 2017  1
|
|
6
Fishdrowned Aug 22, 2017 via Android
优化方法估计只能多核并行遍历了。如果文件内容不会变化，遍历完之后可以缓存结果
|
 |
7
chunk Aug 22, 2017
dd
|
 |
8
sofs Aug 22, 2017 via Android
40G 的文本我不敢去操作
|
 |
9
qian19876025 Aug 22, 2017
@Fishdrowned 除非大部分读进内存 不然你没法 并行
|
 |
10
sun1991 Aug 22, 2017
先扫描一遍, 获取所有行的 pos, 保存起来.
|
 |
11
reus Aug 22, 2017
加索引
|
|
12
Fishdrowned Aug 22, 2017 via Android
@qian19876025 当然可以并行。按文件大小设置几个断点，然后每个线程从断点处开始遍历，找到换行符就记录一下位置，并不需要多少内存。全部完成后汇总，每一行的位置都出来了
|
 |
13
FanWall Aug 22, 2017 via Android
@Fishdrowned 最坏的情况缓存大小是文件大小的四倍
|
|
14
Fishdrowned Aug 22, 2017 via Android
缓存大不用怕，因为缓存是有组织的，内存不够就放磁盘，快速查找不难实现。
|
 |
15
0ZXYDDu796nVCFxq Aug 22, 2017 via iPhone
只查找少数几次：调用 grep，如果你实现了一个比 grep 更快的算法，那牛逼大了
经常查找：扫一遍，建个索引存下来 |
 |
16
lululau Aug 22, 2017
扫描一遍文件，把每一个换行符的索引记录下来，然后 dd 就可以了，不知道 dd 就 man 2 lseek
|
 |
17
webster Aug 22, 2017
用 grep 找过 30G 的文件 感觉真的很科技 很快
|
 |
18
privil Aug 22, 2017
|
 |
19
gouchaoer Aug 22, 2017 via Android
ls 的回答都是什么啊，lz 需求是定位某一行
fseek 可以访问文件偏移量，但是行是以换行符确定的，你需要遍历整个文件 要以常数时间定位某一行的话自己建立一个索引就 ok 了，先遍历文件遇到换行符就记录这是第几行，以及当前 fseek 偏移量 |
|
20
kaiser1992 OP @gstqc 建索引需要时间，存索引需要的空间最后貌似比源文件都大了把
|
 |
21
EchoUtopia Aug 22, 2017 via iPhone
awk
|
 |
22
rrfeng Aug 22, 2017
随机定位是什么鬼？
你随机给个数字，我输出行号等于这个数字的行？ |
|
23
0ZXYDDu796nVCFxq Aug 22, 2017 via iPhone
@kaiser1992 索引表怎么可能比原文件大
你要建立的是行数和偏移量两个值 |
 |
24
ynyounuo Aug 22, 2017
Ctags
不过 40G ？？？这是什么文本啊 |
 |
25
am241 Aug 22, 2017 via Android
扫一遍，记录下每个换行符的位置，然后二分搜索就够了
|
|
26
qian19876025 Aug 23, 2017
@Fishdrowned 那你还是要把东西大部分读进内存啊 难不成你不用？ 难不成你知道硬盘中怎么存储的？ 不读进内存你来搞
|
|
27
qian19876025 Aug 23, 2017
当然如果你的数据是 线性排序 或者 hash 固定 没有冲突的 那是另外的话了
|
|
28
qian19876025 Aug 23, 2017
如果每行数据是 固定大小的 或者能直接算出偏移值的 那也可以直接取出
|
 |
29
watzds Aug 23, 2017 via Android
顺序读取文件似乎每秒几百兆，30g 遍历大概得几分钟吧。
还有个问题，30g 文件中间加一行会怎样？😁 什么需求需要单机存储 30g 大文件？可能一开始就不应该这么存 |
|
30
FanWall Aug 23, 2017 via Android
@gstqc #23 都不用想最坏情况了，假设一个字节一行，换行符是\n，40G 光记录偏移值就要 160G 了(UL 是装不下的)，如果再考虑全部空行…… 320G ？
@qian19876025 #26 我觉得他是对的，索引是有组织的，是可以计算的，只读需要的一小段就行了。 |
|
31
Fishdrowned Aug 23, 2017 via Android
@qian19876025 #26 大哥，我不知道你是怎么理解的，遍历的时候，读一小段文字进内存，获取到换行位置之后就可以释放了然后读下一段了啊，难道你要一直放在内存里？
|
|
32
Fishdrowned Aug 23, 2017 via Android
打个比方，楼主有一本一万页的书，想随机精确地定位到第几个段落。
我一个人数太慢，于是叫来 20 个人（多线 /进程），每人撕走 2000 页，让他们各自统计自己的 2000 页里面各有多少段。 然后我等这 20 个人数完了，汇总整理一下做个索引，我不就知道这本书有几段了？ 每个线程做的事情没有什么花巧，就是遍历，只不过是适合并行计算，把时间分摊了。 至于内存，每个人都不用把 2000 页背下来啊，他只要知道每个段落位置分布在哪里就可以了，内存不够就拿笔写下来。 |
 |
33
t6attack Aug 23, 2017
“随机定位某一行” ，， 究竟是 “随机定位一行”？还是 “定位某一行”？
前者其实简单多了，用 64 位文件指针，随便定位个位置，向前、向后找到换行符就是了。感觉实际应用中，需要的应该就是前者。 |
|
34
t6attack Aug 23, 2017
也不对。这样结果并不随机。内容多的行更容易被定位到。
|
 |
35
ufjfeng Aug 23, 2017 via iPhone
知道行号的话，awk 就行，性能不详
awk 'NR=n {print $0}' n 是行号 |
|
36
ufjfeng Aug 23, 2017 via iPhone
awk 'NR=n {print $0}' filename
楼上忘了写文件名 |
 |
37
linux40 Aug 23, 2017 via Android
40g 为什么是一个文件呢。。。
|
 |
38
libook Aug 23, 2017
定位某一行就是定位某一个换行符，和定位某一个字母 a 或定位某一个数字 1 是一样的，都需要遍历整个文件，除非是像数据库一样做索引优化。
个人以为 linux 提供的指令效率极高，如果还是满足不了需求的话建议想办法建起换行符的索引。 |
 |
39
wangyucn Aug 23, 2017
|
|
40
wangyucn Aug 23, 2017
索引例子：
行数（单位千) 文件偏移 1 456789 （第 1000 行的文件偏移） 2 1234567 （第 2000 行的文件偏移） 3 2345678 （第 2000 行的文件偏移） 4 |
|
41
wangyucn Aug 23, 2017
囧，正在编辑不小心发出去了。凑合看吧。 索引做成外挂式的，不需要改原文件。
|
 |
42
90safe Aug 23, 2017
grep 是个黑科技
|
 |
43
huangfs Aug 23, 2017
rg
|
|
44
kaiser1992 OP @wangyucn 谢谢，前期构建索引需要遍历字符位置，感觉太耗时间了
|
|
45
kaiser1992 OP @lululau 换行符都是\n 或者\r\n 相同符号如何构建索引?
|
|
46
kaiser1992 OP @lululau 我明白你意思了，你是要对每一行换行符的位置做一个索引
|
 |
47
Hozzz Aug 23, 2017
还不如将整个文件先拆成多个小文件，然后再并行查询（如果是构建索引，遇到频繁更新的文件，效率仍然不高）
|
|
48
kaiser1992 OP @Hozzz 不考虑并行的方式，拆分重写小文件，需要的时间也不少，还没有考虑之后查询的时间。
|
 |
49
mhycy Aug 23, 2017
楼上有人提到并行，但实际应用中可行性不大，因为数据是从磁盘顺序读取的。
构建索引只需要记录所有\r\n or \n 的偏移量，构建时间约等于读取 40G 文件所需的时间。 （如果 CPU 足够快的话） 如果 CPU 在判断字符过程中消耗过大（基本不可能，除非 IO 太快） 那么可考虑缓冲区读取多线程并行分析，但考虑到多线程开销，似乎还是单线程更靠谱。 注意：因为 IO 的限制，没有比这个更快的定位不定长数据行的办法。 |
 |
50
xou130 Aug 23, 2017 via Android
40G 这个大小该上 hadoop 了
|
|
51
qian19876025 Aug 23, 2017
@Fishdrowned 不管你怎么样你翻书还是串行的 除非读进内存你这就是延迟而已
|
 |
52
luoqeng Aug 23, 2017
|
 |
53
vjnjc Aug 23, 2017
借楼问一下中文件你们都是怎么操作的？
有一个 sql 文件，大概 100MB，我在 mac 下用 vim 打开都花了一分钟了。。。 |
|
54
Hozzz Aug 23, 2017
@kaiser1992 可以在存入文件之前就对数据进行拆分，或者用个额外的进程不停对该文件进行拆分
|
|
55
Hozzz Aug 23, 2017
@kaiser1992 另外 head 和 tail 命令不会遍历整个文件
|
|
56
Fishdrowned Aug 23, 2017 via Android
@qian19876025 #51 麻烦你了解一下磁盘寻址，我已经知道某行的偏移量在哪里了，找个 offset 还要串行？
|
|
57
Fishdrowned Aug 23, 2017 via Android
@kaiser1992 #44 这个时间（遍历整个文件）是必须付出的，没有捷径。
|
 |
58
realpg PRO |
 |
59
v2orz Aug 23, 2017
6 楼+16 楼应该已经可以解决问题了
|
 |
60
popok Aug 23, 2017
传说中的社工库吗
|
 |
61
shyling Aug 23, 2017
2333，先把它分成多个文件啊。。。例如 n 行一个文件。。。
|
 |
62
sola97 Aug 23, 2017 via Android
社工库的既视感
|
|
63
Fishdrowned Aug 23, 2017 via Android
其实并行只是理论上的优化方法，实际上 cpu 处理的速度应该是高于磁盘的吞吐量的（几百 MB/s，不考虑随机读的 iops 是因为这个可以规避）
|
|
64
wangyucn Aug 23, 2017
@kaiser1992 `不建索引`等于`每次查询都要浪费一次建索引的时间`
想想如果你的要定位的行在文件靠后的位置，因为每行长度不固定，没索引势必要遍历整个文件。 我看不出不建索引有什么优势。也许你的意思是你这个查询只需要做一次？如果只做一次就直接遍历吧。 |
 |
67
sampeng Aug 23, 2017
从应用场景来说，如果只是达成这个目的。。我可能直接先把文件分成 n 个小文件。比如 1G 一个。。然后再算 seek 的目标在哪个文件里面。
只是做而做，感觉没有啥意义。。再快也没什么卵用 |
 |
69
billlee Aug 23, 2017
@Fishdrowned #6 如果是一块硬盘，并发只会更慢
|
 |
70
SlipStupig Aug 23, 2017
elastic search
|
 |
71
rogerchen Aug 23, 2017 via Android
kv 数据库不就是为楼主而生。
|
 |
72
michael2016 Aug 23, 2017
楼主，抬出我的意大利炮。。。
|
 |
73
lybtongji Aug 23, 2017
倍增法
|
|
74
ashfinal Aug 23, 2017
|
) |
75
chunk Aug 23, 2017
很多人关注点都在建索引上,但建索引的算法很依赖于数据的 pattern(比如如果是日志文件,每行的长度差不多)
|
 |
76
elvodn Aug 23, 2017
让给文件那边直接给原生 int 数组二进制文件方便
|
 |
77
kotokz Aug 23, 2017 1
比 grep 快的当然有
the silver search, ag ripgrep, rg ripgrep 是 rust 写的，vsc 最近版本也集成了，蛮火 |
|
78
kaiser1992 OP @ashfinal 搜索不耗时？？
|
|
79
ashfinal Aug 29, 2017
|
|
80
kaiser1992 OP @ashfinal 你的 MacVim 读取文件是直接都读到内存了吧，你看看能否打开上 10G 的文件？
|
|
81
ashfinal Aug 30, 2017
@kaiser1992 嗯 Vim 是默认读到内存的。不过我平时 200 MB 以上的文件都遇不到两个。
|
Select Language