V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
abcdxx
V2EX  ›  程序员

问个排序算法问题

  •  
  •   abcdxx · 2018-01-24 21:46:29 +08:00 · 2514 次点击
    这是一个创建于 2493 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    19 条回复    2018-01-26 01:40:20 +08:00
    h4lbhg1G
        1
    h4lbhg1G  
       2018-01-24 21:50:09 +08:00
    嗯,我随口说说。对 B 建一个 trie 树,然后用 A 来查就好了。这长度固定,深度是固定的,效率应该很高。
    ipwx
        2
    ipwx  
       2018-01-24 21:50:52 +08:00
    楼主你真的学过数据结构和算法么?
    - - - -

    上哈希表,妥妥的。
    luban
        3
    luban  
       2018-01-24 21:52:58 +08:00 via iPhone
    这是思路,你得先对 b 文件排序,再使用查找的算法
    1 千万,即使用快速排序也要很久,为啥不能拆分文件呢
    其他思路本质也是类似,把 b 存到 nosql,redis,mongo 之类,再查找,当然存 mysql 也行,这里就是数据库实现了一些数据结构和算法,不用自己再写了
    liuminghao233
        4
    liuminghao233  
       2018-01-24 22:40:31 +08:00 via iPhone
    2l 第四行

    记得内存插满
    georgetso
        5
    georgetso  
       2018-01-24 22:43:52 +08:00
    1 楼 trie 树 赞同
    sundyli
        6
    sundyli  
       2018-01-24 22:46:07 +08:00
    trie 树 +1
    crayygy
        7
    crayygy  
       2018-01-24 23:04:26 +08:00
    (10 byte + 2 byte) * 1 * 10^6

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

    当然了我还是觉得用树比较合适
    crayygy
        8
    crayygy  
       2018-01-24 23:05:24 +08:00
    @crayygy #7 sorry,我似乎算错了一个级数
    wweir
        9
    wweir  
       2018-01-25 06:56:34 +08:00 via Android
    既然 hash 表不行,要不试试 hash 树?
    hotea
        10
    hotea  
       2018-01-25 09:48:29 +08:00
    布隆过滤器?
    stephenpcg
        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 个数量级以上。
    h4lbhg1G
        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,是不是少了个数量级。虽然排序是不错的方法就是了,而且如果用归并排序似乎更快。
    h4lbhg1G
        13
    h4lbhg1G  
       2018-01-25 12:02:19 +08:00
    @h4lbhg1G 说错了,是可以节省空间。
    stephenpcg
        14
    stephenpcg  
       2018-01-25 12:48:30 +08:00
    @h4lbhg1G 100 万约为 1M,1000 万即为 10M,每行 11 字节,即为 110MB。你前面说“等于 10 的 8 次方”,后面计算时变成了 "x10^9Bytes"。
    h4lbhg1G
        15
    h4lbhg1G  
       2018-01-25 12:57:06 +08:00
    @stephenpcg 11x10^8 等于多少?
    h4lbhg1G
        16
    h4lbhg1G  
       2018-01-25 13:01:30 +08:00
    @stephenpcg 好吧 我错了
    laodao1990
        17
    laodao1990  
       2018-01-25 13:33:07 +08:00
    关注一下。
    大家解题思路别限制字符串长度呀,没准题主例子中的字符串就是随便写的,实际上要关联的是两个几十个 G 的日志文件。
    enenaaa
        18
    enenaaa  
       2018-01-25 13:59:41 +08:00
    如果只是判断 A 的文本是否存在 B 中。 那不用排序啊。
    把 A 的所有行读出来, 放到哈希表或映射表中。 读 B 时判断是否在表中即可。
    手动构建查找树,貌似太为难楼主了。
    wwww961h
        19
    wwww961h  
       2018-01-26 01:40:20 +08:00 via iPhone
    同三楼,我第一印象也是走数据库,不管是 nosql 还是 mysql,数据库就是用来处理数据的,从数据库拿出来用脚本运算绝对快,比你想啥数据结构都快,不过超过亿级之后数据库就基本慢得死了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5352 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 03:36 · PVG 11:36 · LAX 19:36 · JFK 22:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.