我注意到维度从 1 到 2047 的矩阵的计算时间超过 6 秒
从 2048 开始，它们从 44 +- 秒开始。时间如此跳跃的原因可能是什么？
对于 2047 矩阵，RAM 升至 279 MB；对于 2048，RAM 升至 1042 MB
同时，有足够的RAM，她很难只数数
using System.Diagnostics;
using System.Text;
class Program
{
static void Main(string[] args)
{
int m = 0, n = 0;
while (true)
{
Stopwatch stopwatch = new Stopwatch();
InputDate(ref m, "строк m");
InputDate(ref n, "колонок n");
int[][] matrix1 = GenerateMatrix(m, n);
int[][] matrix2 = GenerateMatrix(m, n);
int nn = GetNewDimension(ref m, ref n);
int[][] aN = Addition2SquareMatrix(matrix1, nn, m, n);
int[][] bN = Addition2SquareMatrix(matrix2, nn, m, n);
stopwatch.Start();
int[][] temp = MultiStrassen(aN, bN, nn);
stopwatch.Stop();
//OutputMatrix(matrix1);
//OutputMatrix(matrix2);
//OutputMatrix(GetSubmatrix(temp, m, n));
Console.WriteLine("\n" + stopwatch.Elapsed);
Console.ReadKey();
}
}
/// <summary>
/// Ввод количество строк и столбцов
/// </summary>
/// <param name="number">запись числа в переменную</param>
/// <param name="txt">передаваемый текст</param>
static void InputDate(ref int number, string txt)
{
do
{
Console.Write($"Введите число {txt}: ");
number = int.Parse(Console.ReadLine());
}
while (number <= 0);
}
/// <summary>
/// получаем новую степень матрицы
/// </summary>
/// <param name="m">строка</param>
/// <param name="n">столбец</param>
/// <returns>возвращаем степень матрицы</returns>
static int GetNewDimension(ref int m, ref int n) => 1 << (int)(Math.Log2(Math.Max(m, n))+1);
/// <summary>
/// Преобразуем матрицу к виду 2^n путём добавление дополнительных строк
/// </summary>
/// <param name="a">передаваемый массив</param>
/// <param name="nn">наша новая степень матрицы (размерность)</param>
/// <param name="m">количество строк</param>
/// <param name="n">количество столбцов</param>
/// <returns>возвращаем обновленную матрицу</returns>
static int[][] Addition2SquareMatrix(int[][] a, int nn, int m, int n)
{
int[][] result = new int[nn][];
for (int i = 0; i < nn; i++)
{
result[i] = new int[nn];
if (i < m)
{
for (int j = 0; j < n; j++)
{
result[i][j] = a[i][j];
}
}
}
return result;
}
/// <summary>
/// Алгоритм Штрассена
/// </summary>
/// <param name="a">1 матрица</param>
/// <param name="b">2 матрица</param>
/// <param name="n">размерность матрицы</param>
/// <returns>возвращаем результат</returns>
static int[][] MultiStrassen(int[][] a, int[][] b, int n)
{
if (n <= 64)
{
return Multiply(a, b);
}
n = n >> 1;
int[][] a11 = new int[n][];
int[][] a12 = new int[n][];
int[][] a21 = new int[n][];
int[][] a22 = new int[n][];
int[][] b11 = new int[n][];
int[][] b12 = new int[n][];
int[][] b21 = new int[n][];
int[][] b22 = new int[n][];
for (int i = 0; i < n; i++)
{
a11[i] = new int[n];
a12[i] = new int[n];
a21[i] = new int[n];
a22[i] = new int[n];
b11[i] = new int[n];
b12[i] = new int[n];
b21[i] = new int[n];
b22[i] = new int[n];
}
SplitMatrix(a, a11, a12, a21, a22);
SplitMatrix(b, b11, b12, b21, b22);
int[][] p1 = MultiStrassen(Summation(a11, a22), Summation(b11, b22), n);
int[][] p2 = MultiStrassen(Summation(a21, a22), b11, n);
int[][] p3 = MultiStrassen(a11, Subtraction(b12, b22), n);
int[][] p4 = MultiStrassen(a22, Subtraction(b21, b11), n);
int[][] p5 = MultiStrassen(Summation(a11, a12), b22, n);
int[][] p6 = MultiStrassen(Subtraction(a21, a11), Summation(b11, b12), n);
int[][] p7 = MultiStrassen(Subtraction(a12, a22), Summation(b21, b22), n);
int[][] c11 = Summation(Summation(p1, p4), Subtraction(p7, p5));
int[][] c12 = Summation(p3, p5);
int[][] c21 = Summation(p2, p4);
int[][] c22 = Summation(Subtraction(p1, p2), Summation(p3, p6));
return CollectMatrix(c11, c12, c21, c22);
}
/// <summary>
/// Разделение на матрицу на под матрицы
/// </summary>
/// <param name="a">исходная матрица</param>
/// <param name="a11">матрицы а11</param>
/// <param name="a12">матрица а12</param>
/// <param name="a21">матрица а21</param>
/// <param name="a22">матрица а22</param>
static void SplitMatrix(int[][] a, int[][] a11, int[][] a12, int[][] a21, int[][] a22)
{
int n = a.Length >> 1;
for (int i = 0; i < n; i++)
{
Array.Copy(a[i], 0, a11[i], 0, n);
Array.Copy(a[i], n, a12[i], 0, n);
Array.Copy(a[i + n], 0, a21[i], 0, n);
Array.Copy(a[i + n], n, a22[i], 0, n);
}
}
/// <summary>
/// Объединение подматриц в одну матрицу
/// </summary>
/// <param name="a11"></param>
/// <param name="a12"></param>
/// <param name="a21"></param>
/// <param name="a22"></param>
/// <returns>возвращаем объединённую матрицу</returns>
static int[][] CollectMatrix(int[][] a11, int[][] a12, int[][] a21, int[][] a22)
{
int n = a11.Length;
var b = (n << 1);
int[][] a = new int[b][];
for (int i = 0; i < b; i++)
{
a[i] = new int[b];
}
for (int i = 0; i < n; i++)
{
Array.Copy(a11[i], 0, a[i], 0, n);
Array.Copy(a12[i], 0, a[i], n, n);
Array.Copy(a21[i], 0, a[i + n], 0, n);
Array.Copy(a22[i], 0, a[i + n], n, n);
}
return a;
}
/// <summary>
/// Разность между матрицами
/// </summary>
/// <param name="a">матрица 1</param>
/// <param name="b">матрица 2</param>
/// <returns>результат разности матриц</returns>
static int[][] Subtraction(int[][] a, int[][] b)
{
int n = a.Length;
int m = a[0].Length;
int[][] c = new int[n][];
for (int i = 0; i < n; i++)
{
c[i] = new int[m];
for (int j = 0; j < m; j++)
{
c[i][j] = a[i][j] - b[i][j];
}
}
return c;
}
/// <summary>
/// Умножение матриц
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns>результат умножения </returns>
static int[][] Multiply(int[][] a, int[][] b)
{
int rowsA = a.Length;
int columnsB = b[0].Length;
int columnsA_rowsB = a[0].Length;
int[][] c = new int[rowsA][];
for (int i = 0; i < rowsA; i++)
{
c[i] = new int[columnsB];
for (int j = 0; j < columnsB; j++)
{
int sum = 0;
for (int k = 0; k < columnsA_rowsB; k++)
{
sum += a[i][k] * b[k][j];
}
c[i][j] = sum;
}
}
return c;
}
/// <summary>
/// Суммирование матриц
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
static int[][] Summation(int[][] a, int[][] b)
{
int n = a.Length;
int m = a[0].Length;
int[][] c = new int[n][];
for (int i = 0; i < n; i++)
{
c[i] = new int[m];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
c[i][j] = a[i][j] + b[i][j];
}
}
return c;
}
/// <summary>
/// Убирает лишние строки матриц
/// </summary>
/// <param name="a"></param>
/// <param name="n"></param>
/// <param name="m"></param>
/// <returns>возвращаем матрицу</returns>
static int[][] GetSubmatrix(int[][] a, int n, int m)
{
int[][] result = new int[n][];
for (int i = 0; i < n; i++)
{
result[i] = new int[m];
Array.Copy(a[i], 0, result[i], 0, m);
}
return result;
}
/// <summary>
/// Генерация произвольного размера матрицы
/// </summary>
/// <param name="m">количество строк</param>
/// <param name="n">количество столбцов</param>
/// <returns>возврощаем матрицу</returns>
static int[][] GenerateMatrix(int m, int n)
{
Random rand = new Random();
int[][] matrix = new int[m][];
for (int i = 0; i < m; i++)
{
matrix[i] = new int[n];
for (int j = 0; j < n; j++)
{
matrix[i][j] = rand.Next(1, 100);
}
}
return matrix;
}
/// <summary>
/// Вывод на экран матриц
/// </summary>
/// <param name="matrix"></param>
static void OutputMatrix(int[][] matrix)
{
var sb = new StringBuilder();
foreach (int[] row in matrix)
{
foreach (int element in row)
{
sb.Append(element);
sb.Append(' ');
}
sb.Length--;
sb.AppendLine();
}
Console.WriteLine($"\n" + sb);
}
}
为了实验的纯粹性，我运行了你的代码。
首先我会回答这个问题，然后我会提出改进建议。
那么，为什么时间会增加：每次超过两个阈值的幂（2、4、16、32、...、1024、2048）时，执行时间会增加大约 7 倍，因为有一个额外的分支分成 7 个递归调用，因为出现了另一级递归嵌套。也就是说，在
if (n <= 64)触发条件之前会发生额外的分支。对于矩阵大小的所有其他增加，时间根据循环迭代次数线性增加。现在谈谈问题。您创建了大量几乎一次性使用的数组。假设对于 2048x2048 矩阵来说，这是数千万。而未使用和丢弃的数组是垃圾收集器关注的问题。汇编器本身可能会在汇编期间减慢代码执行速度。在调试模式下，这不是那么明显，因为执行了大量调试加载，但如果应用程序被编译成发布程序集并启动，则构建器的影响将更加明显。
为了使汇编器的工作更容易并可能加快代码速度，可以缓存矩阵。也就是说，我不会扔掉用过的矩阵，而是将其清理并放入集合中，当我需要新的矩阵时，我会查看缓存中是否有现成的我需要的大小的矩阵并从那里拿走它。
这是一个简单的矩阵池实现：
所以这就是发生的事情。
Также применил кеширование массивов по индексам, в методах сложения, вычитания и умножения матриц.
Это позволяет не искать массив по индексу каждый раз при обращении к его элементу, что тоже добавляет скорости.
Запускаю
То есть ~99% использованных матриц - это использованные повторно. То есть нагрузка на сборщик мусора сократилась до минимума, её практически нет. Именно за счёт этого немного подросла производительность кода. Учтите, что код работы методов пула матриц тоже добавил свою нагрузку, но всё равно стало быстрее.
Но самое интересное, здесь даже не скорость, а то что пик расхода памяти - 695 мегабайт в отладчике.
С пулом надо выполнять всего-лишь одно правило. Если вы отдали матрицу в пул, то вы не должны далее её использовать.
Кстати, пробовал переписать этот код на двухмерные
int[,]массивы, но работает медленнее процентов на 20, поэтому не стал показывать этот вариант.Кстати, методы суммирования и вычитания легко векторизовать
Это добавит ещё немного производительности.
На моём процессоре один вектор это 8 интов, то есть 8 сумм или разностей за одну итерацию цикла. Если не знакомы с векторами, почитайте что-нибудь про SIMD и AVX инструкции процессора.
Функция
GetNewDimension(m, n)считает размер до которого надо растянуть матрицы, чтобы с ними мог работать алгоритм Штрассена. Это должна быть степень двойки:Зачем 2048 увеличивается до 4096? 2048 уже степень двойки. Можно было оставить без изменений:
Теперь ступенька на 2048 пропала. Но она перебралась на 2049. Это нормально, алгоритм Штрассена переключается на следующую степень двойки и замедляется примерно в семь раз.
Нам не нужно чтобы размер матрицы был степенью двойки. Достаточно чтобы размер матрицы делился пополам до тех пор пока он не станет ≤ 64. Матрицы маленьких размеров умножаются обычным алгоритмом умножения, который работает с любыми размерами матриц.
Если 2049 увеличить до 2112, то алгоритм Штрассена поделит размер пополам шесть раз и получит матрицу размера 33 (= 2112 / 26), которую передаст обычному умножению.
Вот новая функция:
Времена работы на моей машине. Хотя ступеньки остались, они стали гораздо ниже:
P.S. От ступенек можно избавиться полностью, но потребуется много переделок в основной процедуре, а выигрыш в сравнении с текущим вариантом составит не более десяти процентов. А так дёшево и сердито.