C# Tips | コレクション・LINQ：高速検索

C# C#
スポンサーリンク

はじめに：「高速検索」は“探し方を変えるだけで世界が変わる”テクニック

LINQ を覚えたての頃は、だいたいこう書きがちです。

var user = users.FirstOrDefault(x => x.Id == id);
var exists = users.Any(x => x.Email == email);
C#

小さいデータならこれで十分ですが、件数が 1 万、10 万、100 万と増えてくると、
「毎回、先頭からなめて探す」やり方では、だんだんしんどくなります。

ここで効いてくるのが「高速検索」の発想です。
ポイントはたった一つで、

「毎回“全部をなめて探す”のではなく、“探しやすい形にしてから探す”」

に切り替えることです。

ここでは、初心者向けに

線形検索（Where/First）の限界
Dictionary / HashSet による高速検索
ToDictionary / ToLookup で“検索用インデックス”を作る
LINQ と高速検索をどう組み合わせるか

を、例題付きでかみ砕いて説明していきます。

まず押さえるべき前提：Where/First は「毎回、全部をなめて探す」

直感的には分かりやすいけど、スケールしにくい書き方

var user = users.FirstOrDefault(x => x.Id == id);
C#

これは「先頭から順番に見ていって、条件に合うものが見つかったら止める」という動きです。
最悪の場合、「最後まで見ても見つからない」ので、全件をなめることになります。

1 回だけなら大したことはありませんが、

1 つの画面表示の中で 100 回同じような検索をする
バッチ処理で 1 万回ループの中から毎回検索する

となると、「毎回、全件をなめる」コストが積み上がって、目に見えて遅くなります。

ここでの重要ポイントは、

「Where/First/Any だけで頑張る＝“毎回、線形検索している”」

という自覚を持つことです。

高速検索の基本：Dictionary で「キー検索」に変える

Id で探すなら、最初から「Id → User」の辞書を作る

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

public class User
{
    public int Id { get; set; }
    public string Name { get; set; } = "";
}

var users = new List<User>
{
    new User { Id = 1, Name = "Alice" },
    new User { Id = 2, Name = "Bob" },
    new User { Id = 3, Name = "Charlie" }
};
C#

「Id から User を何度も引きたい」なら、こうします。

var userById = users.ToDictionary(x => x.Id);
C#

これで Dictionary<int, User> ができます。

if (userById.TryGetValue(2, out var user))
{
    Console.WriteLine(user.Name); // Bob
}
C#

ここでの重要ポイントは、

「FirstOrDefault(x => x.Id == id) を毎回やるのではなく、
一度 ToDictionary で“検索用インデックス”を作ってから、
TryGetValue で O(1) で引く」

という発想に切り替えることです。

何がそんなに違うのか（ざっくりイメージ）

FirstOrDefault(x => x.Id == id)
毎回、先頭から順番に見ていく（最悪 O(N)）

Dictionary + TryGetValue
内部でハッシュテーブルを使って、ほぼ一定時間で見つかる（平均 O(1)）

件数が増えれば増えるほど、この差が効いてきます。

存在チェックの高速化：HashSet を使う

Contains を「速くて正しい形」で使う

「この ID が存在するかどうかだけ知りたい」という場面も多いです。

var exists = users.Any(x => x.Id == id);
C#

これも毎回、全件をなめる可能性があります。

「ID の集合」が分かっているなら、HashSet にしてしまうのが定番です。

var idSet = users
    .Select(x => x.Id)
    .ToHashSet();

var exists = idSet.Contains(id);
C#

ここでの重要ポイントは、

「Any(x => 条件) を乱発するより、
“条件に使う値だけを HashSet にしておいて Contains する”ほうが圧倒的に速い」

ということです。

複数件ヒットする検索：ToLookup で「1 対 多」のインデックスを作る

例：部署ごとにユーザーを引きたい

public class User
{
    public int Id { get; set; }
    public string Department { get; set; } = "";
    public string Name { get; set; } = "";
}

var users = new[]
{
    new User { Id = 1, Department = "Sales", Name = "Alice" },
    new User { Id = 2, Department = "Dev",   Name = "Bob" },
    new User { Id = 3, Department = "Sales", Name = "Charlie" },
    new User { Id = 4, Department = "Dev",   Name = "Dave" },
};
C#

「部署ごとにユーザー一覧を何度も取りたい」なら、毎回こう書くのはもったいないです。

var salesUsers = users.Where(x => x.Department == "Sales");
var devUsers   = users.Where(x => x.Department == "Dev");
C#

代わりに、ToLookup で「部署 → ユーザー列」のインデックスを作ります。

var usersByDept = users
    .ToLookup(x => x.Department);
C#

これで ILookup<string, User> ができます。

var salesUsers = usersByDept["Sales"];
var devUsers   = usersByDept["Dev"];

foreach (var u in salesUsers)
{
    Console.WriteLine(u.Name);
}
C#

ここでの重要ポイントは、

「ToDictionary が“1 対 1”、ToLookup が“1 対 多”のインデックス」

というイメージを持つことです。
「キーに対して複数件ヒットする」のが分かっているなら、ToLookup が素直です。

LINQ と高速検索をどう組み合わせるか

パターン1：最初にインデックスを作ってから LINQ で流す

例えば、「注文の明細に、商品マスタの情報をくっつけたい」ケース。

public class OrderLine
{
    public string ItemCode { get; set; } = "";
    public int Quantity { get; set; }
}

public class Item
{
    public string Code { get; set; } = "";
    public string Name { get; set; } = "";
}

var lines = new[]
{
    new OrderLine { ItemCode = "A", Quantity = 1 },
    new OrderLine { ItemCode = "B", Quantity = 2 },
    new OrderLine { ItemCode = "A", Quantity = 3 },
};

var items = new[]
{
    new Item { Code = "A", Name = "Apple" },
    new Item { Code = "B", Name = "Banana" },
};
C#

素朴に書くと、こうなりがちです。

var result = lines
    .Select(line =>
    {
        var item = items.FirstOrDefault(x => x.Code == line.ItemCode);
        return new
        {
            line.ItemCode,
            line.Quantity,
            ItemName = item?.Name
        };
    })
    .ToList();
C#

これは「明細の件数 × 商品マスタの件数」だけ検索が走るので、件数が増えると効いてきます。

高速検索を意識すると、こう書き換えられます。

var itemByCode = items.ToDictionary(x => x.Code);

var result = lines
    .Select(line =>
    {
        itemByCode.TryGetValue(line.ItemCode, out var item);

        return new
        {
            line.ItemCode,
            line.Quantity,
            ItemName = item?.Name
        };
    })
    .ToList();
C#

ここでの重要ポイントは、

「“マスタ側”は先に Dictionary にしておいて、
“トランザクション側”からはキー検索だけにする」

というパターンを覚えることです。
業務システムでは、この構図が本当に頻繁に出てきます。

高速検索ユーティリティを自作しておく

「IndexBy」のような名前で 1 本持っておく

毎回 ToDictionary と書くのも悪くないですが、
「インデックスを作る」という意図をはっきりさせるために、
ユーティリティ拡張メソッドを 1 本用意しておくのも手です。

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

public static class IndexExtensions
{
    public static Dictionary<TKey, TSource> IndexBy<TSource, TKey>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector)
        where TKey : notnull
    {
        return source.ToDictionary(keySelector);
    }
}
C#

使い方はこうです。

var itemByCode = items.IndexBy(x => x.Code);
C#

ここでの重要ポイントは、

「IndexBy という名前だけで、“これは検索用インデックスだな”と読み手に伝わる」

ということです。
ToDictionary だと「ただの変換」にも見えてしまうので、意図を名前に乗せるのは結構効きます。

どこまでやるかの判断基準

いつ Dictionary / HashSet / ToLookup を使うべきか

ざっくりした目安としては、

同じ条件での検索を何度も繰り返す
マスタデータとトランザクションデータを突き合わせる
存在チェックを大量に行う

といった場面では、「高速検索用のインデックスを作る」ことを検討してよいです。

逆に、

1 回しか検索しない
件数が数十件程度で小さい
コードのシンプルさを優先したい一時的なスクリプト

なら、素直に FirstOrDefault や Any で十分です。

ここでの重要ポイントは、

「高速検索は“常にやるべき最適解”ではなく、
“繰り返し検索するところにだけ投資するチューニング”」

という感覚を持つことです。

まとめ：「高速検索ユーティリティ」は“探し方を設計するための道具”

高速検索の本質は、

「毎回、全部をなめて探す」のをやめて、
「探しやすい形（インデックス）に変えてから探す」

ことです。

押さえておきたいポイントを整理すると、

Where/First/Any だけで頑張ると、件数が増えたときに線形検索のコストが効いてくる
1 対 1 の検索は Dictionary（ToDictionary + TryGetValue）
存在チェックは HashSet（ToHashSet + Contains）
1 対 多の検索は ToLookup（キー → 要素列）
マスタ側をインデックス化して、トランザクション側からキー検索するパターンは業務で超頻出
IndexBy のようなユーティリティを用意しておくと、意図がコードに乗る

ここまで腹落ちしていれば、
「なんとなく LINQ で毎回 Where して探す」段階から卒業して、
“どこでインデックスを張るかを自分で設計できる C# エンジニア”に一歩近づけます。

スポンサーリンク
タイトルとURLをコピーしました