使用 Java Stream API，查找变量的最高值，以及对变量所做的更改的流

背景/场景

假设我们有一个不可变的对象，名为Transaction, where transaction.getAction()会返回一个TransactionAction enum这可以是DEPOSIT or WITHDRAW, and transaction.getAmount()会返回一个Integer其中指定存款或取款的金额。

enum TransactionAction {
    WITHDRAW,
    DEPOSIT
}

public class Transaction {

    private final TransactionAction action;
    private final int amount;

    public Transaction(TransactionAction action, int amount) {
        this.action = action;
        this.amount = amount;
    }

    public TransactionAction getAction() {
        return action;
    }

    public int getAmount() {
        return amount;
    }

}

Question

我们现在有一个Stream<Transaction>这是一条充满了Transaction那可以是DEPOSIT or WITHDRAW。我们可以想象这个Stream<Transaction> as a 交易历史 of 一个特定的银行帐户.

我想要实现的是获得最高余额该帐户曾经取得过最有效率的方式（因此使用 Stream API）。

Example

鲍勃的交易历史是：

// balance start at 0
[DEPOSIT]   1200        // balance: 1200
[DEPOSIT]   500         // balance: 1700
[WITHDRAW]  700         // balance: 1000
[DEPOSIT]   300         // balance: 1300
[WITHDRAW]  800         // balance: 500
[WITHDRAW]  500         // balance: 0

Bob 的最高余额是1700.

您需要的是找到累积和的最大值。在伪代码中，这将类似于：

transactions = [1200, 500, -700, 300, -800, -500]
csum = cumulativeSum(transactions) // should be [1200,1700,1000,1300,500,0]
max(csum) // should be 1700

势在必行的方式：

传统的 for 循环非常适合这种情况。它应该相当容易编写，并且可能是时间和空间上最有效的替代方案。它不需要多次迭代，也不需要额外的列表。

int max = 0;
int csum = 0;
for (Transaction t: transactions) {
    int amount = (t.getAction() == TransactionAction.WITHDRAW ? -1 : 1) * t.getAmount();
    csum += amount;
    if (csum > max) max = csum;
}

深入探讨功能：

流是一种函数式编程概念，因此它们没有副作用，并且非常适合无状态操作。保持累积状态被认为是一种副作用，然后我们必须讨论 Monad 来控制这些副作用……我们不想走那条路。

Java 不是一种函数式语言（尽管允许函数式风格），因此不太关心纯度。您可以简单地在流外部有一个控制变量来跟踪当前的外部状态map or reduce运营。但这也将放弃 Stream 的一切用途。

那么我们来看看Java的有经验的小伙伴们在这件事情上是怎么做的呢？在纯 Haskell 中，累积和可以通过 Scan Left 操作来实现：

λ> scanl1 (+) [1200, 500, -700, 300, -800, -500] 
[1200,1700,1000,1300,500,0]

找到最大值就像这样简单：

λ> maximum ( scanl1 (+) [1200, 500, -700, 300, -800, -500] )
1700

Java Streams 解决方案：

Java 没有这种表达左扫描的惯用方式，但是您可以使用以下命令获得类似的结果collect.

transactions.stream()
    .map(t -> (t.getAction() == TransactionAction.WITHDRAW ? -1 : 1) * t.getAmount())
    .collect(ArrayList<Integer>::new, (csum, amount) -> 
        csum.add(csum.size() > 0 ? csum.get(csum.size() - 1) + amount : amount), 
        ArrayList::addAll)
    .stream()
    .max(Integer::compareTo);
// returns Optional[1700]

EDIT:正如评论中正确指出的那样，该累加器函数不具有关联性，如果尝试使用则会出现问题parallelStream代替stream.

这可以进一步简化。例如，如果您使用乘数丰富 TransactionAction 枚举（-1 表示WITHDRAW和 1 为DEPOSIT), then map可以替换为：

.map(t -> t.getAction().getMultiplier() * t.getAmount())

编辑：另一种方法：并行前缀和

从 Java 8 开始，数组提供了parallelPrefix可以使用如下操作：

Integer[] amounts = transactions.stream()
    .map(t -> (t.getAction() == TransactionAction.WITHDRAW ? -1 : 1) * t.getAmount())
    .toArray(Integer[]::new);

Arrays.parallelPrefix(amounts, Integer::sum);

Arrays.stream(amounts).max(Integer::compareTo); 
// returns Optional[1700]

作为流collect，它还需要一个关联函数，Integer::sum满足该性质。缺点是它需要一个数组并且不能与列表一起使用。虽然parallelPrefix非常高效，设置阵列来使用它并没有什么回报。

包起来：

同样，使用 Java Streams 可以实现这一点，尽管它在时间和空间上不如传统循环那么高效。但您可以从流的组合性中受益。一如既往，这是一种权衡。