functional-programming - Java 8函数样式以索引进行迭代

Question

我已经练习Java 8流和功能样式已有一段时间了。
有时我尝试仅使用流来解决一些编程难题。
在这段时间里，我发现了一类任务，我不知道如何用流来解决，只能用经典方法解决。

此类任务的一个示例是:
给定一个数字数组，找到该元素的索引，该索引将使该数组的左半部分之和小于零。
例如数组[1, 2, 3, -1, 3, -10, 9]的答案将是5
我的第一个想法是使用IntStream.generate(0, arr.length)...，但后来我不知道如何累积值并同时知道索引。

所以问题是:

是否有可能以某种方式在流上累积值，然后有条件退出？

那么并行执行又是什么？它不适合在需要知道元素顺序的地方找到索引的问题。

Answer 1

我怀疑您的任务是否非常适合流。您正在寻找的是典型的左扫描操作，它本质上是顺序操作。

例如，想象一下管道中的以下元素:[1, 2, -4, 5]。并行执行可以将其分为两个子部分，即[1, 2]和[-4, 5]。那你要怎么处理他们呢？您不能独立地对它们进行求和，因为它将产生[3]和[1]，然后您就失去了1 + 2 - 4 < 0受到尊重的事实。

因此，即使您编写了一个跟踪索引和总和的收集器，它也无法并行运行(我怀疑您甚至可以从中受益)，但是您可以想象这样的收集器可以顺序使用:

public static Collector<Integer, ?, Integer> indexSumLeft(int limit) {
        return Collector.of(
                () -> new int[]{-1, 0, 0},
                (arr, elem) -> {
                    if(arr[2] == 0) {
                        arr[1] += elem;
                        arr[0]++;
                    }
                    if(arr[1] < limit) {
                        arr[2] = 1;
                    }

                },
                (arr1, arr2) -> {throw new UnsupportedOperationException("Cannot run in parallel");},
                arr -> arr[0]

        );
    }

和一个简单的用法:

int index = IntStream.of(arr).boxed().collect(indexSumLeft(0));

这仍然会遍历管道的所有元素，因此效率不是很高。

如果数据源是数组，您也可以考虑使用 Arrays.parallelPrefix。只需计算其上的部分和，然后使用流查找总和低于限制的第一个索引。

Arrays.parallelPrefix(arr, Integer::sum);
int index = IntStream.range(0, arr.length)
                     .filter(i -> arr[i] < limit)
                     .findFirst()
                     .orElse(-1);

这里也计算了所有的部分和(但并行)。

简而言之，我将使用一个简单的for循环。