这是一个创建于 2995 天前的主题，其中的信息可能已经有所发展或是发生改变。
目前有 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 年 1 月 24 日 嗯，我随口说说。对 B 建一个 trie 树，然后用 A 来查就好了。这长度固定，深度是固定的，效率应该很高。 |
 | 2 ipwx 2018 年 1 月 24 日 楼主你真的学过数据结构和算法么？ - - - - 上哈希表，妥妥的。 |
 | 3 luban 2018 年 1 月 24 日 via iPhone 这是思路，你得先对 b 文件排序，再使用查找的算法 1 千万，即使用快速排序也要很久，为啥不能拆分文件呢 其他思路本质也是类似，把 b 存到 nosql，redis，mongo 之类，再查找，当然存 mysql 也行，这里就是数据库实现了一些数据结构和算法，不用自己再写了 |
 | 4 liuminghao233 2018 年 1 月 24 日 via iPhone 2l 第四行 记得内存插满 |
 | 5 georgetso 2018 年 1 月 24 日 1 楼 trie 树 赞同 |
 | 6 sundyli 2018 年 1 月 24 日 trie 树 +1 |
 | 7 crayygy 2018 年 1 月 24 日 (10 byte + 2 byte) * 1 * 10^6 算起来也没多少...全放内存似乎也没啥大不了的 当然了我还是觉得用树比较合适 |
 | 9 wweir 2018 年 1 月 25 日 via Android 既然 hash 表不行，要不试试 hash 树？ |
 | 10 hotea 2018 年 1 月 25 日 布隆过滤器？ |
 | 11 stephenpcg 2018 年 1 月 25 日  2 既然楼主都考虑过 awk 了，我觉得很可能是一次性的任务，1000 万行也不大，也就百来兆的文件，可以试试： comm -1 -2 <(sort a) <(sort b) 时间主要消耗在 sort 上面，我本地随机生成了两个文件 a、b，每个文件 1000 万行，每行长度 10 个字符，本地测试总开销 12s。时间比 awk 少 2 个数量级以上。 |
| 12 h4lbhg1G 2018 年 1 月 25 日 @stephenpcg 1000 万等于 10 的 8 次方。每行 11 个字符. 一共有 1.1x10^9Bytes=1.1x10^9/1024/1024/1024GB=1.024GB，是不是少了个数量级。虽然排序是不错的方法就是了，而且如果用归并排序似乎更快。 |
| 14 stephenpcg 2018 年 1 月 25 日 @h4lbhg1G 100 万约为 1M，1000 万即为 10M，每行 11 字节，即为 110MB。你前面说“等于 10 的 8 次方”，后面计算时变成了 "x10^9Bytes"。 |
| 15 h4lbhg1G 2018 年 1 月 25 日 @stephenpcg 11x10^8 等于多少？ |
| 16 h4lbhg1G 2018 年 1 月 25 日 @stephenpcg 好吧 我错了 |
 | 17 laodao1990 2018 年 1 月 25 日 关注一下。 大家解题思路别限制字符串长度呀，没准题主例子中的字符串就是随便写的，实际上要关联的是两个几十个 G 的日志文件。 |
 | 18 enenaaa 2018 年 1 月 25 日 如果只是判断 A 的文本是否存在 B 中。 那不用排序啊。 把 A 的所有行读出来， 放到哈希表或映射表中。 读 B 时判断是否在表中即可。 手动构建查找树，貌似太为难楼主了。 |
 | 19 wwww961h 2018 年 1 月 26 日 via iPhone 同三楼，我第一印象也是走数据库，不管是 nosql 还是 mysql，数据库就是用来处理数据的，从数据库拿出来用脚本运算绝对快，比你想啥数据结构都快，不过超过亿级之后数据库就基本慢得死了 |
Select Language