这是一个创建于 2525 天前的主题，其中的信息可能已经有所发展或是发生改变。
目前有 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，数据库就是用来处理数据的，从数据库拿出来用脚本运算绝对快，比你想啥数据结构都快，不过超过亿级之后数据库就基本慢得死了
|
Select Language