在使用具有不同成本的谓词调用 allMatch 之前对 Java 流进行排序是否会带来任何好处？

Question

我已经实现了一个 Java 流管道，其中对一些元素进行排序并检查它们是否全部满足谓词。管道看起来像这样：

items.stream()
     .sorted(this::sortByType)
     .allMatch(this::isCompliant);

谓词的验证在成本上有所不同。有些元素只需要检查属性，对于其中一些元素，我也必须从数据库中获取可能的许多元素并评估它们。

因为我需要知道所有这些都是真的，所以知道至少有一个是假的，是等价的。如果我正确理解了 allMatch() 操作的 JavaDoc，那么一旦一个元素为 false，它就应该短路。

因此，为了潜在地提高执行速度，我对元素进行排序，以便首先执行所有非常简单的验证，并且只有当它们全部成功时，我才执行成本更高的验证。

至少我认为是这样的。然而，我的 IDE 告诉我，调用 allMatch() 之前进行排序是多余的，因为它不依赖于排序顺序。

我编写了一些测试，这些测试似乎表明在遍历管道时实际上考虑了排序顺序，但也许我的测试用例太小或者只是碰巧被正确调用。

所以我的问题是： allMatch() 是否考虑预先施加的排序顺序？还是它忽略了它？

Answer 1

从你的描述来看

谓词的验证在成本上有所不同。有些元素只需要检查属性，对于其中一些元素，我也必须从数据库中获取可能的许多元素并评估它们。

我创建了一个简单的测试用例。该类Waiter有一个int属性，用于定义排序顺序以及计算谓词所需的时间：

public class Waiter implements Comparable<Waiter> {
    private final int time;

    public Waiter(int time) {
        this.time = time;
    }

    public boolean isValid() {
        try {
            Thread.sleep(time);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        return time > 10;
    }

    @Override
    public int compareTo(Waiter o) {
        return Integer.compare(time, o.time);
    }
}

该类Sorter创建几个s 并输出未排序或已排序的服务员列表Waiter的时间：allMatch()

import java.util.List;

public class Sorter {
    public static void main(String[] args) {
        var data = List.of(
                new Waiter(500),
                new Waiter(500),
                new Waiter(500),
                new Waiter(500),
                new Waiter(1)
        );
        System.out.printf("Duration sorted: %d ms%n", time(() -> data.stream().sorted().allMatch(Waiter::isValid)));
        System.out.printf("Duration unsorted: %d ms%n", time(() -> data.stream().allMatch(Waiter::isValid)));
        System.out.printf("Duration sorted: %d ms%n", time(() -> data.stream().sorted().allMatch(Waiter::isValid)));
        System.out.printf("Duration unsorted: %d ms%n", time(() -> data.stream().allMatch(Waiter::isValid)));
    }

    private static long time(Runnable r) {
        long start = System.currentTimeMillis();
        r.run();
        return System.currentTimeMillis() - start;
    }
}

结果如预期：如果Waiterwhos 谓词计算为 false 是第一个（即数据已排序），则allMatch()计算速度会更快：

Duration sorted: 6 ms
Duration unsorted: 2021 ms
Duration sorted: 3 ms
Duration unsorted: 2030 ms

请注意，如果我将最后一个更改Waiter为也等待 500 毫秒，则未排序的变体总是更快（因为排序需要时间并且不会更改所有谓词匹配的情况下的输出）

请记住，这是一个非常简单的测试，可能会受到各种因素的影响：

• 这不是一个合适的微基准。没有热身，仅运行两次测试。经过适当的热身后，这些数字可能会有所不同。

• 排序本身需要时间。在这个简单的情况下，对数据进行排序的时间很短，但您的数据可能会有所不同

  • allMatch()仅当可以短路时排序才有效（即至少一个谓词失败）

  • 另一方面，对于所有谓词都返回 true 的情况，由于排序，您会受到性能损失

结论：

• 如果某些谓词失败，则对流进行排序会带来好处，并且排序的效果是将失败的谓词移动到已排序流的开头。

• 对于所有谓词都匹配的情况，排序会受到惩罚

您需要找出这两种情况中哪一种更能描述您的问题。