第8.7章: 数值算法

概述

头文件 <numeric> 提供了一批把元素组合起来的算法：求和、归约、计算前缀结果等等。这些算法很简单，但在日常编程中极其有用。

本章将介绍：

accumulate
reduce
transform_reduce
partial_sum
inclusive_scan and exclusive_scan

1. accumulate

accumulate 从左到右处理元素，并用一个二元运算把它们组合起来。它总是需要一个初始值。


::fast_io::vector<int> v{1, 2, 3, 4};

int sum = ::std::accumulate(
    v.begin(), v.end(),
    0,
    ::std::plus<>()
);

print("sum = ", sum, "\n");

可以用 std::multiplies<> 来计算连乘：


int product = ::std::accumulate(
    v.begin(), v.end(),
    1,
    ::std::multiplies<>()
);

注意：初始值会影响结果。例如对整数从 1 而不是从 0 开始累加，得到的总和是不一样的。这正是 reduce 往往更受欢迎的原因之一。

2. reduce

reduce 与 accumulate 类似，但它为并行执行而设计。与 accumulate 不同，它不要求初始值；如果不提供，就使用第一个元素。


int sum = ::std::reduce(
    v.begin(), v.end(),
    ::std::plus<>()
);

你也可以显式提供一个初始值：


int sum2 = ::std::reduce(
    v.begin(), v.end(),
    0,
    ::std::plus<>()
);

由于组合顺序未作规定，该运算必须满足结合律。

为什么优先用 reduce？因为它能避免“选错初始值”这个常见错误。用 accumulate 时忘记初始值会悄悄改变结果；用 reduce 时，默认行为通常就是正确的。

3. transform_reduce

transform_reduce 把投影和归约合成一步。它先对每个元素做一次变换，再对结果做归约。


int total = ::std::transform_reduce(
    v.begin(), v.end(),
    0,
    ::std::plus<>(),
    [](int x) { return x * x; }   // projection: square
);

print("sum of squares = ", total, "\n");

归约使用一个函数对象。投影可以是 lambda，也可以是指向成员的指针。

4. partial_sum

partial_sum 计算前缀和：


::fast_io::vector<int> out(v.size());

::std::partial_sum(
    v.begin(), v.end(),
    out.begin(),
    ::std::plus<>()
);

若 v = {1,2,3,4}，则 out = {1,3,6,10}。

5. inclusive_scan 与 exclusive_scan

它们是对前缀运算的现代、对 ranges 友好的版本。


::std::inclusive_scan(
    v.begin(), v.end(),
    out.begin(),
    ::std::plus<>()
);

::std::exclusive_scan(
    v.begin(), v.end(),
    out.begin(),
    0,
    ::std::plus<>()
);

inclusive_scan 包含当前元素，exclusive_scan 不包含。

要点

accumulate 总是需要初始值。
reduce 不需要初始值，并能避免常见错误。
reduce 对并行友好，且要求运算满足结合律。
transform_reduce 把投影与归约合为一体。
partial_sum 和 scan 系列计算前缀结果。
二元运算请使用函数对象（std::plus<>、std::multiplies<>）。
简单的投影请使用 &Item::member。