【.Net C#】多次元配列、ジャグ配列、List<T> この中で一番速いのは?速さと使いやすさを両立しているのはどれ?

この記事では .Net Framework と C# の、多次元配列、ジャグ配列、List<T> について記載しています。

結論

多次元配列、ジャグ配列、List<T> の中で、
アクセス(get/set)スピードが最も優れているのは、ジャグ配列です。
速さと使いやすさを両立できるのは List<T> です。

多次元配列

エクセルのような、縦と横の2次元配列で表現できそうなデータを管理しよう!となった場合、C# にはそのまんま、多次元配列という仕組みがあるので、多次元配列で実装しようと考えます。

//多次元(ここでは2次元)配列の宣言
string[,] cells = new string[100,100];

//51行目、21桁目のセルに hogehoge を代入
cells[50,20] = "hogehoge";

直感的で分かりやすいのですが、多次元配列には重大な欠陥があります。
問題点は、Unity マニュアルの最適化のページに記載されています。

すごく簡単に言うと、

死ぬほど遅い!

どれが速いのか計測してみた

じゃあ、Unity 以外の .Net のバージョンでも、同じ結果になるのか?は、実際に速度を測ってみないと分かりません。
同じバージョンの .Net を使っても、Win64 と IOS で同じ結果になるのか?も分かりません。

ということで、

.Net Framework 4.8.3
C# 5
Windows 10(64bit)

という条件で速度比較をしてみました。

結果は

速い ジャグ配列 > List<T> > 多次元配列 遅い

Unity に限らず、多次元配列が遅いことは変わりませんでした。

集計データを Google Spreadsheet にまとめているので、興味がある方はご覧ください。

Windows 10 以外の環境がないので、他の OS でも同じ結果になるのかは分かりません。

ジャグ配列

アクセススピードが最も優れている、ジャグ配列は以下のように使います。

//ジャグ配列の宣言
string[][] cells = new string[][]{ new string[3], new string[3] };

//1行目2桁目に hogehoge を代入
cells[0][1] = "hogehoge";

ジャグ配列に限らず、配列の問題点は、配列のサイズが変わる場合、その処理を作る手間です。
配列のサイズを変える場合、以下の処理を作る必要があります。

・新しいサイズの配列を作成
・サイズが増える場合
 元の配列の全ての要素を新しい配列にコピーして、増えた分を初期値で埋める。
・サイズが減る場合
 元の配列から新しいサイズ分の要素を新しい配列にコピーする。

単純にコピーに時間がかかります。
この時間がバカにならないので、ゲームだとなんでもかんでも上限をつけて、サイズが変わらないようにするのが常套手段です。
サイズが変わらないようにする理由は他にもありますが、長くなるのでここでは割愛します。

List<T>

サイズが変わってもそこそこのパフォーマンスを出せるようにするには、List<T> を使います。

//二次元目の要素を追加
List<List<int>> cells = new List<List<int>>();

//一次元目の要素を追加
cells.Add(new List<int>());

//[0]に二次元目の要素を追加しつつ、0 を代入
//cells[0][0] = 0 になった
cells[0].Add(0);

//一次元目の要素を追加
//cells[1] が追加される
cells.Add(new List<int>());

cells[1].Add(0); //[1]に[0]を追加しつつ 0 を代入
cells[1].Add(1); //[1]に[1]を追加しつつ 1 を代入

ジャグ配列よりも、ちょっと使い方が分かりにくいです。

List<T> は、配列のように最初に決まったサイズを確保するわけではなく、必要に応じて Add() で要素を追加していくものです。
配列と違って、サイズを変更しても要素の全コピーは発生しません。
アクセススピードはジャグ配列よりも若干劣りますが、要素の追加と削除のしやすさを考えると、これくらいのロスは許せるかな?というレベルです。
むしろ、リスト構造でよくここまでのパフォーマンスを出せているなぁ…と惚れ惚れするレベルです。

配列のように使いたい場合、インスタンスを生成したあと、以下のように初期化します。

List<List<int>> cells = new List<List<int>>();

//[100][100]の要素を確保し、0 で初期化
for (int i = 0; i < 100; i++) cells.Add(new List<int>()); //一次元目を確保
for (int i = 0; i < 100; i++) {
	for (int j = 0; j < 100; j++) cells[i].Add(0); //二次元目を確保しながら 0 を代入
}

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です