避免在 Java 8 stream reduce 方法中使用全局变量

Question

我正在尝试使用 Java 8 重写 Moore’s Voting Algorithm 的实现以查找数组中的众数。

Java 7 的实现是这样的：

public int findCandidate(int[] nums) {

    int maj_index = 0, count = 1;
    for(int i=1; i<nums.length;i++){
        if(count==0){
            count++;
            maj_index=i;
        }else if(nums[maj_index]==nums[i]){
            count++;
        } else {
            count--;
        }
    }
    return nums[maj_index];
}

我能想到的方法是使用stream reduce得到最终结果

public int findCandidate(int[] nums) {
    int count = 1;
    Arrays
            .asList(nums)
            .stream()
            .reduce(0, (result, cur) -> {
                if (count == 0) {
                    result = cur;
                    count++;
                } else if (result == cur){
                    count++;
                } else {
                    count --;
                }
            });
    return result;
}

但是这个方法有编译错误，而且也打破了函数式的纯粹主义，这种情况我遇到过很多次，请问在lambda表达式中如何处理全局变量最好。

Answer 1

所以就像我在评论中告诉你的那样，在你的 lambda 表达式中使用可变对象是不行的。但是在你的情况下，如果你真的想应用相同的算法，那将是困难的。

这是一个和你想要的一样的，如果没有找到多数，它 returns -1

public static int findCandidate(int ... nums) {
    Map<Integer, List<Integer>> map =
    Arrays.stream(nums)
          .boxed()
          .collect(Collectors.groupingBy(x -> x));
    int value = 
          map
          .entrySet().stream()
          .max((e1, e2) -> Integer.compare(e1.getValue().size(), e2.getValue().size()))
          .map(e -> e.getKey())
          .get();
    int result = map.get(value).size();
    return result > nums.length / 2 ? value : -1;
}

Answer 2

展示了一些非常好的流技术。 (+1) 从根本上说，我认为它使用了正确的方法。不过，可以对其进行一些小的改进。

第一个更改是使用 counting() 收集器来计算每个组中的项目，而不是将它们累积到列表中。由于我们正在寻找多数，我们需要的只是计数，而不是实际元素，我们避免了必须比较列表的长度。

第二个更改是过滤列表以查找计数占多数的组。根据定义，最多可以有一个，因此我们只需使用此谓词过滤映射条目，并使用 findAny 而不是 max.

终止流

第三个变化是拥有更符合其意图的功能return OptionalInt。 OptionalInt 要么包含多数值，要么在没有多数值时为空。这避免了必须使用可能实际出现在数据中的标记值，例如 -1。由于 findAny return 是 OptionalInt，我们完成了。

最后，我在几个地方依赖静态导入。这主要是样式问题，但我认为它稍微清理了代码。

这是我的变体：

static OptionalInt majority(int... nums) {
    Map<Integer, Long> map =
        Arrays.stream(nums)
              .boxed()
              .collect(groupingBy(x -> x, counting()));

    return map.entrySet().stream()
              .filter(e -> e.getValue() > nums.length / 2)
              .mapToInt(Entry::getKey)
              .findAny();
}

Answer 3

您的问题是 Java 流没有真正的 list fold operation。使用真正的折叠操作，将函数编写为左折叠并不太困难。例如，在 Haskell:

import Data.List (foldl')

-- A custom struct to represent the state of the fold.
data MooreState a = MooreState { candidate :: a, count :: !Int }

findCandidate :: Eq a => [a] -> Maybe a
findCandidate (first:rest) = Just result
    where 
      Moore result _ = foldl' combiner (MooreState first 1) rest                       

      combiner :: Eq a => MooreState a -> a -> MooreState a
      combiner (Moore candidate count) current
          | count == 0           = MooreState current 1
          | candidate == current = MooreState candidate (count + 1)
          | otherwise            = MooreState candidate (count - 1)

-- The empty list has no candidates.
findCandidate [] = Nothing

Java 的 reduce() 方法最接近真正的左折叠，但如果您查看 the Javadoc for the reduce() method that you're using，您会注意到它说：

它"is not constrained to execute sequentially";
要求累加函数关联.

这个文档真的很难解释，但我的阅读方式是这样的。即使它可能会乱序处理元素：

如果你的累加函数是关联的那么它保证产生与顺序处理流相同的结果;
如果您的累加函数不是关联的，那么它可能会产生与简单顺序过程不同的结果。

为什么这很重要？好吧，首先，您正在改变外部变量这一事实意味着您使用 count 的方式被破坏了。据您所知，流的元素 #7 可能会在元素 #5 之前处理。

更隐蔽的是，上面 Haskell 版本中的 combine 操作结合了不同类型的输入（Moore a 和 a），但是 Java您使用的 reduce 方法基于 BinaryOperator<T>，它结合了两个相同类型的对象。有 another overload of reduce that uses a BiFunction<U, T, U>，但这需要您提供 BinaryOperator<U> combiner 及其 U identity。这是因为 Java 的 reduce 方法被设计成可以：

将输入流拆分为连续的块；
并行处理多个块；
相邻块的结果在完成时按顺序合并。

因此，关联性和身份要求是为了保证此并行处理产生与顺序处理相同的结果。但这意味着虽然算法有一个简单的功能实现，但没有直接的方法来用 Java 的 Stream 类型编写它。（有一种非直截了当的方法，但这会带来一些魔力，这将 (a) 非常复杂并且 (b) 在 Java 中非常慢。）

所以我个人会接受 Java 不是一种很棒的函数式编程语言，不要管它有多好，而是按原样使用命令式版本。但是，如果出于某种奇怪的原因，我真的坚持在功能上这样做，我会选择像 jOOλ which provides true left folds in Java 这样的库。然后你可以像 Haskell 解决方案（未经测试的伪代码）一样做：

import org.jooq.lambda.Seq;
import org.jooq.lambda.tuple.Tuple2;

class MooreState<A> {
    private final A candidate;
    private final int count;
    // ...constructors and getters...
}

public static Optional<A> findCandidate(Seq<A> elements) {
    Tuple2<Optional<A>, Seq<A>> split = elements.splitAtHead();
    return split.v1().map(first -> {
        Seq<A> rest = split.v2();
        return rest.foldLeft(
            new MooreState<>(first, 1),
            (state, current) -> {
                if (state.getCount() == 0) {
                    return new MooreState<>(current, 1);
                } else if (state.getCandidate().equals(current) {
                    return new MooreState<>(state.getCandidate(),
                                            state.getCount() + 1);
                } else {
                    return new MooreState<>(state.getCandidate(),
                                            state.getCount() - 1);
                }
            }
        );
    });
}

...这可能慢得可怕。

Answer 4

@Stuart Marks 写了简洁的代码。但是它仍然可以通过 AbacusUtil

来简化

Stream.from(nums).groupBy(Function.identity(), Collectors.counting())
     .findAny(e -> e.getValue() > nums.length / 2)

披露：我是 AbacusUtil 的开发者。

避免在 Java 8 stream reduce 方法中使用全局变量

Avoid using global variable in Java 8 stream reduce method

java

algorithm

reduce

functional-programming

java-8