[小白问题] Java 中路径 String 的字典序排序 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
SakuraSa
V2EX    问与答

[小白问题] Java 中路径 String 的字典序排序

 
  •   SakuraSa 2017 年 11 月 16 日 3260 次点击
    这是一个创建于 2977 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近在用不太熟悉的 java 写点项目,有个需求需要把以“.”分隔的路径按照每个子路径的字典序排序,例如:

    python:

    arr = ["a.b.c", "a.b", "a.ab", "c"] sorted(arr, key=lambda r: r.split(".")) 

    输出: ['a.ab', 'a.b', 'a.b.c', 'c'] 然而我用 java 实现却有点麻烦,我的实现是:

    java:

    arr.stream().map(key -> Tuple2.apply(key, key.split("\\."))) .sorted((o1, o2) -> { String[] parts1 = o1._2(); String[] parts2 = o2._2(); int maxLength = Math.max(parts1.length, parts2.length); for (int i=0;i<maxLength;i++) { if (i>=parts1.length) { return -1; } else if(i>=parts2.length) { return 1; } int compareResult = parts1[i].compareTo(parts2[i]); if (compareResult != 0) { return compareResult; } } return 0; }).map(Tuple2::_1) .collect(Collectors.toList()); 

    不得不说这代码有点...丑

    所以请教各位 java 大神,这种逻辑有没有简洁的实现方法呢?

    11 条回复    2017-11-17 12:59:35 +08:00
    zjp
        1
    zjp  
       2017 年 11 月 16 日   1
    一样不优雅...https://gist.github.com/zunpiau/65a9fd03ac2d07da6d72abcc96eef1f3

    不知道"a.b.c" 和 "a.ba"应该怎么排序,不过在代码里改一下判断顺序就好了
    SakuraSa
        2
    SakuraSa  
    OP
       2017 年 11 月 16 日
    @zjp 这种写法有一点小小的问题:排序过程中每次比较都会做 split,一次排序可能做 2*n*log(n) 次的 split,感觉性能消耗有点多
    SoloCompany
        3
    SoloCompany  
       2017 年 11 月 16 日 via iPhone
    @SakuraSa 难道原文中的 python 代码不需要 split ?
    SakuraSa
        4
    SakuraSa  
    OP
       2017 年 11 月 16 日
    @SoloCompany 需要,但是 Python 中 split 只需要 n 次(虽说 n 次和 2*n*log(n)差别也不大啦)
    SoloCompany
        5
    SoloCompany  
       2017 年 11 月 16 日
    @SakuraSa 这仅仅是一个空间换时间的问题,n vs n*log(n) 的代价就是你需要缓存每个计算结果, 假如 java 是一门动态语言 (也就是说任意 object 都可以动态的增加一个 attachment 属性) 也一样可以这样干, 现在因为 object 不可以任意添加 attachment 所以类库没有提供这种 sortby map 的封装, 建议你可以尝试一下 kotlin, 不过即使提供了 sortby 封装, 一般也不一定会做这样的预求值优化的

    当然具体到本题案例, 因为 map 是可逆的, 可以先 map 成 slpit 排序完了再 map join 回来只是不是很有必要性
    SakuraSa
        6
    SakuraSa  
    OP
       2017 年 11 月 16 日
    @SoloCompany #5
    嗯,因为我在写的应用相对时间比较敏感,所以需要空间换时间
    不过主要的问题是,这个实现太不优雅了。
    明明 python 中只要一句就可以轻松实现的逻辑,我在 java 中实现却需要 20 行。
    我觉得可能是因为我对于 java 的实现不太熟悉,没有使用正确的姿势,所以来请教有没有更好的写法。
    SoloCompany
        7
    SoloCompany  
       2017 年 11 月 17 日
    @SakuraSa 这关系到两点:1. 数组不是值类型 List 才是所以 split 的结果不能直接用作 Comparable, 2. 没有 sortby 封装. 后者仅仅是一个库支持的问题写一个 sortby 方法并没有什么困难, 前者就不是这么好解决

    把原语组合起来大概就是 arr.sortedWith(compareBy(compareByArray, String::split))
    这是常见的做法, 因为基于 compare 而不是 comparable 所以也不可能预求值优化
    如果希望能预求值优化那么需要创造另外的原语如 arr.sortBy(x -> ComparableArray(x.split(“.”))

    这些类型转换的复杂性本来就是存在的只不过甜度比较高的语法糖可能会让你忽略了其存在而已
    SakuraSa
        8
    SakuraSa  
    OP
       2017 年 11 月 17 日
    @SoloCompany #7 所以说我需要实现:

    1. 带预求值优化的 sortBy
    2. 将 string[] 包装为 Comparable 的对象

    是么?
    SakuraSa
        9
    SakuraSa  
    OP
       2017 年 11 月 17 日
    SoloCompany
        10
    SoloCompany  
       2017 年 11 月 17 日
    @SakuraSa 差不多就是这样。不过我建议你最好做一下 benchmark,像这类的优化通常都是无关紧要的。你可以对比一下 kotlin 版本 https://try.kotlinlang.org/#/UserProjects/pccstv7712df4g3ibqatu457rs/fei6se6j97r7494cjaq5r0jkvh

    把 main 函数里面的 altSortedBy 改成 sortedBy 就是标准库实现的版本
    SakuraSa
        11
    SakuraSa  
    OP
       2017 年 11 月 17 日
    | Benchmark | Mode | Cnt | Score | Error | Units |
    | ----------------------- | ----------------- | ---- | ------ | ----- | ----- |
    | testGround.BenchMark.complexImpl | avgt | 20 | 182.190 | 3.762| ms/op |
    | testGround.BenchMark.earlyEvalSorting | avgt | 20 | 161.369 | 2.573| ms/op |
    | testGround.BenchMark.splitOnCompareTo | avgt | 20 | 85.232 | 0.640| ms/op |
    | testGround.BenchMark.splitSortJoin | avgt | 20 | 199.678 | 24.554| ms/op |


    https://gist.github.com/SakuraSa/e139f303e075cc0b1cd7df06b4bacb49
    关于     帮助文档     自助推广系统     博客     API     FAQ     Solana     2721 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 29ms UTC 03:44 PVG 11:44 LAX 19:44 JFK 22:44
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86