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

[SakuraSa]

最近在用不太熟悉的 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 大神，这种逻辑有没有简洁的实现方法呢？

[zjp]

一样不优雅...https://gist.github.com/zunpiau/65a9fd03ac2d07da6d72abcc96eef1f3

不知道"a.b.c" 和 "a.ba"应该怎么排序，不过在代码里改一下判断顺序就好了

[SakuraSa]

@zjp 这种写法有一点小小的问题：排序过程中每次比较都会做 split，一次排序可能做 2*n*log(n) 次的 split，感觉性能消耗有点多

[SoloCompany]

@SakuraSa 难道原文中的 python 代码不需要 split ？

[SakuraSa]

@SoloCompany 需要，但是 Python 中 split 只需要 n 次（虽说 n 次和 2*n*log(n)差别也不大啦）

[SoloCompany]

@SakuraSa 这仅仅是一个空间换时间的问题，n vs n*log(n) 的代价就是你需要缓存每个计算结果, 假如 java 是一门动态语言 (也就是说任意 object 都可以动态的增加一个 attachment 属性) 也一样可以这样干, 现在因为 object 不可以任意添加 attachment 所以类库没有提供这种 sortby map 的封装, 建议你可以尝试一下 kotlin, 不过即使提供了 sortby 封装, 一般也不一定会做这样的预求值优化的

当然具体到本题案例, 因为 map 是可逆的, 可以先 map 成 slpit 排序完了再 map join 回来只是不是很有必要性

[SakuraSa]

@SoloCompany #5
嗯，因为我在写的应用相对时间比较敏感，所以需要空间换时间
不过主要的问题是，这个实现太不优雅了。
明明 python 中只要一句就可以轻松实现的逻辑，我在 java 中实现却需要 20 行。
我觉得可能是因为我对于 java 的实现不太熟悉，没有使用正确的姿势，所以来请教有没有更好的写法。

[SoloCompany]

@SakuraSa 这关系到两点:1. 数组不是值类型 List 才是所以 split 的结果不能直接用作 Comparable, 2. 没有 sortby 封装. 后者仅仅是一个库支持的问题写一个 sortby 方法并没有什么困难, 前者就不是这么好解决

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

这些类型转换的复杂性本来就是存在的只不过甜度比较高的语法糖可能会让你忽略了其存在而已

[SakuraSa]

@SoloCompany #7 所以说我需要实现：

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

是么？

[SakuraSa]

@SoloCompany #7 是类似与这样的实现么？
https://gist.github.com/anonymous/13511df6b921cda56637cc3b29e50e9c

[SoloCompany]

@SakuraSa 差不多就是这样。不过我建议你最好做一下 benchmark，像这类的优化通常都是无关紧要的。你可以对比一下 kotlin 版本 https://try.kotlinlang.org/#/UserProjects/pccstv7712df4g3ibqatu457rs/fei6se6j97r7494cjaq5r0jkvh

把 main 函数里面的 altSortedBy 改成 sortedBy 就是标准库实现的版本

[SakuraSa]

| 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