LINQの遅延評価とキャッシング

C#

C#3.0からLINQという機能が加わったのはいまさらですが、まだ知らない部分があったので今回はそれを紹介します。
ちなみにLINQの基礎的な部分はここでは解説しないので別サイトを参照してください。


まずLINQでは遅延評価というものが行われます。lazy listと言ったりもします。
遅延評価を超簡単に説明すると、値が実際に必要とされるまで実行を先延ばしして処理にかかる時間を分散させることができる仕組みです。
この辺も詳しく説明されているサイトが別にあるので、詳しく知りたい方は頑張って探してね。


遅延評価が行われる構造の場合、二度同じ部分の値が必要になったとき、
一度目は実行して値を求めるのですが二度目は一度目の値を保存しておきそれをすぐに返すということをします。
これをキャッシングと言ったりするのですが、実はLINQの遅延評価の構造ではキャッシングが行われません。
つまり二度同じ部分の値を参照した場合、二度とも実行されます。

System.Diagnostics.Stopwatch sw =  System.Diagnostics.Stopwatch.StartNew();
IEnumerable<int> list = Enumerable.Range(0, 100).Where((num) => 
	{
		System.Threading.Thread.Sleep(10);
		return num % 2 == 0;
	});
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds.ToString());

sw.Reset();
sw.Start();
foreach (int i in list)
	i.ToString();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds.ToString());

sw.Reset();
sw.Start();
foreach (int i in list)
	i.ToString();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds.ToString());

これの実行結果は
1
1074
1074
となりました（僕の環境では)。


この結果から、一つ目の出力のWhereを使って0〜100までの偶数のリストを作っているようにみえる部分では実はまだ実行はされていないことがわかります。
そして、二つ目の出力で実際に必要になったときに実際に実行が行われていることがわかります。
最後に、三つ目の出力から一度行った実行をキャッシングしているのではなく再実行をしていることがわかります。


これでは単なる二度手間なのでこれを回避する方法ももちろんあります。

System.Diagnostics.Stopwatch sw =  System.Diagnostics.Stopwatch.StartNew();
IEnumerable<int> list = Enumerable.Range(0, 100).Where((num) => 
	{
		System.Threading.Thread.Sleep(10);
		return num % 2 == 0;
	}).ToList();//ここでリストに変換
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds.ToString());

sw.Reset();
sw.Start();
foreach (int i in list)
	i.ToString();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds.ToString());

sw.Reset();
sw.Start();
foreach (int i in list)
	i.ToString();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds.ToString());

最初の例からの変更点は、コメントでも書いているようにWhereの結果をそのままものすのではなくリストに変換して戻してやります。
これの実行結果は、
1075
0
0
のようになりました。


この実行結果からToList() (ToArray()などでもいい)で変換したタイミングで一度実行が行われ、
それ以降実際に値を利用するときは実行が行われていないことがわかります。


このような結果から、複数回値を利用する場合は一度ToList()などで変換してそれを使った方がいいでしょう。


で、ここまででLINQの遅延評価とキャッシングについては終わりです。
終りなのですが、もう少し書きたいことがあるので続けます。


まずはコードを示します。（あくまでも例なのでやっていることに大した意味はありません）

int count = 0;
Action<IEnumerable<int>> action = null;
action = (list) =>
	{
		if (count++ > 1000)
			return;
		else
		{
			System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
			int num = list.Count();
			sw.Stop();

			writer.WriteLine(num.ToString() + "," + sw.ElapsedMilliseconds.ToString()); //csvファイルとして保存している
			//再帰呼び出しを行っている
			action(list.Skip(0));//list.Skip(0)がLINQのメソッド
		}
	};
action(Enumerable.Range(0, 10000));

この結果を図にして示します。


list.Count()で得られる数は変更を行っていないので常に一定です。
ですが回数を重ねるごとに(再帰が深くなるほどに)list.Count()の処理にかかる時間が増えています。
かなり上下にぶれはありますがだいたい線形で増加しています。


これについてちゃんとした検証をしていないのであくまで推測なのですが、
Count()でlistの要素の数えるためにはlistがちゃんとした実態を持っていないといけません。
つまりLINQで生成したlistの場合まだ評価が行われていないので、いったんLINQを実行してそのあとCount()で数を数えます。
ですが今回の例は再帰を使っています。
つまりLINQを実行する元になるIEnumerable型のlistも遅延評価のためにまだLINQの実行が行われていない可能性があります。
その場合その元になるlistももちろんLINQを実行しなければなりません。ですがさらにその元になるlistも遅延評価のためまだ実行が行われていない可能性が...以下略。


このように再帰が深くなっていくにつれ、未実行のlistも増えていきます。
なので図のように線形に計測にかかる時間が増えていったと予想されます（本当にあくまで予想です）。


これでは使いにくいので修正しましょう。

action(list.Skip(0).ToList());//LINQを実行したものを再帰の引数として渡す

修正したのは再帰呼び出しをしている一か所だけです。
コメントとして書いているように、変更内容は再帰の引数として渡すlistにToList()をすることによってLINQが実行済みの形に変更するだけです。
結果は乗せるまでもないですが一応、

すべて０です。
この図から、どんなに再帰が深くなったとしても処理が定数時間で終わっていることがわかります。


以上で今回の内容はすべて終了です。
結論は、
LINQを使うときは遅延評価であることを忘れずにさらにキャッシングが行われないということにも気をつけよう。
という感じですね。


それでは最後にこれに気づくことになったプログラムを乗っけて終わります。
内容はエラトステネスの篩をLINQを使ってうまいこと実装できないだろうかというような感じですが、結局満足のいくコードはできませんでした。
ちなみに高速化とか省メモリとか一切考えてないのでその辺の突っ込みはナシで。

Func<int, IList<int>> sieveOfEratoshtenes = (max) =>
	{
		List<int> acc = new List<int>();
		if (max > 1)
		{
			Action<IEnumerable<int>> sieve = null;
			sieve = (list) =>
				{
					if (list.Count() == 0)
						return;
					int head = list.First();
					acc.Add(head);
					sieve(list.Skip(1).Where((num) => num % head != 0).ToList());
				};

			sieve(Enumerable.Range(2, max - 1));
		}
		return acc;
	};

IList<int> primes = sieveOfEratoshtenes(100);
foreach (int num in primes)
	Console.WriteLine(num.ToString());