performance - 使用 Java 8 查找连续子列表的负和

Question

我正在尝试优化以下代码:

private final static class SubarrayProcessorNegativeSumStrategy 
    implements SubarrayProcessorStrategy {
    @Override public Integer apply(Integer[] array) {
        final List<Integer> numbers = Arrays.asList(array);
        return (int) IntStream.range(0, numbers.size())
            .map(index -> findNegativeSums(numbers, index)).sum();
    } 
    private Integer findNegativeSums(final List<Integer> numbers, 
                                     final Integer startIndex) {
    final Integer numbersSize = numbers.size();
    if (startIndex < numbersSize) {
        return (int) IntStream.range(startIndex, numbers.size())
        .map(newIndex -> numbers.subList(startIndex, newIndex + 1)
        .stream().mapToInt(x -> x).sum())
        .filter(sum -> sum < 0).count();
    } else {
        return 0;
    }
}

我想避免为原始列表的每个元素从 startIndex 迭代到 newIndex + 1

numbers.subList(startIndex, newIndex + 1).stream().mapToInt(x -> x).sum()

您对我如何实现这一点有什么建议吗？或者您是否可以提供任何改进以获得相同的结果？

谢谢

问候，

Answer 1

如果你想通过Stream API来实现，就没有必要走List API的弯路了。此外，如果您执行单个 flatMap 流操作，则 «元素计数总和» 是所有元素的总数:

private final static class SubarrayProcessorNegativeSumStrategy
    implements SubarrayProcessorStrategy {
    @Override public Integer apply(Integer[] array) {
        return (int)IntStream.rangeClosed(0, array.length)
            .flatMap(index -> IntStream.range(0, index)
                .map(newIndex -> Arrays.stream(array,newIndex,index).mapToInt(x->x).sum())
                .filter(sum -> sum < 0))
            .count();
    }
}

这仍然具有与嵌套迭代相同的时间复杂度。如果您想优化执行时间，有状态操作更适合该任务，这不是 Stream API 的好用例。使用普通循环很简单:

private final static class SubarrayProcessorNegativeSumStrategy 
    implements SubarrayProcessorStrategy {
    @Override public Integer apply(Integer[] array) {
        int count=0;
        for(int index = 0; index < array.length; index++) {
            for(int newIndex = index, currSum = 0; newIndex < array.length; newIndex++) {
                currSum += array[newIndex];
                if(currSum < 0) count++;
            }
        }
        return count;
    }
}