V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
SakuraSa
V2EX  ›  问与答

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

  •  
  •   SakuraSa · 2017-11-16 11:45:30 +08:00 · 2775 次点击
    这是一个创建于 2584 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近在用不太熟悉的 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 13:32:27 +08:00   ❤️ 1
    一样不优雅...https://gist.github.com/zunpiau/65a9fd03ac2d07da6d72abcc96eef1f3

    不知道"a.b.c" 和 "a.ba"应该怎么排序,不过在代码里改一下判断顺序就好了
    SakuraSa
        2
    SakuraSa  
    OP
       2017-11-16 16:02:02 +08:00
    @zjp 这种写法有一点小小的问题:排序过程中每次比较都会做 split,一次排序可能做 2*n*log(n) 次的 split,感觉性能消耗有点多
    SoloCompany
        3
    SoloCompany  
       2017-11-16 20:40:09 +08:00 via iPhone
    @SakuraSa 难道原文中的 python 代码不需要 split ?
    SakuraSa
        4
    SakuraSa  
    OP
       2017-11-16 21:46:12 +08:00
    @SoloCompany 需要,但是 Python 中 split 只需要 n 次(虽说 n 次和 2*n*log(n)差别也不大啦)
    SoloCompany
        5
    SoloCompany  
       2017-11-16 22:09:51 +08:00
    @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 23:19:25 +08:00
    @SoloCompany #5
    嗯,因为我在写的应用相对时间比较敏感,所以需要空间换时间
    不过主要的问题是,这个实现太不优雅了。
    明明 python 中只要一句就可以轻松实现的逻辑,我在 java 中实现却需要 20 行。
    我觉得可能是因为我对于 java 的实现不太熟悉,没有使用正确的姿势,所以来请教有没有更好的写法。
    SoloCompany
        7
    SoloCompany  
       2017-11-17 00:21:31 +08:00
    @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 02:20:04 +08:00
    @SoloCompany #7 所以说我需要实现:

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

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

    把 main 函数里面的 altSortedBy 改成 sortedBy 就是标准库实现的版本
    SakuraSa
        11
    SakuraSa  
    OP
       2017-11-17 12:59:35 +08:00
    | 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   ·   实用小工具   ·   2563 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 13:49 · PVG 21:49 · LAX 05:49 · JFK 08:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.