Java Streams:如何做一个有效的"独特和排序"？

Question

让我们假设我有一个Stream<T>并且想要只获得不同的元素并进行排序.

天真的方法是做到以下几点:

Stream.of(...)
    .sorted()
    .distinct()

或者,也许相反:

Stream.of(...)
    .distinct()
    .sorted()

由于JDK的源代码无法实现这两者的实现,我只是想知道可能的内存消耗和性能影响.

或者编写我自己的过滤器会更有效率如下？

Stream.of(...)
    .sorted()
    .filter(noAdjacentDuplicatesFilter())

public static Predicate<Object> noAdjacentDuplicatesFilter() {
    final Object[] previousValue = {new Object()};

    return value -> {
        final boolean takeValue = !Objects.equals(previousValue[0], value);
        previousValue[0] = value;
        return takeValue;
    };
}

Answer 1

当您distinct()在之后链接操作时sorted(),实现将利用数据的排序性质并避免构建内部HashSet,这可以通过以下程序演示

public class DistinctAndSort {
    static int COMPARE, EQUALS, HASHCODE;
    static class Tracker implements Comparable<Tracker> {
        static int SERIAL;
        int id;
        Tracker() {
            id=SERIAL++/2;
        }
        public int compareTo(Tracker o) {
            COMPARE++;
            return Integer.compare(id, o.id);
        }
        public int hashCode() {
            HASHCODE++;
            return id;
        }
        public boolean equals(Object obj) {
            EQUALS++;
            return super.equals(obj);
        }
    }
    public static void main(String[] args) {
        System.out.println("adjacent sorted() and distinct()");
        Stream.generate(Tracker::new).limit(100)
              .sorted().distinct()
              .forEachOrdered(o -> {});
        System.out.printf("compareTo: %d, EQUALS: %d, HASHCODE: %d%n",
                          COMPARE, EQUALS, HASHCODE);
        COMPARE=EQUALS=HASHCODE=0;
        System.out.println("now with intermediate operation");
        Stream.generate(Tracker::new).limit(100)
            .sorted().map(x -> x).distinct()
            .forEachOrdered(o -> {});
        System.out.printf("compareTo: %d, EQUALS: %d, HASHCODE: %d%n",
                          COMPARE, EQUALS, HASHCODE);
    }
}

这将打印

adjacent sorted() and distinct()
compareTo: 99, EQUALS: 99, HASHCODE: 0
now with intermediate operation
compareTo: 99, EQUALS: 100, HASHCODE: 200

简单的中间操作map(x -> x)不能被Stream实现识别,因此,必须假设元素可能不会根据映射函数的结果进行排序.

没有保证会发生这种优化,但是,假设Stream实现的开发人员不会删除该优化甚至尝试添加更多优化是合理的,因此滚动您自己的实现将阻止您的代码受益于未来的优化.

此外,您创建的是"有状态谓词",强烈建议不要这样做,当然,在与并行流一起使用时会中断.

如果您不信任Stream API来足够有效地执行此操作,那么最好在没有Stream API的情况下实现此特定操作.