Почему алгоритм Штрассена резко замедляется после 2047?
Я заметил матрицы размерностью от 1 до 2047 считаются за 6+- секунд
А начиная от 2048 начинают от 44 +- секунд. С чем может быть связан такой скачок во времени ?
при 2047 матрицы оперативка поднималась до 279 мб при 2048 до 1042 мб
При этом оперативки хватает, тяжко просто считать ей становится
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);
}
}
Ответы (1 шт):
Автор решения: Stanislav Volodarskiy
→ Ссылка
Функция GetNewDimension(m, n) считает размер до которого надо растянуть матрицы, чтобы с ними мог работать алгоритм Штрассена. Это должна быть степень двойки:
n (= m) GetNewDimension(m, n) 2047 2048 2048 4096 Зачем? 2049 4096
Зачем 2048 увеличивается до 4096? 2048 уже степень двойки. Можно было оставить без изменений:
static int GetNewDimension2(ref int m, ref int n) =>
1 << (int)Math.Ceiling(Math.Log2(Math.Max(m, n)));
Теперь ступенька на 2048 пропала. Но она перебралась на 2049. Это нормально, алгоритм Штрассена переключается на следующую степень двойки и замедляется примерно в семь раз.
Нам не нужно чтобы размер матрицы был степенью двойки. Достаточно чтобы размер матрицы делился пополам до тех пор пока он не станет ≤ 64. Матрицы маленьких размеров умножаются обычным алгоритмом умножения, который работает с любыми размерами матриц.
Если 2049 увеличить до 2112, то алгоритм Штрассена поделит размер пополам шесть раз и получит матрицу размера 33 (= 2112 / 26), которую передаст обычному умножению.
Вот новая функция:
static int GetNewDimension(ref int m, ref int n)
{
int b = 64;
int k = Math.Max(n, m);
int f = 1 << (int)Math.Ceiling(Math.Log2((k + b - 1) / b));
return f * ((k + f - 1) / f);
}
Времена работы на моей машине. Хотя ступеньки остались, они стали гораздо ниже:
n (= m) GetNewDimension(m, n) Время работы 2047 2048 14.18 2048 2048 14.19 2049 2112 17.48 2050 2112 17.85 ... 2111 2112 17.80 2112 2112 17.46 2113 2176 18.86 2114 2176 18.99 ... 2175 2176 18.74 2176 2176 18.80 2177 2240 20.04 2178 2240 20.03
P.S. От ступенек можно избавиться полностью, но потребуется много переделок в основной процедуре, а выигрыш в сравнении с текущим вариантом составит не более десяти процентов. А так дёшево и сердито.