问个排序算法问题

[abcdxx]

目前有 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();

速度太慢了. 在不考虑切分文件的情况下,有算法可以处理这类需求吗？

[h4lbhg1G]

嗯，我随口说说。对 B 建一个 trie 树，然后用 A 来查就好了。这长度固定，深度是固定的，效率应该很高。

[ipwx]

楼主你真的学过数据结构和算法么？
- - - -

上哈希表，妥妥的。

[luban]

这是思路，你得先对 b 文件排序，再使用查找的算法
1 千万，即使用快速排序也要很久，为啥不能拆分文件呢
其他思路本质也是类似，把 b 存到 nosql，redis，mongo 之类，再查找，当然存 mysql 也行，这里就是数据库实现了一些数据结构和算法，不用自己再写了

[liuminghao233]

2l 第四行

记得内存插满

[georgetso]

1 楼 trie 树 赞同

[sundyli]

trie 树 +1

[crayygy]

(10 byte + 2 byte) * 1 * 10^6

算起来也没多少...全放内存似乎也没啥大不了的

当然了我还是觉得用树比较合适

[crayygy]

@crayygy #7 sorry，我似乎算错了一个级数

[wweir]

既然 hash 表不行，要不试试 hash 树？

[hotea]

布隆过滤器？

[stephenpcg]

既然楼主都考虑过 awk 了，我觉得很可能是一次性的任务，1000 万行也不大，也就百来兆的文件，可以试试：

comm -1 -2 <(sort a) <(sort b)

时间主要消耗在 sort 上面，我本地随机生成了两个文件 a、b，每个文件 1000 万行，每行长度 10 个字符，本地测试总开销 12s。时间比 awk 少 2 个数量级以上。

[h4lbhg1G]

@stephenpcg 1000 万等于 10 的 8 次方。每行 11 个字符. 一共有 1.1x10^9Bytes=1.1x10^9/1024/1024/1024GB=1.024GB，是不是少了个数量级。虽然排序是不错的方法就是了，而且如果用归并排序似乎更快。

[h4lbhg1G]

@h4lbhg1G 说错了，是可以节省空间。

[stephenpcg]

@h4lbhg1G 100 万约为 1M，1000 万即为 10M，每行 11 字节，即为 110MB。你前面说“等于 10 的 8 次方”，后面计算时变成了 "x10^9Bytes"。

[h4lbhg1G]

@stephenpcg 11x10^8 等于多少？

[h4lbhg1G]

@stephenpcg 好吧 我错了

[laodao1990]

关注一下。
大家解题思路别限制字符串长度呀，没准题主例子中的字符串就是随便写的，实际上要关联的是两个几十个 G 的日志文件。

[enenaaa]

如果只是判断 A 的文本是否存在 B 中。 那不用排序啊。
把 A 的所有行读出来， 放到哈希表或映射表中。 读 B 时判断是否在表中即可。
手动构建查找树，貌似太为难楼主了。

[wwww961h]

同三楼，我第一印象也是走数据库，不管是 nosql 还是 mysql，数据库就是用来处理数据的，从数据库拿出来用脚本运算绝对快，比你想啥数据结构都快，不过超过亿级之后数据库就基本慢得死了