はじめに
いわゆる「畳み込み」処理を行うための高階関数が、いろいろなプログラミング言語で用意されています。
それぞれの言語では、fold、reduceのいずれかの関数名であることが多いようです。
しかし、D言語ではfoldとreduceの両方が用意されています。
なぜそうなのかを調べた際のメモになります。
さらに、foldとsumについても調べました。
foldとreduce
くりかえしになりますが、D言語では「畳み込み」処理を行う関数として、foldとreduceがあります。
import std;
void main()
{
int[] arr = [10, 20, 30, 40];
writeln(fold!("a + b")(arr));
writeln(reduce!("a + b")(arr));
}
100
100
sample1.dでは、配列arrに格納された値を足し合わせた結果を表示します。
foldでもreduceでも、同じように使えて、結果も同じ100です。
次に、途中まで集計を行った小計subtotalがあり、小計に配列arrを足し合わせる場合を考えます。
import std;
void main()
{
int subtotal = 50;
int[] arr = [10, 20, 30, 40];
writeln(fold!("a + b")(arr, subtotal));
writeln(reduce!("a + b")(subtotal, arr));
}
150
150
foldとreduceで引数の呼び出し順序が異なります。
実際に、Phobos内のソースコードiteration.dを調べると、引数の呼び出し順序を変えていることがわかります。
auto fold(R, S...)(R r, S seed)
{
static if (S.length < 2)
{
return reduce!fun(seed, r);
}
else
{
import std.typecons : tuple;
return reduce!fun(tuple(seed), r);
}
}
ソースコードからもわかるように、reduceが先に実装されていて、バージョン2.071でfoldが追加されています。
Library Changes
8.fold was added as an alternative to reduce with argument order swapped.
UFCSを利用する際に、より適したfoldを追加したようです。
参考：Forumでの議論
以下に、UFCSを使って記述しました。
foldの方が、arrに対しての「畳み込み」処理であることが直感的にわかるかと思います。
import std;
void main()
{
int subtotal = 50;
int[] arr = [10, 20, 30, 40];
writeln(arr.fold!("a + b")(subtotal));
writeln(subtotal.reduce!("a + b")(arr));
}
foldとsum
バージョン2.071以降であれば、foldとreduceのうち、基本foldを使えばよいことがわかりました。
ところで、D言語では配列(やRange)を合計するための関数として、sumも用意されています。
こちらは、fold!("a + b")と同じかというと、少し違います。
以下は、foldとsumのどちらを使っても同じ結果になる例です。
import std;
void main()
{
int[] arr = [10, 20, 30, 40];
writeln(arr.fold!("a + b"));
writeln(arr.sum);
}
100
100
次に、結果が異なる例です。sumを使った方は正確な値が得られています。
浮動小数を単純に加算すると誤差が発生する例です。D言語のバグではなく、他のプログラミング言語でも同じように誤差が発生する点に、ご注意ください。
import std;
void main()
{
float[] arr = [ 10000.0, 3.14159, 2.71828];
writefln("%.5f", arr.fold!("a + b"));
writefln("%.5f", arr.sum);
}
10005.86035
10005.85987
D言語のsumは、浮動小数を扱う場合に、カハンの加算アルゴリズムを使って、誤差が少なくなるように実装されています。
整数を扱う場合は、foldとsumは同じ動きとなります。
auto sum(R, E)(R r, E seed)
if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)))
{
static if (isFloatingPoint!E)
{
static if (hasLength!R && hasSlicing!R)
{
if (r.empty) return seed;
return seed + sumPairwise!E(r);
}
else
return sumKahan!E(seed, r);
}
else
{
return reduce!"a + b"(seed, r);
}
}
private auto sumKahan(Result, R)(Result result, R r)
{
static assert(isFloatingPoint!Result && isMutable!Result, "The type of"
~ " Result must be a mutable floating point, not "
~ Result.stringof);
Result c = 0;
for (; !r.empty; r.popFront())
{
immutable y = r.front - c;
immutable t = result + y;
c = (t - result) - y;
result = t;
}
return result;
}
※追記：コメントいただいた件について、foldとsumの速度比較を行いました。
sample4.dでは、要素数1億のdouble型配列を生成して加算を行っています。
static import std.datetime.stopwatch;
import std;
void main()
{
immutable times = 100_000_000;
auto rnd = Random();
double[] arr = generate!(() => uniform01(rnd)).takeExactly(times).array;
double res1,res2;
void f1() { res1 = arr.fold!("a + b"); }
void f2() { res2 = arr.sum; }
auto r = std.datetime.stopwatch.benchmark!(f1, f2)(1);
writefln("fold -> %.6f", res1);
writefln("sum -> %.6f", res2);
writefln("fold -> %.6f", cast(double)r[0].total!"usecs" / 1_000_000);
writefln("sum -> %.6f", cast(double)r[1].total!"usecs" / 1_000_000);
}
D:\Dev> ldc2 -release -O sample4.d
D:\Dev> sample4
fold -> 49999807.977276
sum -> 49999807.977278
fold -> 0.097922
sum -> 0.056561
私の事前予想では、foldの方が速いと思っていましたが、sumの方が速かったです。
浮動小数の場合、sumを使えばよさそうです。
速度比較ということで、ldc2でコンパイルしました。
ただし、dmdでもsumの方が速いという結論は同じでした。
念のため、整数型でも試しましたが、foldとsumでどちらが速いということはありませんでした。
ということで、足し算の場合は、sumを使えばよいが私の結論です。