目前有 A B 两个文件
A 文件结构如下
aasdad11k1
dddasda113
oadap123ka
12321312aa
B 文件结构如下
kkooasda11
aasdad11k1
asdad11111
ooooo12312
asdada1312
AB 两个文件都是写\n 换行,每行都是以 字符+数字 组成,并且长度固定 现在想获取 A 里面的文件内容是否在 B 里面,如果在则输出这一行。
AB 两个文件大小都在 1000 万行
用 AWK 命令
awk 'NR==FNR{x[$0];next}{for(i in x)if($0~i)print}' a b > result
这个效率略低,目前代码如下
String b=null;
int i=0;
while ((str = bufferedReader.readLine()) != null){
b[i]=str;
i++;
}
while ((str = bufferedReader_a.readLine()) != null){
for (int m=0;m<b.length;m++){
if (str.equals(b[m])){
bw.write(str);
break;
}
}
}
bw.close();
fw.close();
速度太慢了. 在不考虑切分文件的情况下,有算法可以处理这类需求吗?
1
h4lbhg1G 2018-01-24 21:50:09 +08:00
嗯,我随口说说。对 B 建一个 trie 树,然后用 A 来查就好了。这长度固定,深度是固定的,效率应该很高。
|
2
ipwx 2018-01-24 21:50:52 +08:00
楼主你真的学过数据结构和算法么?
- - - - 上哈希表,妥妥的。 |
3
luban 2018-01-24 21:52:58 +08:00 via iPhone
这是思路,你得先对 b 文件排序,再使用查找的算法
1 千万,即使用快速排序也要很久,为啥不能拆分文件呢 其他思路本质也是类似,把 b 存到 nosql,redis,mongo 之类,再查找,当然存 mysql 也行,这里就是数据库实现了一些数据结构和算法,不用自己再写了 |
4
liuminghao233 2018-01-24 22:40:31 +08:00 via iPhone
2l 第四行
记得内存插满 |
5
georgetso 2018-01-24 22:43:52 +08:00
1 楼 trie 树 赞同
|
6
sundyli 2018-01-24 22:46:07 +08:00
trie 树 +1
|
7
crayygy 2018-01-24 23:04:26 +08:00
(10 byte + 2 byte) * 1 * 10^6
算起来也没多少...全放内存似乎也没啥大不了的 当然了我还是觉得用树比较合适 |
9
wweir 2018-01-25 06:56:34 +08:00 via Android
既然 hash 表不行,要不试试 hash 树?
|
10
hotea 2018-01-25 09:48:29 +08:00
布隆过滤器?
|
11
stephenpcg 2018-01-25 10:54:53 +08:00 2
既然楼主都考虑过 awk 了,我觉得很可能是一次性的任务,1000 万行也不大,也就百来兆的文件,可以试试:
comm -1 -2 <(sort a) <(sort b) 时间主要消耗在 sort 上面,我本地随机生成了两个文件 a、b,每个文件 1000 万行,每行长度 10 个字符,本地测试总开销 12s。时间比 awk 少 2 个数量级以上。 |
12
h4lbhg1G 2018-01-25 12:01:30 +08:00
@stephenpcg 1000 万等于 10 的 8 次方。每行 11 个字符. 一共有 1.1x10^9Bytes=1.1x10^9/1024/1024/1024GB=1.024GB,是不是少了个数量级。虽然排序是不错的方法就是了,而且如果用归并排序似乎更快。
|
14
stephenpcg 2018-01-25 12:48:30 +08:00
@h4lbhg1G 100 万约为 1M,1000 万即为 10M,每行 11 字节,即为 110MB。你前面说“等于 10 的 8 次方”,后面计算时变成了 "x10^9Bytes"。
|
15
h4lbhg1G 2018-01-25 12:57:06 +08:00
@stephenpcg 11x10^8 等于多少?
|
16
h4lbhg1G 2018-01-25 13:01:30 +08:00
@stephenpcg 好吧 我错了
|
17
laodao1990 2018-01-25 13:33:07 +08:00
关注一下。
大家解题思路别限制字符串长度呀,没准题主例子中的字符串就是随便写的,实际上要关联的是两个几十个 G 的日志文件。 |
18
enenaaa 2018-01-25 13:59:41 +08:00
如果只是判断 A 的文本是否存在 B 中。 那不用排序啊。
把 A 的所有行读出来, 放到哈希表或映射表中。 读 B 时判断是否在表中即可。 手动构建查找树,貌似太为难楼主了。 |
19
wwww961h 2018-01-26 01:40:20 +08:00 via iPhone
同三楼,我第一印象也是走数据库,不管是 nosql 还是 mysql,数据库就是用来处理数据的,从数据库拿出来用脚本运算绝对快,比你想啥数据结构都快,不过超过亿级之后数据库就基本慢得死了
|