【Unity】【C#】LINQとfor, ListとArray(配列)での実行速度を比較してみる

　LINQ や List はとても便利だけど、実行速度が遅いという欠点があるので、改めてよく使いそうなコードで比較してみたのを記録しておく。

　私はよくこういう実験をするのだが、気をつけて欲しいのは実行環境やマシンスペック、言語などによっても結果は異なるという点だ。また、コンパイラ等もバージョンによって最適化が入ったりして、高速になる場合もある。今回は C# で Unity 上（主にエディタ上）での実験になってるが、実機ではまた異なる結果が出る場合があるので、あくまでも目安として考えて欲しい。

　ちなみに元ネタではないが、以下の記事でも通常の for, foreach 構文と LINQ の ForEach を実験しているが、特に ForEach が遅かったのが記憶に残っていたので、改めて調べたキッカケだったりする（記事のバージョンが古いので）。だがしかし、現64bitバージョンでも値は２倍速くらいになっているが、結果（比率）は同じだった。例えば for に対してLNQ の ForEach はやはり２倍くらい遅い。こういったデータを公開してくれるのは非常に有り難い。

（参考）
・【Unity】ループ構文の処理速度の検証結果
・CPU のパフォーマンスに関する推奨事項：コストのかかる操作を避ける - LINQ を使わないようにする

■LINQ と for 構文で比較
　●LINQ の ForEach と for の単純アクセス（値取り出し）比較
　●LINQ と for でフィルタ（抽出）の比較
　●LINQ と for で全要素文字列変換の比較
■List と Array(配列)で比較
　●単純なアクセス（値取り出し）の比較
　●ソートの比較
　●シャッフル（Fisher-Yates shuffle）の比較
■結果一覧

(※) Unity 2018.2.1f1（エディタ上）.NET 3.5 / Windows10(x64), Intel Core i5 x64 2.9GHz で確認

---

■LINQ と for 構文で比較

　ここでは簡単な数値計算でのフィルタと、全要素の文字列を LINQ と単純な for で比較してみよう。データには List を使っているが、Array（配列）にした方が速くなるのはとりあえず置いておいて欲しい(笑)。

　実際の測定方法は以下のコードを１つのメソッドにして、11回実行し、はじめの1回の結果を捨て、残りの10回の平均を出している。なぜはじめの1回を捨ててるかというと、アプリを起動したときには色々な初期化処理が動くので重くなり、測定値が不安定になるからだ（だいたい通常より値が大きくなる）。Unity に限らず、他のプラットフォームでも同じことがよく起こるので、その辺は覚えておくと良いかも知れない。

---

●LINQ の ForEach と for の単純アクセス（値取り出し）比較

　例えば、順次アクセスしていって、値を取り出すだけのコードを比較してみた。通常はその値を何らかで利用すると考えて欲しい。

①LINQ で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

list.ForEach(i => {
    int value = list[i];
});

float elapsed = Time.realtimeSinceStartup - startTime;

Debug.Log("1 : " + elapsed + " [s]"); //0.002561998 [s]

②for で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < num; i++)
{
    int value = list[i];
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.001707292 [s]

1 : 0.002561998 [s]
2 : 0.001707292 [s]

　ただ値を取り出しただけで何もしてないが、実行速度は LINQ に比べて for は約1.5倍くらい速かった。要素数が少ないとき（50以下とか）にはあまり気にすることはないとは思うが、要素数が大きくなるほど、その差は大きく出る。大量のデータをスキャン、または変換など処理を施すのには LINQ はとても遅いので気をつけよう（プロコン問題などに使うとタイムアウトすることが多い(笑)）。
※List を配列にした方がもっと速い（約3.1倍：0.0008201599 [s]）。

---

●LINQ と for でフィルタ（抽出）の比較

　例えば、連続した値の要素から、偶数だけを抽出するコードを比較してみた。

①LINQ で書いた場合

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

//前準備
int num = 10000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

List<int> list2 = list.Where(e => e % 2 == 0).ToList();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]"); //0.0007956981 [s]

②for で書いた場合

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

//前準備
int num = 10000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

List<int> list2 = new List<int>(num);
for (int i = 0; i < num; i++)
{
    int value = list[i];
    if (value % 2 == 0)
        list2.Add(value);
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.0002808333 [s]

1 : 0.0007956981 [s]
2 : 0.0002808333 [s]

　測定部分では、LINQ はとてもシンプルで、for 文は長々と書いている感じだが、実行速度は LINQ に比べて、単純な for の方が約2.8倍くらい速かった(笑)。特に要素数が大きいときにはこの傾向は強くなる。for 文は昔ながらのとてもダサい(笑)文に見えるが、実は高速なので、Unity のようなフレームアプリケーションには向いているかも知れない(笑)。

---

●LINQ と for で全要素文字列変換の比較

　例えば、一定の文字列があり、それらを全部小文字にするコードを比較してみた（100個書くのが面倒くさい(笑)ので 10個x10=100個にしている）。

①Linq で書いた場合

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

//前準備
string[] words = {
    "Apple", "Banana", "Candy", "Doughnut", "Egg",
    "Fish", "Grape", "Honey", "IceCream", "Jelly"
};
List<string> list = Enumerable.Repeat(words, 10).SelectMany(a => a).ToList(); //10x10=100個
int num = 1000;

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < num; i++)
{
    List<string> list2 = list.Select(e => e.ToLower()).ToList();
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]"); //0.04769385 [s]

②for で書いた場合

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

//前準備
string[] words = {
    "Apple", "Banana", "Candy", "Doughnut", "Egg",
    "Fish", "Grape", "Honey", "IceCream", "Jelly"
};
List<string> list = Enumerable.Repeat(words, 10).SelectMany(a => a).ToList(); //10x10=100個
int num = 1000;

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < num; i++)
{
    int length = list.Count;
    List<string> list2 = new List<string>(length);
    for (int j = 0; j < length; j++)
    {
        list2.Add(list[j].ToLower());
    }
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.03735647 [s]

1 : 0.04769385 [s]
2 : 0.03735647 [s]

　測定部分では、for 文の方では list.Count を length に入れて使っているが、こうすると、ループのたびにプロパティを読み出しに行かなくて済むため、ほんのわずかだが速くなる。生成された list2 の方は特に何も使ってないが、通常は何か処理が入ると考えて欲しい。

　結果はだいたい、LINQ より for で書いたほうが約1.3倍くらい速くなった。思ったより速度は変わらないね。要素数が少ないなら、どちらを使っても良さそう。

　ちなみに for の例で List を全て Array で書き直すとわずかに速くなる（約1.4倍：0.03489325 [s]）。

---

■List と Array（配列）で比較

　ここではデータ格納先となる List と Array（配列）で速度を比較してみよう。

　これも同じ様に、11回実行し、はじめの1回の結果を捨て、残りの10回の平均を出した測定値だ。単純なものしか書いてないが、実際には何らかの処理が他に入ると考えて欲しい。

---

●単純なアクセス（値取り出し）の比較

　例えば、順次アクセスしていって、値を取り出すだけのコードを比較してみた。通常はその値を何らかで利用すると考えて欲しい。

①List で書いた場合

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

//前準備
int num = 100000;
List list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < list.Count; i++)
{
    int value = list[i];
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]"); //0.00246439 [s]

②Array で書いた場合

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

//前準備
int num = 100000;
int[] array = Enumerable.Range(0, num).ToArray();

//以下を測定
float startTime = Time.realtimeSinceStartup;

for (int i = 0; i < array.Length; i++)
{
    int value = array[i];
}

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]"); //0.0008202791 [s]

1 : 0.00246439 [s]
2 : 0.0008202791 [s]

　ただ値を取り出しただけで何もしてないが、実行速度は List に比べて Array（配列）は約3.1倍くらい速かった(笑)。これも要素数が大きくなるほど、その傾向が強くなる。ライブラリ関数も配列を返すものが多いが、もしかしたらその利用の実行速度のためであるかも知れない(笑)。

　ちなみに、二分探索の Array.BinarySearch と List.BinarySearch を比較してみると、要素数が多くなっても、ほとんど違いが出ないようだ。つまりアクセス回数に比例して速度が落ちていることがわかる。

---

●ソートの比較

　例えば、標準関数にあるソートで比較してみた。

①List で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();
list.Reverse();

//以下を測定
float startTime = Time.realtimeSinceStartup;

list.Sort();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]");  //0.00460794 [s]

②Array（配列）で書いた場合

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

//前準備
int num = 100000;
int[] array = Enumerable.Range(0, num).ToArray();
Array.Reverse(array);

//以下を測定
float startTime = Time.realtimeSinceStartup;

Array.Sort(array);

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]");  //0.002492619 [s]

1 : 0.00460794 [s]
2 : 0.002492619 [s]

　結果は List に比べて Array（配列）でのソートの方が約1.8倍くらい速かった。

　実際には C# のソートは要素数によってアルゴリズムが変わると聞いたことがあるので（例えばクイックソートは要素数が多いときはパフォーマンス良いが、要素数が少ないときは、それほど良くないと言われているので、アルゴリズムを変えるのは有効である）、利用する場合は一度実験しておく方が良いかも知れない。

・50以下挿入ソート、5万以下マージソート、あとはクイックソート

　ちなみに、Reverse（要素の反転）の代わりに、後述するシャッフルを使った場合、以下のようになった。

1 : 0.007369685 [s]
2 : 0.003433919 [s]

　比率としては約2.1倍である。誤差を含めて約2倍と考えても良いだろう。

---

●シャッフル（Fisher-Yates shuffle）の比較

　例えば、Fisher-Yates アルゴリズムを用いたシャッフル関数を定義し、それを利用して比較してみた。

①List で書いた場合

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

//前準備
int num = 100000;
List<int> list = Enumerable.Range(0, num).ToList();

//以下を測定
float startTime = Time.realtimeSinceStartup;

list.Shuffle();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("1 : " + elapsed + " [s]");  //0.00126977 [s]


//拡張メソッドを定義
public static class Extensions
{
    //リストの要素をシャッフルする (Fisher-Yates shuffle)
    public static void Shuffle<T>(this List<T> list)
    {
        for (int i = list.Count - 1; i > 0; i--)
        {
            int j = Random.Range(0, i + 1);  //[0]～[i]
            list.Swap(i, j);
        }
    }

    //要素のスワップ
    public static void Swap<T>(this List<T> list, int i, int j)
    {
        T tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }
}

②Array（配列）で書いた場合

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

//前準備
int num = 100000;
int[] array = Enumerable.Range(0, num).ToArray();

//以下を測定
float startTime = Time.realtimeSinceStartup;

array.Shuffle();

float elapsed = Time.realtimeSinceStartup - startTime;
Debug.Log("2 : " + elapsed + " [s]");  //0.0006387234 [s]


//拡張メソッドを定義
public static class Extensions
{
    //配列の要素をシャッフルする (Fisher-Yates shuffle)
    public static void Shuffle<T>(this T[] arr)
    {
        for (int i = arr.Length - 1; i > 0; i--)
        {
            int j = Random.Range(0, i + 1);  //[0]～[i]
            arr.Swap(i, j);
        }
    }

    //要素のスワップ
    public static void Swap<T>(this T[] arr, int i, int j)
    {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

1 : 0.00126977 [s]
2 : 0.0006387234 [s]

　このシャッフルは以前に書いたコードそのままである。

　結果は List に比べて Array（配列）でのソートの方が約1.9倍くらい速かった。

　これも誤差を含めて約2倍と考えても良いだろう。

---

■結果一覧

　以上をまとめると表のようになる。

●LINQ と for 構文での比較

処理内容	実装方法	測定時間	備考
単純なアクセス	LINQ	0.002561998 [s]
	for	0.001707292 [s]	LINQ より約1.5倍速い
フィルタ(抽出)	LINQ	0.0007956981 [s]
	for	0.0002808333 [s]	LINQ より約2.8倍速い
全要素文字列変換	LINQ	0.04769385 [s]
	for	0.03735647 [s]	LINQ より約1.3倍速い

●List と Array(配列)で比較

処理内容	実装方法	測定時間	備考
単純なアクセス	List	0.00246439 [s]
	配列	0.0008202791 [s]	List より約3.1倍速い
ソート	List	0.00460794 [s]
	配列	0.002492619 [s]	List より約1.8倍速い
シャッフル	List	0.00126977 [s]
	配列	0.0006387234 [s]	List より約1.9倍速い

　今回は単純な反復での比較しかしてないが、他にもアルゴリズムも絡めると実行速度はまた変わる。しかしそれらは言語でも異なるので注意しよう。例えば C#, Java などは文字列操作は遅いが、Ruby, PHP, Perl などは文字列操作はとても速い（=変換も速い）。実際に「数値の桁数を求める」問題があったとして、C#, Java などでは「10で割って数をかぞえる」アルゴリズムが速いが、Ruby, PHP などは「文字列に変換して長さで数える」方が速かったりする。こういったものは測定してみないとわからない。

　プロコン問題（競技プログラミング：AtCoderとか）とか見てても、上のランクほど、for, while, 配列だけで解いている場合が多いのも納得がいく。やはり 0.1秒で合否が分かれる問題などでは（10万件のデータを2秒以内に処理するプログラムとか普通なので）、LINQ や List では遅すぎるというのは体験的に知っているのだろう（事実、大量のデータを処理するには LINQ は向いてないと思う※今後のバージョンアップで改善されるかも知れないが）。

　この結果だけ見ると「LINQ は使わないで単純な構文に」「List は使わないで配列に」のように思えてしまうが、要素数が少ないときはそれほど大差ないので（1000個を超えると結構差が出てくるが、50個以下で１回きりとかなら、それほど差は出ない）、実行速度が欲しいときに、改めて見直すのもヒントとして考えるのも良いだろう。

　Unity 公式ブログにも IL2CPP について『もしあなたが10000個の要素をもつリストをイテレートしたい場合は、Listの代わりに配列を使う方がよいでしょう。なぜならその方が生成されるC++コードがよりシンプルになり、また配列アクセスの方が単純に高速だからです。』とも書いてあるね。長さを変化させる必要が無いなら、機械的に配列にするのも良いかもね。

・Update()を10000回呼ぶ

　またそのうち色々実験したら、追加しておく(笑)。

（関連記事）
【Unity】【C#】配列・リストのシャッフル
【Java】数値の桁数を調べる（べき乗の桁数・べき乗のべき乗の桁を調べる）
【C#】２次元配列（ジャグ配列・多次元配列）のソート
【Java】２次元配列のソート
【Java】配列要素の反転(reverse)
【一覧】Java, C#, PHP, Ruby, Python, JavaScript での Math.round（四捨五入・五捨六入）比較