Java函数式编程中归约reduce()的使用教程

21-05-25 banq

归约Reduce流运算允许我们通过对序列中的元素重复应用合并操作,从而从元素序列中产生一个单一结果。其中参与者有三者:

  • 标识identity:代表一个元素,它是归约reduce运算的初始值,如果流为空,则为此默认结果。
  • Accumulator 累加器:具有两个参数的函数:归约reduce运算后的部分结果和流的下一个元素
  • Combiner 组合器:当归约是并行化或累加器参数的类型与累加器实现的类型不匹配时,用于合并combine归约操作的部分结果的函数

可以转为reduce的for-loop:

List<String> letters = Arrays.asList("a","bb","ccc");
boolean seen = false;
String acc = null;
for (String letter : letters) {
    if (!seen) {
        seen = true;
        acc = letter;
    } else {
        acc = acc.length() < letter.length() ? acc : letter;
    }
}

对应的reduce函数:

letters.stream()
       .reduce((partialString, element) -> {
           System.out.println(partialString + " " + element);
           return partialString.length() < element.length() ? partialString : element;
       }).get();

// output
a bb
a ccc

  • 这里partialString是identity标识,它保存reduce的初始值,也是stream是空的默认结果;
  • partialString后面是一个累加器,它会将使用partialString和Stream中一个元素实现运算获得结果;

当Stream并行执行时,Java运行时会将流拆分为多个子流。在这种情况下,我们需要使用一种函数将子流的结果合并为一个。 这就是组合器的作用。

List<Integer> ages = Arrays.asList(25, 30, 45, 28, 32);
int computedAges = ages.parallelStream().reduce(0, a, b -> a + b, Integer::sum);

上面Integer :: sum方法是组合器。

如果我们使用顺序流并且累加器参数的类型和其实现的类型匹配,则无需使用组合器。

 

使用并行流时,应确保reduce()或在流上执行的任何其他聚合累积操作是:

  • associative互换的:结果不受操作数顺序的影响

    • 无干扰:操作不会影响数据源

      • 无状态和确定性的:该操作没有状态,并且对于给定的输入产生相同的输出

我们应该满足所有这些条件,以防止出现不可预测的结果。

并行流比顺序流的性能要好得多,当我们需要使用大型流并执行昂贵的聚合操作时,并行化流是正确的方法。

 

看看下面是一个字符串合并的reduce不正确用法:

 public String concatenate(List<Character> chars) {
        return chars.stream()
                    .reduce(new StringBuilder(""), (acc, c) -> acc.append(c)).toString();
    }

上面reduce两个参数:identity标识参数、累积器accumulator参数。

注意:这里用法是不正确的,reduce对累加器有要求的,应该是可交换、无干扰和无状态的,由于这里identity标识new StringBuilder("")是可变的,这个初始值因为追加新的字符变化,因此在并行执行的情况下,结果将被破坏。

修复:

public static String concatenate(List<Character> chars) {
        return chars
                .stream()
                .reduce(new StringBuilder(),
                                StringBuilder::append,
                                StringBuilder::append).toString();
    }

它类似下面代码:

U result = identity;
for (T element : this stream)
     result = accumulator.apply(result, element)
return result;

上面做法性能不好!这样的实现将进行大量的字符串复制,并且运行时间的字符数将为O(n ^ 2)。一种更有效的方法是将结果累积到中StringBuilder,这是用于累积字符串的可变容器。我们可以像使用普通归约法一样使用相同的技术来并行化可变归约法。

可变归约运算称为 collect(),因为它将所需的结果收集到结果容器中Collection。

 

reduce与collect

与reduce方法(该方法在处理元素时总是会创建一个新值)不同,collect方法会修改或变异现有值。一个collect操作需要三个函数参数:

  • supplier供应商函数,用于构造结果容器的新实例;

    • 累加器功能,用于将输入元素合并到结果容器中;

      • 以及组合combiner功能,用于将一个结果容器中的内容合并到另一个结果容器中。

 <R> R collect(Supplier<R> supplier,
               BiConsumer<R, ? super T> accumulator,
               BiConsumer<R, R> combiner);

与reduce()一样,collect以这种抽象方式表示的好处是它直接适合于并行化:只要累加和组合函数满足适当的要求,我们就可以并行累加部分结果,然后将它们组合起来。例如,要将流中元素的String表示形式收集到中ArrayList,我们可以编写明显的顺序for-each形式:

ArrayList<String> strings = new ArrayList<>();
for (T element : stream) {                 
        strings.add(element.toString());
}

或者我们可以使用可并行化的收集形式:

ArrayList<String> strings = stream.collect(() -> new ArrayList<>(),
                              (c, e) -> c.add(e.toString()),
                               (c1, c2) -> c1.addAll(c2));

或者,将map操作从累加器函数中拉出,我们可以更简洁地表示为:

List<String> strings = stream.map(Object::toString)
               .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);

我们的供应商就是ArrayList constructor,累加器将字符串化的元素添加到ArrayList中 ,而addAll 合并器只是用来将字符串从一个容器复制到另一个容器中。

这个代码实际是一个Map/reduce模式。

 

reduce vs. fold

这两个函数之间的区别在于,fold()取一个初始值并将其用作第一步的累加值,而reduce()的第一步则将第一和第二个元素用作第一步的操作参数。kotlin代码:

val numbers = listOf(5, 2, 10, 4)

val sum = numbers.reduce { sum, element -> sum + element }
println(sum)
val sumDoubled = numbers.fold(0) { sum, element -> sum + element * 2 }
println(sumDoubled)

//val sumDoubledReduce = numbers.reduce { sum, element -> sum + element * 2 } //incorrect: the first element isn't doubled in the result
//println(sumDoubledReduce)

fold()用于计算加倍元素的总和。如果将相同的函数传递给reduce(),则它将返回另一个结果,因为它在第一步使用列表的第一个和第二个元素作为参数,因此第一个元素不会被加倍。

java中collect类似kotlin的fold。

 

网友启发观点:

reduce实际是累计sum或Accumulator!

是不是类似SQL中5个嵌套的JOINS和GROUP BY?

它实际是一直尾递tail-recursive功能!

1
猜你喜欢