何度も実行される箇所で Linq を使うことによるパフォーマンスの影響

PE Linq

Project Euler 23 を解いていて、Linq 使用の有無で速度差が出たのでメモ。

約数の和を求める SumProperDivisors メソッドで Linq を使う場合と、Linq を使わずに for 文で計算する場合とでどれくらい速度に差が出るか計測してみました。

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    const int N = 28123;

    static int SumProperDivisors(int n) {
#if USE_LINQ
        return Enumerable.Range(1, n/2).Where(e => n % e == 0).Sum();
#else
        int sum = 0;
        for (int i = 1; i <= n/2; i++) {
            if (n % i == 0) {
                sum += i;
            }
        }
        return sum;
#endif
    }

    static bool IsAbandant(int n) {
        return SumProperDivisors(n) > n;
    }

    static void Main() {
        var xs = Enumerable.Range(1, N).Where(IsAbandant).ToList();

        var tab = new bool[N + 1];
        foreach (var x in xs) {
            foreach (var y in xs) {
                int m = x + y;
                if (m <= N) {
                    tab[m] = true;
                }
            }
        }

        int ans = Enumerable.Range(1, N).Where(e => !tab[e]).Sum();
        Console.WriteLine(ans);
    }
}

Linq を使う場合の実行結果です。コマンドラインで、USE_LINQ シンボルを定義しています。

$ mcs -optimize+ -d:USE_LINQ 023.cs
$ time mono 023.exe
4179871
mono 023.exe  2.39s user 0.01s system 99% cpu 2.410 total

次に Linq を使わない場合の実行結果です。

$ mcs -optimize+ 023.cs
$ time mono 023.exe
4179871
mono 023.exe  0.85s user 0.01s system 99% cpu 0.865 total

Linq を使わずに for 文で計算すると、2.8 倍ほど速度アップしました。 何度も実行される箇所で Linq を使うと、パフォーマンスに影響があるかもしれません。