エンジニア

LINQのJoinを使って計算オーダーを削減・高速化

投稿日：

こんにちは。タノシムスタジオでUnityクライアントエンジニアをやっている水戸です。
みなさん、LINQ使ってますか？
今回は、LINQを使った、いわゆるN+1問題のようなパフォーマンスの悪い実装例と、それの解決例についてご紹介します。

N+1問題とは

ORマッパーを利用している際に発生しやすい問題です。

  • 一覧に表示するデータを取得するために SELECT を 1 回実行（N レコード返される）
  • 各データの関連データを取得するために SELECT を N 回実行

このように、関連するいくつかのデータを取得しようとした際に、意図せず大量のSQLが発行され、パフォーマンスが低下することを指します。
N+1というよりは1+Nと捉える方がわかりやすいです。

パフォーマンスの悪い実装例

UnityでLINQを使う際、N+1問題に似た問題に直面することがあります。

以下のようなデータモデルを持つゲームがあるとします。

キャラクターと、キャラクターが出てくるストーリーのデータです。
キャラクターとストーリーはそれぞれListなどで持っているものとします。
このデータを使って、ストーリーに出てくる名前が5文字以下のキャラクターの名前一覧を取得してみます。

class Example
{
  List<Character> characters { get; }
  List<CharacterStory> characterStories { get; }

  public List<string> GetCharacterStoryCharacters()
  {
    var filteredCharacters = characters.Where(c => c.Name.Length <= 5);
    return characterStories
        .Select(s =>
        {
          var character = filteredCharacters.First(c => c.Id == s.CharacterId);
          return character.Name;
        })
        .ToList();
  }
}

このコードはもちろんなんの問題もなく動作します。
ですが、先ほど紹介したN+1問題の例に、状況が似ていることがおわかりいただけますでしょうか。

これがLINQを利用した際のパフォーマンスの悪い例です。

CharacterStoriesのSelect内部でfilteredCharactersに対してFirstを呼び、結果のNameで射影しています。
つまり、CharacterStoriesの数だけfilteredCharactersにFirstが呼ばれることになります。

CharacterやCharacterStoryの数が膨大になれば、リストの個数+1回リストへのアクセスが起き、パフォーマンスが劣化するというわけです。

さらに、このフィルタリング処理ではIEnumerableの遅延評価の性質が考慮されていないため、ここでもさらにパフォーマンスが劣化します。

IEnumerableの遅延評価について

IEnumerableでは、オブジェクトの評価は遅延実行されます。
先ほど紹介したコードを抜粋して説明します。

var filteredCharacters = characters.Where(c => c.Name.Length <= 5);
return characterStories
    .Select(s =>
    {
      var character = filteredCharacters.First(c => c.Id == s.CharacterId);
      return character.Name;
    })
    .ToList();

IEnumerableの要素を評価する際、MoveNext()というメソッドが内部的に呼ばれ、その際に要素の値が評価される仕組みになっています。
つまり、上記のコードではcharactersの要素数だけ評価されるはずが、characterStoriesの要素数 × charactersの要素数の回数評価が行われることになります。
今回のようなケースでは、事前にToArrayやToListを呼び、確定した要素のリストに変換しておくことで無駄に行われていた処理を省略できます。

上記コードの改善例

さて、Selectなどのループの内部で検索処理を使ったり、IEumerableの性質を考慮しないとパフォーマンスが劣化することがわかったところで、上記のコードをどのように改善するか例をご紹介します。

class Example
{
  List<Character> characters { get; }
  List<CharacterStory> characterStories { get; }

  public List<string> GetCharacterStoryCharacters()
  {
    var filteredCharacters = characters.Where(c => c.Name.Length <= 5).ToList();
    return characterStories
        .Join(filteredCharacters, s => s.CharacterId, c => c.Id, (s, c) => new { CharacterName = c.Name })
        .Select(t => t.CharacterName)
        .ToList();
  }
}

LINQのメソッドであるJoinを用いることで、高速化を図りました。

.Join(
      結合するリスト,
      結合する側の結合条件（characterStories）,
      結合される側の結合条件（filteredCharacters）,
      (（結合する側の変数）, （結合される側の変数）)
　　　 => new
      {
         （結合後のテーブル）
      })

引数が多くてややこしいですが、二つのリストを結合するためのメソッドです。
上記の例を言語化してみると、

  • characterStoriesとfilteredCharactersの二つのリストを結合する
  • CharacterStoryのCharacterIdと、CharacterのIdが同じものという条件
  • 結合されたデータから匿名型で射影する(中身は、CharacterNameのみを持つ構造)

といった形です。

第4引数で指定するデータ型には例のように匿名型を使うこともでき、全く新しい構造に書き換えることも可能です。
(むしろ、匿名型を使って必要最低限のデータを後ろに回すのが良いと思います。)

パフォーマンス計測してみた

Select + Firstのコードと、Joinのコードの実行時間を計測してみました。
結果は以下の通りです。

Select + First Join
100件ずつ 2ミリ秒 4ミリ秒
1000件ずつ 16ミリ秒 4ミリ秒
10000件ずつ 1111ミリ秒 7ミリ秒

リストの件数が少ない場合はSelect + Firstの方が速いですが、件数が多くなるとJoinの方が速いという結果になりました。
Joinの内部処理でLookupテーブルの作成とグルーピングする処理があるため、件数が少ないとその処理がネックになるようです。

予め件数が少ないとわかっている場合にはSelect + Firstでも良いかもしれません。

あとがき

いかがでしたでしょうか。
私の場合、改善前のコードではゲームのユーザー情報を表示する機能でUnityEditorがフリーズしました。
(もっとも、かなり煩雑な事例でしたが)

ゲームの場合、多数のデータが関連することがありがちなので、特に気をつける必要がありますね…
LINQは便利なメソッドがたくさん用意されているのでいろいろな使い方ができますが、うっかりパフォーマンスの悪いコードを書いてしまうことがないように気をつけましょう。

採用情報

ワンダープラネットでは、一緒に働く仲間を幅広い職種で募集しております。

-エンジニア
-

© WonderPlanet Inc.