かずきのBlog@hatena

日本マイクロソフトに勤めています。このブログは個人ブログなので、ここに書いている内容は個人的な意見で会社の公式見解ではない点にご注意ください。好きなものは XAML と C# 。苦手なものは型の無い言語です。

LINQ を使う時に一般的に気を付けること via C#でLinqを使うよりPythonの方が2倍速かったのでベンチマークをしてみた

追記

2018/04/25 GroupBy が遅延評価じゃないという旨の記載があってまちがえていたので修正しました。

本文

以下の記事を見ました。

qiita.com

そして、それを受けての記事があります。

qiita.com

上記記事に ToList を複数回呼び出してることに関する言及があります。

そう LINQ を使う時に一番効くのが無駄にループを回す処理をいつの間にか書いてしまっていないかというところです。

LINQ は基本的に遅延評価です。例えば…

var array = new[] { 1, 2, 3 };
var result = array.Where(x => x % 2 == 0);

上記コードだけだと、Where を呼び出した行では「あぁ、フィルタリングしたいのね。わかった」というのをお願いしてるだけなので実際に処理は行われません。 LINQ の多くのメソッドは、このようにお願いだけしておいて必要になったら実際に処理をするというように動きます。

じゃぁいつ実行されるの?ということですが、これは実際に処理を実行しないと出来ないものが呼ばれたときになります。わかりやすいのが foreach で回すときです。

var array = new[] { 1, 2, 3 };
var result = array.Where(x => x % 2 == 0);
foreach (var r in result) // 実際に列挙するときはさすがに処理しないと出来ないよね
{
    Console.WriteLine(r);
}

その他には配列やリストに変換するときです。

var array = new[] { 1, 2, 3 };
var result = array.Where(x => x % 2 == 0);
var list = result.ToList(); // リストにするには全要素舐めないと無理
var a = result.ToArray(); // 配列にするには全要素舐めないと無理

といった感じです。因みに上記処理では 2 回要素を走査してます。ToListで1回とToArrayで1回ですね。 このように複数回同じものにたいしてループすることが多い場合は予め配列にしておいたほうが早いケースもあります。

var array = new[] { 1, 2, 3 };
var result = array.Where(x => x % 2 == 0).ToArray(); // ここで一回


foreach (var x in result)
{
    // 何か処理
}

foreach (var x in result)
{
    // 何か処理
}

foreach は配列は特別扱いしてくれるようなので早いんですよね。確か。 今回の Where が 1 つだけなら大したことないですが途中で何かしら重い処理を挟んでいる場合は一旦配列にして(ここで重い処理が走る)から後でループで処理(ここでは重い処理ではなく評価された結果だけ使う)といった形で使えます。

ということなので、最初の python より凄く遅いケースのプログラムを確認してみると…

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using Newtonsoft.Json;

namespace app
{
    class Program
    {
        static void Main(string[] args)
        {
            var stopwatch = new Stopwatch();
            stopwatch.Start();

            using (var reader = new StreamReader("App_Data/test.csv"))
            {
                reader.ReadLine();
                while (!reader.EndOfStream)
                {
                    string s = reader.ReadLine();
                    var columns  = s.Split(',');
                    testData.Add(new TestData
                    {
                        a = columns[0],
                        b = columns[1],
                        x = double.Parse(columns[2]),
                        y = double.Parse(columns[3])
                    });
                }
            }               

            var testData_0 = testData.Select(d => new {d.a, d.b, d.x, d.y, z = MultiplyToInt(d.x, d.y)}).ToList();
            var testData_1 = testData_0.GroupBy(d => d.a)
                .Select(g => new {a = g.Key, sum = g.Sum(d => d.z)}).ToList();
            using (StreamWriter file = File.CreateText("App_Data/result.json"))
            {
                JsonSerializer serializer = new JsonSerializer();
                serializer.Serialize(file, testData_1);
            }

            var ts = stopwatch.Elapsed;            
            Console.WriteLine($"処理時間: {ts.TotalSeconds}秒");
        }

        static int MultiplyToInt(double x, double y)
        {
            if (x > 0)
                return (int)(x * y + 0.0000001);
            return (int)(x * y - 0.0000001);
        }
    }

    class TestData
    {
        public string a { get; set; }
        public string b { get; set; }
        public double x { get; set; }
        public double y { get; set; }
    }
}

まず、StreamReader を使ってデータを読み込むところで 100 万回のループ、そして途中に ToList が 2 個あるので 100 万回ループが追加で 2 つ。そしてシリアライズのタイミングでもループを回さないといけないで、ここでも 1 回ループが入ります。(厳密には最後の ToList とシリアライズ時のループは GroupBy した結果に対してなので 100 万件もデータはないですが)

こういう意図しないループが複数回走ると LINQ はというよりまぁ当然遅くなります。 LINQ 使ってみたんだけど凄く遅いんだよねっていうのは割とこのケースが多いので遅かったら、この観点でチェックしてみるといいなと思います。

最後に

この手の話は結構前から何度も出てるのですが、まぁ新たに書くことで新たに目に触れる機会のある人もいるかな?ということで書いてみました。 あと C で書かれた最適化されまくったライブラリが pip で手軽にインストールしてさくっと呼べるという形に整備されまくってる python はいいなと思いました。 最近は何言語使ってもそこそこ早いですよね。なので得意なものでさくっとやってしまうのが 1ms の速度を気にするよりはコーディングにかかる時間を考えるといいと思います。

まぁ、パフォーマンスが重要なものに関しては別ですが。