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

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などが入ってしまう場合、 prevcurrentを代入するのを忘れると変数の状態がおかしくなるという危うさを持つ。

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がいいのかな。

programming/csharp/performance/foreach_with_prev.txt · 最終更新: 2016/08/01 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0