今からできる、速くシンプルに LINQ を書くためのコツ 3 個

お知らせ

2021 年 9 月現在，この記事の大幅な改訂版を書いています．こちらも合わせてご活用ください．

LINQ のコツ 2021 年版 (1) - LINQ の遅延評価

執筆予定の続編:

よい materialization と悪い materialization
LINQ を pure にしよう
SelectMany の活用
IAsyncEnumerable と System.Linq.Async
Parallel.ForEachAsync

はじめに

たびたび「LINQ が遅い」と言われているのを見かけるので、どうやったら速く書けるのか、どう書くと遅くなるのかについてまとめてみます。 LINQ は非常に強力で、ぼくが出会った「LINQ 遅い」のほとんどは、実装の仕方がまずいものばかりです。 LINQ はいくつかポイントを意識するだけでかなり安全に速く書けるようになります。いろいろとポイントはありますが、 3 つだけに絞って書いてみました。

私自身 C# 書き始めてようやく 2 年たったぐらいなので、間違っているところはバシバシご指摘いただけると嬉しいです。

こちらの記事も参考になるので、合わせてご覧ください。

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

「LINQ が遅い」の 3 パターン

LINQ は速くないこともたまにあるのですが、大抵の場合は十分なパフォーマンスを提供してくれます。「LINQ が遅い」と言う時はだいたい以下のどれかかなと思います。

よくわからないけどイメージで「遅そう」と言っている (使いたくない、覚えたくない)
LINQ のしくみがよくわからず、誤った使い方、明らかに遅い書き方をしている (例: なんとなく Count(), ToArray() などしてしまう)
LINQ の内部実装をよく知っているプロフェッショナルが LINQ が適していない場合に「遅い」と言う

1 の場合はどうにもできないです。 3 の場合は必要に応じて LINQ 以外の方法を取ることもできますし、 LINQ を使うと判断した場合は最も適切なメソッドを選んで使用できるので遅くなりません。プログラマとしてはここを目指したい。問題は 2 の場合で、「なんとなく動くものは書けるけど遅い、どこが遅いのかよくわからない」というのが多いです。今回は最も多いと思われる 2 のパターンをターゲットに書いていきます。

1. 不用意に要素数を取得しない (Count メソッド)

一番良く見かけるのがこれです。簡単に書けてしまいますが非常に危険です。

IEnumerable<Hoge> source = // ...

if (source.Count() > 0)
{
    // 要素があるときの処理
}

IEnumerable<T> は一般にはカウントを持ちません。いくつ要素があるのかも全部列挙してみないとわかりません。もしかしたら非常に長かったり、列挙におおきなコストがかかったり、無限につづくシーケンスでそもそもカウントできないかもしれません。 Count メソッドは IEnumerable<T> の実体が配列の場合などは最適化されていますが，一般には 100 万個要素があったら 100 万個全部を 1 個ずつ列挙して数えていくため非常に遅く、ほとんどの場合に意図していない列挙を発生させます。もちろん Count の前に Select や Where をかけていて、列挙の際になんらかの計算が発生するような場合にはその計算のコストもかかります。実体が Count プロパティをもつコレクションである場合には Count プロパティの値を取得するような最適化は入っているものの、本当に「何個あるか知りたい時」以外使うべきでないです。

source.Count() > 0 と書くのであれば、代わりに source.Any() と書きましょう。

「ある条件を満たす要素が n 個以上あるかどうかを判定したいとき」には下記のように Skip や Take を使用することで、一部だけの列挙におさえることができます。

var filtered = source.Where(predicateFunc);

// 列挙した要素を一切使わず、ただ n 個以上あることをたしかめたいとき
// 列挙したものを保存する必要がないのであれば、この方法で無駄な配列確保を避けられる
if (filtered.Skip(n - 1).Any())
{
    // n 個あった時の処理
}

// 列挙した要素を n 個使用するとき
// 複数回同じものに対しての列挙を避けるには、ToArray() が有効。
// ただし、 n が大きくなった場合、それだけ大きい配列が確保されるので注意。これは ToList() でも同様
var part = filtered.Take(n).ToArray();

if (part.Length == n)
{
    foreach (var item in part)
    {
        // なにか処理
    }
}

2. なんとなく配列やリストに突っ込まない。ライブラリを作るときはなるべく IEnumerable で受ける。

ToArray() や ToList() は非常に便利なメソッドですが、ほとんどの場合 LINQ の途中で呼ぶ必要はありません。たとえば、下記のような ToArray は意味がないばかりか、無駄な配列のためのメモリを確保してパフォーマンスを著しく低下させます。

IEnumerable<Hoge> source = // ...

var array = source.ToArray() // むだな配列生成
    .Select(x => ごにょごにょ)
    .Where(x => ごにょごにょ)
    .Distinct()
    .ToArray(); // むだな配列生成

// foreach するだけならむだな array はいらない
foreach (var x in array)
{
    // なにかする
}

下記のように書いてもまったく動作上問題がなく、パフォーマンスがよくなります。

IEnumerable<Hoge> source = // ...

var array = source
    .Select(x => ごにょごにょ)
    .Where(x => ごにょごにょ)
    .Distinct();

// foreach するだけならむだな array はいらない
foreach (var x in array)
{
    // なにかする
}

また、配列である必要がないのに配列で引数を要求するメソッドを書くのはやめましょう。 IEnumerable<T> で受けましょう。本当は 1 個ずつ処理するだけのメソッドなのに、渡す側で ToArray() して渡す必要があるのは無駄です。

3. 巨大なファイルを 1 行ずつ処理するときも、リストはいらない。

たとえば、こんなコードを書いたことはありませんか？これはほんとうに無駄なのでやめましょう。

// 1 行ずつ処理したいけど、 LINQ をつかうから IEnumerable<T> がほしい。 List<T> に Add していこう

List<Hoge> sourceList = new List<Hoge>();

using (var reader = new StreamReader(stream))
{
    string line;
    while ((line = reader.ReadLine()) != null
    {
        sourceList.Add(MapToHoge(line));
    }
}

sourceList.Select(xxx).Where(xxx). // ...

こんなふうに書けば、一気に全部読んでしまう必要はまったくありません。

IEnumerable<Hoge> Read()
{
    using (var reader = new StreamReader(stream))
    {
        string line;
        while ((line = reader.ReadLine()) != null
        {
            yield return MapToHoge(line);
        }
    }
}

Read().Select(xxx).Where(xxx) // ...

あるいは、ファイルから読むことがわかっているならこれでも良いです。

File.ReadLines("filepath")
    .Select(xxx)
    .Where(xxx)
    . // ...

File.ReadAllLines メソッドもありますが、こちらはすべてを読んで配列に入れてから返してくるので気をつけましょう。巨大なファイルを読む場合に大量のメモリが必要になります。

さいごに

たくさん書きましたが、要するにおなじシーケンスに対しての複数回の列挙や、必要のないものの列挙、巨大なメモリ確保にもっと慎重になりましょうということです。 LINQ は遅延評価が基本ですが、誤った使い方をすればそのメリットを活かせないばかりか、非常に遅いコードが簡単に出来上がってしまいます。遅いのは LINQ のバグでも、 .NET Core 開発チームの怠慢でも、マシンのスペックが足りないからでもなく、ただ遅くなるように書いたからです。そうでないこともありますが、だいたいそうです。

自分で書いたコードが遅かったり、すっきり書けなかったりして困ったときに、Qiita や twitter に投稿するといろんな人のアドバイスが受けられて楽しいです。読む人にとってはその投稿についたコメントや、反応の記事のほうが役にたつことがたくさんありますが、最初の投稿がなければそれらの記事も生まれません。

また， LINQ の内部の実装を読むことは非常に勉強になります。 GitHub で .NET Core の完全な実装を読むことができます。難しく見えるかもしれませんが、単純なもの、きになるものから読んでいくといいと思います。また、簡単そうなメソッドを自分で書いてみるのも理解するには効果がありました。 LINQ を書く際に気をつけることはこれがすべてではありませんが、ドキュメントやコードをきちんと読んだり、信頼できる先輩にアドバイスをもらったりしながらだんだんと身についていくものだと思います。

あと、 ReSharper などのツールを入れると multiple enumeration の注意を出してくれたりもします。（ReSharper は他にもいろいろなことを教えてくれる素晴らしい先生になるのでめちゃくちゃおすすめです）

(おまけ) 記事を書いたきっかけ

もともと微妙なコードをちょくちょく見かけていて、 LINQ ってそんなに難しいのかなーと思っていたのですが、 twitter で

C#で Linq を使うより Python の方が 2 倍速かったのでベンチマークをしてみた - Qiita

という記事が回ってきました。

公開から短時間でいいねが複数ついていたことから、ほんとうは速くシンプルに書けるにもかかわらず、 LINQ が遅いと判断してしまう人は多いのではないかと思い、急いで記事を書いている次第です (そもそもこのブログ自体そんなに見られてないのでどの程度効果があるかは疑問ですが)。

この記事の具体的な内容についてはもう十分他の方が指摘などされていると思いますので、ここでは細かく言及しません。ただ、もし初心者の方が読まれる場合には下記の点だけは頭においてほしいです。

(意図的にそうしているとは思いませんが、結果として) 検証用のコードが非常に遅くなるように書かれています。検証用のコードを改善することでだいぶ速い結果になる、という記事がすでにあります。GroupBy が遅いように書かれていますが、それよりも無駄な ToList 何度も呼んでいるめにループの回数が増えてしまっていることのほうがはるかに大きな問題です。C# の Linq が python の２倍遅い、は嘘 - Qiita
Span<T> に関しては用途が違うように思います。 Qiita の記事とは全く無関係ですが、日本語で読める Span<T> の記事としては Span構造体 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C がとても参考になります。
実際には、LINQ に限らず .NET のパフォーマンスの改善や新機能の開発に多くの優秀なエンジニアが取り組んでいます。また、明らかに遅かったり問題があり、改善方法があることが本当にわかっているなら、 issue をあげたり、プルリクエストを送ってみたりする手段は誰にでも開かれています。

BenchmarkDotnet を使って LINQ の部分のベンチマークをとってみたところ、標準の LINQ メソッドだけで 3 倍以上高速になりました。

SlowLinq が Qiita の元記事、 NormalLinq がそれを書き直したもの、 UseGroupSum が GroupBy を使わないものです。

Method	Mean	Error	Gen 0	Gen 1	Gen 2	Allocated
SlowLinq	321.59 ms	NA	12400.0000	6200.0000	800.0000	78916.81 KB
NormalLinq	85.77 ms	NA	1400.0000	600.0000	-	8415.32 KB
UseGroupSum	62.12 ms	NA	-	-	-	147.43 KB

Cisis - C##

ASP.NET Core 開発者のブログ