前の要素を参照しつつのループ処理

Listに入った要素に順番に処理を施す構文にはforやLINQなどがあるが、中でも1つ前の要素と現在の要素を同時に参照したいことがある。

順番に座標データが入ったListから、1つずつ1つ前の点との距離を算出して足し合わせると、道のりの距離が出せる、など

方法はいろいろあるが、速度をある程度気にするならどれを使うべきかというテスト。今回は、intList内の並んだ2要素の積を、すべて合計した数値を得るとする。（1*2 + 2*3 + 3*4 + …）

// テストに使用する配列
List<int> intList = Enumerable.Range(1, 1000).ToList();
// ループ回数
int loopMax = 100000;

for文内部で要素取得

forを使い、内部で2つのList探査をする。

int result = 0;
for (int j = 0; j < intList.Count - 1; j++)
{
    result += intList[j] * intList[j + 1];
}
// 861ms

昔ながらの方法。ぽたぽた焼きの香り。

for文外部で要素保持

forループの外に前回の要素を保存する変数を用意

int result = 0;
int prev = intList[0];
for (int j = 1; j < intList.Count; j++)
{
    int current = intList[j];
    result += prev * current;
    prev = current;
}
// 673ms

テストした中ではもっとも速かったが、for文内の処理がもう少し複雑になり、途中でcontinueなどが入ってしまう場合、 prevにcurrentを代入するのを忘れると変数の状態がおかしくなるという危うさを持つ。

foreach外部で要素保持

上のforeach版。Skip(1)で最初の要素を飛ばす。

int result = 0;
int prev = intList[0];
foreach (int current in intList.Skip(1))
{
    result += prev * current;
    prev = current;
}
// 1287ms

Skip(1)で新しいコレクションを生成するためか、forに比べ2倍近い時間がかかってしまう。

Aggregate

次のループに現在の値を引き継げるLINQ。

int result = 0;
intList.Skip(1).Aggregate(intList[0], (p, n) =>
{
    result += p * n;
    return n;
});
// 2153ms

もともとはList内の要素を合計するときなんかに使うはずだが、こういう使い方もできる。でも遅いし、特にわかりやすくないし、これを選ぶ意味はなさそう。

イテレータを定義

private IEnumerable<Tuple<int, int>> GetPrevAndCurrent(List<int> list)
{
    int prev = list[0];
    for (int i = 1; i < list.Count; i++)
    {
        int current = list[i];
        yield return Tuple.Create(prev, current);
        prev = current;
    }
}

...

int result = 0;
foreach (Tuple<int, int> tpl in GetPrevAndCurrent(intList))
{
    result += tpl.Item1 * tpl.Item2;
}
// 4490ms

for文の部分を外に出した感じ。関数名を正しく命名すれば直感的に分かりやすいコードになるし、他にも同様の処理を行う個所があれば使いまわせるので可読性は増すが、いかんせんタプルの生成が重たい。タプルでなくて配列にしても速度はほぼ変わらなかった。

1つずらしてZip

result = intList.Zip(intList.Skip(1), (p, n) => p * n).Sum();
// 3181ms

Skip(1)で1つずらしたリストと、元のリストをZipで掛けあわせ、Sumで合計。 Zipは2つの要素数が異なる場合、少ない方に合わせられる。重たいが、1行で書けるのはいい。速度がそこまで気にならない要素数でオシャレに書くならこれか。

結論

	1000 Range 100000 loops	50 Range 2000000 loops
for文内部	861	900
for文外部	673	715
foreach	1287	1494
Aggregate	2153	2285
IEnemurable	4490	4807
Zip	3181	3381

単純なテストでは、ループの外に前回の要素を保存するfor文が最も速くなった。

そもそも速度を必要とするならC#使うなって話だけど、いざ直面した時に少しでもましな方法をとるならforがいいのかな。

目次