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