std::accumulateをstd::reduceに書き換えるためにどうすればいいか

はじめに

配列の要素を合計するような関数としてC++17より前はstd::accumulateというのがありました。

C++17では新たにstd::reduceが追加されました。

std::reduceはC++17で追加されたparallel algoritmsと呼ばれる、並列化に対応しています。

std::accumulateは対象配列の先頭から合計するという性質を持っていたために、並列化できなかったのですが、std::reduceにはその制約がないため並列化ができるわけです。

当然並列化してくれたほうが助かるので書き換えたいわけですが、この制約の違いから、バグを作り込まないようにする必要があります。

単純な書き換えで済む場合

単なる合計などは特に悩むことはありません。

accumulate

using value_type = std::int64_t;
value_type calc_sum(const std::deque<value_type>& logbuf) {
	return std::accumulate(logbuf.begin(), logbuf.end());
}

reduce

using value_type = std::int64_t;
value_type calc_sum(const std::deque<value_type>& logbuf) {
	return std::reduce(std::execution::par, logbuf.begin(), logbuf.end());
}

交換法則が成り立っていなかった場合

標準偏差を求める例を見ていきます。標本標準偏差は各要素と平均値との差の2乗の総和を要素数-1で割ってルートをとったたものでした

accumulate

using value_type = std::int64_t;
double calc_stdev(const std::deque<value_type>& logbuf, double average) {
	return std::sqrt(
		std::accumulate(logbuf.begin(), logbuf.end(), 0.0, [average](double sum, value_type val) {
			return sum + std::pow(static_cast<double>(val) - average, 2);
		}) / (logbuf.size() - 1)
	);
}

reduce

using value_type = std::int64_t;
double calc_stdev_impl(double n, double) { return n; }
double calc_stdev_impl(value_type n, double average)
{
	const auto re = static_cast<double>(n) - average;
	return re * re;
}
double calc_stdev(const std::deque<value_type>& logbuf, double average) {
	return std::sqrt(
		std::reduce(std::execution::par, logbuf.begin(), logbuf.end(), 0.0, [average](auto l, auto r) {
			return calc_stdev_impl(l, average) + calc_stdev_impl(r, average);
		}) / (logbuf.size() - 1)
	);
}

std::reduceにわたすbinary_opは以下の全ての演算結果の型が、型Tに変換可能であることが必要です。

• binary_op(init, *first)
• binary_op(*first, init)
• binary_op(init, init)
• binary_op(*first, *first)

さて、今回の例だとTはdoubleです。一方で要素の型はstd::int64_t型です。つまりbinary_opの2つの引数はこの2つの引数をそれぞれ受け取れる必要があります。これを解決するためにC++14で追加されたジェネリックラムダを用います。

また、binary_opの計算結果はdouble型にしたので、引数がdouble型のとき、その値はすでに平均差の2乗の部分和になっているわけですから加工は不要になります。今回は関数overloadで解決してみました。

std::accumulateでは部分和は第一引数に来ましたが、std::reduceではどちらに来るかわからないという点がポイントとなりそうです。