🦆
[C#]多次元配列・ジャグ配列・リスト、行列積で最もパフォーマンスが高いのはどれ?
行列の掛け算を効率化したい場合、どのようなコレクションを選ぶべきでしょうか?
先人が築いた素晴らしいライブラリを用いるため普段は意識しないことですが、ふと気になったので簡単な比較を行いました。
結論、行列の掛け算のアルゴリズム、実験内容、実験結果の順に書いていきます。
2022/11/22 タイトル変更
旧タイトル:行列計算のための配列のパフォーマンス比較
(結論)パフォーマンスはジャグ配列が最速、二番手が配列inリスト、多次元配列が意外と遅かった
今回の実験内容をパフォーマンスが良かった順に記しました。同じことをしていてもパフォーマンスに差があるのが面白いですね。
| コレクション | 1回目 | 2回目 | 3回目 | 4回目 | 5回目 |
|---|---|---|---|---|---|
| 2次元配列 | 0.799 sec | 0.664 | 0.645 | 0.643 | 0.643 |
| ジャグ配列 | 0.365 | 0.318 | 0.317 | 0.313 | 0.316 |
| ジャグ配列の転置 | 0.374 | 0.321 | 0.313 | 0.312 | 0.314 |
| リストinリスト | 0.927 | 0.808 | 0.818 | 0.818 | 0.812 |
| 配列inリスト | 0.610 | 0.511 | 0.515 | 0.511 | 0.513 |
| 自作クラス | 1.37 | 1.02 | 1.00 | 1.01 | 1.01 |
自作クラスがダントツでビリでした。今回紹介していないSpna<T>構造体まで使ったのに圧倒的に遅かったです。勉強不足です。
行列の掛け算のアルゴリズム
データ構造の違いがパフォーマンスに影響を与える理由を考えるため、計算方法と計算量を調べます。
まずは具体例として、今回の実験の計算式を下記に記します。
行列の掛け算の要素の一般式は下記になります。
ここで行列
- 行列
A i B j -
k -
k
-
-
N M
これより、行列の掛け算の計算回数は下記になります。
特に正方行列同士の掛け算の場合
実験内容
前述した具体例の計算を100万回繰り返して計算時間を調べます。
1 多次元配列
直観的な分かりやすさや配列の要素数の安定性を考えると、最初は多次元配列で掛け算メソッドを作成すると思います。
/// <summary>
/// 2次元の多重配列で、掛け算のパフォーマンスを測定する
/// </summary>
public static TimeSpan Array2dPerformanceForMatrix()
{
// 配列の初期化
double[,] A = new double[3, 2]
{
{1,5 },
{1,1 },
{4,4 }
}; // 掛けられる数
double[,] B = new double[2, 3]
{
{8,1,0 },
{3,1,5 }
}; // 掛ける数
var sw = new System.Diagnostics.Stopwatch(); // Stopwatchクラス生成
// 掛け算の計算
sw.Start();
double[,] C = new double[3, 3]; // 掛け算の答え
for (int i = 0; i < A.GetLength(0); i++)
{
for (int j = 0; j < B.GetLength(1); j++)
{
for (int k = 0; k < A.GetLength(1); k++)
{
C[i, j] += A[i, k] * B[k, j];
}
}
}
sw.Stop();
return sw.Elapsed;
}
2 ジャグ配列
C#の勉強を始めたころは、なんだこいつは、準備も面倒だし要素数も簡単に変えられる危ないじゃないか、多次元配列ではいかんのかと思っていました。
/// <summary>
/// ジャグ配列で、掛け算のパフォーマンスを測定する
/// </summary>
public static TimeSpan JagArrayPerformanceForMatrix()
{
// 配列の初期化
double[][] A = new double[3][];// 掛けられる数
A[0] = new double[2] { 1, 5 };
A[1] = new double[2] { 1, 1 };
A[2] = new double[2] { 4, 4 };
double[][] B = new double[2][]; // 掛ける数
B[0] = new double[3] { 8, 1, 0 };
B[1] = new double[3] { 3, 1, 5 };
var sw = new System.Diagnostics.Stopwatch(); // Stopwatchクラス生成
// 掛け算の計算
sw.Start();
double[][] C = new double[3][]; // 掛け算の答え
C[0] = new double[3];
C[1] = new double[3];
C[2] = new double[3];
for (int i = 0; i < A.Length; i++)
{
for (int j = 0; j < B[0].Length; j++)
{
for (int k = 0; k < A[0].Length; k++)
{
C[i][j] += A[i][k] * B[k][j];
}
}
}
sw.Stop();
return sw.Elapsed;
}
3 ジャグ配列の転置
掛け算のかける数の行列を転置します。転置を考慮すると掛け算の要素の一般式は下記のようになります。
掛ける数の要素数だけデータを書き込む回数が増えるので不利に見えますが、「C# 配列 計算速度」などでググったときに出てくる速度改善の恩恵のほうが大きいです。
/// <summary>
/// ジャグ配列の転置で、掛け算のパフォーマンスを測定する
/// </summary>
public static TimeSpan JagArrayTransposedPerformanceForMatrix()
{
// 配列の初期化
double[][] A = new double[3][];// 掛けられる数
A[0] = new double[2] { 1, 5 };
A[1] = new double[2] { 1, 1 };
A[2] = new double[2] { 4, 4 };
double[][] B = new double[2][]; // 掛ける数
B[0] = new double[3] { 8, 1, 0 };
B[1] = new double[3] { 3, 1, 5 };
double[][] BT = new double[B[0].Length][]; // 掛ける数の転置
BT[0] = new double[B.Length];
BT[1] = new double[B.Length];
BT[2] = new double[B.Length];
var sw = new System.Diagnostics.Stopwatch(); // Stopwatchクラス生成
// 掛け算の計算
sw.Start();
double[][] C = new double[3][]; // 掛け算の答え
C[0] = new double[3];
C[1] = new double[3];
C[2] = new double[3];
// 掛ける数の転置
for (int i = 0; i < BT.Length; i++)
{
for (int j = 0; j < BT[i].Length; j++)
{
BT[i][j] = B[j][i];
}
}
// 掛け算
for (int i = 0; i < A.Length; i++)
{
for (int j = 0; j < BT.Length; j++)
{
for (int k = 0; k < A[0].Length; k++)
{
C[i][j] += A[i][k] * BT[j][k];
}
}
}
sw.Stop();
return sw.Elapsed;
}
4 リストinリスト
比較用です。コレクションの速度を調べるとリストは配列より遅いと言われています。
public static TimeSpan ListInListPerformanceForMatrix()
{
// 配列の初期化
List<List<double>> A = new List<List<double>>();
A.Add(new List<double>()); A[0].Add(1); A[0].Add(5);
A.Add(new List<double>()); A[1].Add(1); A[1].Add(1);
A.Add(new List<double>()); A[2].Add(4); A[2].Add(4);
List<List<double>> B = new List<List<double>>();
B.Add(new List<double>()); B[0].Add(8); B[0].Add(1); B[0].Add(0);
B.Add(new List<double>()); B[1].Add(3); B[1].Add(1); B[1].Add(5);
var sw = new System.Diagnostics.Stopwatch(); // Stopwatchクラス生成
// 掛け算の計算
sw.Start();
List<List<double>> C = new List<List<double>>();
C.Add(new List<double>()); C[0].Add(0); C[0].Add(0); C[0].Add(0);
C.Add(new List<double>()); C[1].Add(0); C[1].Add(0); C[1].Add(0);
C.Add(new List<double>()); C[2].Add(0); C[2].Add(0); C[2].Add(0);
for (int i = 0; i < A.Count; i++)
{
for (int j = 0; j < B[0].Count; j++)
{
for (int k = 0; k < A[0].Count; k++)
{
C[i][j] += A[i][k] * B[k][j];
}
}
}
sw.Stop();
return sw.Elapsed;
}
5 配列inリスト
リストの中に配列を入れると速度はどうなるのか気になりました。
/// <summary>
/// リストの中に配列を入れたもので、掛け算のパフォーマンスを測定する
/// </summary>
/// <returns></returns>
public static TimeSpan ArrayInListPerformanceForMatrix()
{
// 配列の初期化
List<double[]> A = new List<double[]>();
A.Add(new double[2] { 1, 5 });
A.Add(new double[2] { 1, 1 });
A.Add(new double[2] { 4, 4 });
List<double[]> B = new List<double[]>();
B.Add(new double[3] { 8, 1, 0 });
B.Add(new double[3] { 3, 1, 5 });
var sw = new System.Diagnostics.Stopwatch(); // Stopwatchクラス生成
// 掛け算の計算
sw.Start();
List<double[]> C = new List<double[]>();
C.Add(new double[3]);
C.Add(new double[3]);
C.Add(new double[3]);
for (int i = 0; i < A.Count; i++)
{
for (int j = 0; j < B[0].Length; j++)
{
for (int k = 0; k < A[0].Length; k++)
{
C[i][j] += A[i][k] * B[k][j];
}
}
}
sw.Stop();
return sw.Elapsed;
}
6 自作クラス
計算パッケージを作成していまして、自作クラスのパフォーマンスも調べました。
using Tremendous1192.SelfEmployed.MyMathematicalToolsNet;
namespace YourNameSpace
{
public class Tester
{
/// <summary>
/// 自作の行列クラスで、掛け算のパフォーマンスを測定する。
/// 自作クラスはGitHub上にあるので、不要な場合、このメソッドは削除してください。
/// </summary>
public static TimeSpan MyMatrixPerformanceForMatrix()
{
// 配列の初期化
Matrix A = new Matrix(3, 2); // 掛けられる数
A[0, 0] = 1; A[0, 1] = 5;
A[1, 0] = 1; A[1, 1] = 1;
A[2, 0] = 4; A[2, 1] = 4;
Matrix B = new Matrix(2, 3); // 掛ける数
B[0, 0] = 8; B[0, 1] = 1; B[0, 2] = 0;
B[1, 0] = 3; B[1, 1] = 1; B[1, 2] = 5;
var sw = new System.Diagnostics.Stopwatch(); // Stopwatchクラス生成
// 掛け算の計算
sw.Start();
Matrix C = A * B; // 掛け算の答え
sw.Stop();
return sw.Elapsed;
}
}
}
検証方法
各計算メソッドを100万回実行して計算時間の和を記録する。
コンパイルごとに処理時間が異なるので、これを5回繰り返します。
public static void Test()
{
TimeSpan array2D = TimeSpan.Zero;
TimeSpan arrayJag = TimeSpan.Zero;
TimeSpan arrayJagT = TimeSpan.Zero;
TimeSpan arrayList = TimeSpan.Zero;
TimeSpan arrayInList = TimeSpan.Zero;
TimeSpan arrayMyClass = TimeSpan.Zero;
int loopMax = 1000000;
for (int loop = 0; loop < loopMax; loop++)
{
array2D += Sandbox.Tremendous1192.SelfEmployed.MyMathematicalToolsNet.Zenn.Array2dPerformanceForMatrix();
arrayJag += Sandbox.Tremendous1192.SelfEmployed.MyMathematicalToolsNet.Zenn.JagArrayPerformanceForMatrix();
arrayJagT += Sandbox.Tremendous1192.SelfEmployed.MyMathematicalToolsNet.Zenn.JagArrayTransposedPerformanceForMatrix();
arrayList += Sandbox.Tremendous1192.SelfEmployed.MyMathematicalToolsNet.Zenn.ListInListPerformanceForMatrix();
arrayInList += Sandbox.Tremendous1192.SelfEmployed.MyMathematicalToolsNet.Zenn.ArrayInListPerformanceForMatrix();
arrayMyClass += Sandbox.Tremendous1192.SelfEmployed.MyMathematicalToolsNet.Zenn.MyMatrixPerformanceForMatrix();
}
Console.WriteLine("2次元配列\t" + array2D);
Console.WriteLine("ジャグ配列\t" + arrayJag);
Console.WriteLine("ジャグ配列の転置\t" + arrayJagT);
Console.WriteLine("リストの中にリスト\t" + arrayList);
Console.WriteLine("リストの中に配列\t" + arrayInList);
Console.WriteLine("自作クラス\t" + arrayMyClass);
}
実験結果
ジャグ配列が圧倒的に早いですね。行列の構造が破壊されないように守る必要はありますが、十分おつりがくるでしょう。リストの中に配列を格納するのが意外と早かったです。参照型が効いているんですかね?
| コレクション | 1回目 | 2回目 | 3回目 | 4回目 | 5回目 |
|---|---|---|---|---|---|
| 2次元配列 | 0.799 sec | 0.664 | 0.645 | 0.643 | 0.643 |
| ジャグ配列 | 0.365 | 0.318 | 0.317 | 0.313 | 0.316 |
| ジャグ配列の転置 | 0.374 | 0.321 | 0.313 | 0.312 | 0.314 |
| リストinリスト | 0.927 | 0.808 | 0.818 | 0.818 | 0.812 |
| 配列inリスト | 0.610 | 0.511 | 0.515 | 0.511 | 0.513 |
| 自作クラス | 1.37 | 1.02 | 1.00 | 1.01 | 1.01 |
終わりに
行列の掛け算を効率化したい場合、どのようなコレクションを選ぶべきか、簡単な比較を行いました。ジャグ配列が圧倒的に早いです。
今回は行列の掛け算をお題に調べましたが、それ以外のタスクでも、ジャグ配列を使えるところでは積極的に使用したいと思いました。
Discussion