GroupByとToLookup

ここしばらく、C#関連記事ではGroupByを使ったものが続いています。

ところで、.net Frameworkには、GroupByと非常によく似た「ToLookup」というEnumerable拡張メソッドがあります。大体名前のイメージで、GroupByは遅延実行で、ToLookupは即時実行だと思い、基本的に使い分けていました。

もう少し調べてみると、ToLookupはその名の通りルックアップテーブルを作るメソッドで、戻されるLookupクラスは、キーからのルックアップを機能として有している。と。

ところがふと、過去にGroupByを使っていて、ToLookupを使ったほうがよいケースがあったりするんじゃないかと不安になってきまして。たとえば何も考えずにGroupByを使っていた箇所で、ToLookupを使ったほうが実はよかった。とかいうケースがあったらいやだなぁ。と。

なので、とりあえず処理時間を計ってみました。使ったのはこんなコード。

static void Main(string[] args)
{
  var rnd = new Random(DateTime.Now.Millisecond);
  var items = Enumerable.Range(0, 10000000).Select(_ => new
  {
    Key1 = rnd.Next(10),
    Key2 = rnd.Next(100),
    Value = rnd.Next(10000)
  });

  var sw = new Stopwatch();
  sw.Start();

  var dic = items.GroupBy(i => new { i.Key1, i.Key2 })
    .ToDictionary(g => g.Key, g => g.First().Value);

  sw.Stop();

  Console.WriteLine("Elapsed:{0}msec", sw.ElapsedMilliseconds);
}

先日の『ToDictionaryで重複のない辞書を作る』と同様に、コレクションからキー重複を排除した辞書を作る処理にGroupByを使ってみて、単純にGroupBy→ToLookupに置き換えたときにどれくらい処理速度の差があるか？ほんの少しGroupByが早いんじゃないかな？と予想。

結果は、
GroupBy … 6155msec。
ToLookup … 6081msec。
となり、予想に反してほんの誤差レベルとはいえGroupByのほうが遅い結果に。なんでだろう？と思ってソースコードを調べてみた。

GroupByは大体こんな感じ。

public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(
  this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
  return new GroupedEnumerable<TSource, TKey, TSource>(
    source, keySelector, IdentityFunction<TSource>.Instance, null);
}

internal class GroupedEnumerable<TSource, TKey, TElement>
  : IEnumerable<IGrouping<TKey, TElement>>
{
  public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator()
  {
    return Lookup<TKey, TElement>.Create<TSource>(
      source, keySelector, elementSelector, comparer).GetEnumerator();
  }
}

それに対して、ToLookupはこんな感じ。

public static ILookup<TKey, TSource> ToLookup<TSource, TKey>(
  this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
  return Lookup<TKey, TSource>.Create(
    source, keySelector, IdentityFunction<TSource>.Instance, null);
}

あー。これだとほぼ即時実行か遅延実行かの違いしかないですねぇ。これならToLookupが若干速いのも納得できる。

というか、そうするとGroupByの存在意義が解らなくなったので、ちょっと調べてみたら、Stackoverflowに「Why are ToLookup and GroupBy different?」こんな質問があって、その回答が以下。

What happens when you call ToLookup on an object representing a remote database table with a billion rows in it?

なるほど。例えばデータソースがObjectではなくDatabaseだったりしたときに、即時実行しないで済むならそうしたい。LINQのメソッドはデータソースを問わないわけだから、基本的にはGroupByを使い、明示的に即時実行にしたい場合や、実行後のルックアップが必要なら、ToLookupを使うべし。と、解釈して納得できた。

気にしなければならない速度差では全くないですしね。