C# Алгоритм Штрассена перемножения матриц. Медленно работает

Помогите пожалуйста оптимизирать алгоритм.

Реализовал данный алгоритм, но он почему то у меня работает гораздо медленне чем традиционный n^3 (тестировалось на матрицах 1000х1000). Алгоритм реализован для квадратных матриц, так как большего не требуется.
Для алгоритма был создан класс Matrix, содержащий в себе интовый массив, и три указателя, характеризующих, с какой частью массива происходит работа(I ,J — левый верхний угол, n — сколько элементов от этого угла брать для работы). Это сделано для того, чтобы можно было без особых заморочек взять подматрицы и протолкнуть по ссылку массив.
Если в рекурсию передаются массивы с размером меньшим либо равным 32, то они перемножаются по алгоритму Винограду.

Описание самого алгоритма на Вики.

Алгорит перемножает корректно, проверено на множестве тестов.

Код под катом.



public class Matrix
{
    public int I { get; set; }
    public int J { get; set; }
    public int[,] mas { get; set; }
    public int n{get;set;}

    public Matrix(int Size)
    {
       mas = new int[Size, Size];
       I = 0; J = 0; n = Size;
    }
    
    public Matrix(int[,] mas,int I,int J,int n)
    {
        this.I = I;
        this.J = J;
        this.n = n;
        this.mas = mas;
    }

    public Matrix(int[,] mas)
    {
        this.I = 0;
        this.J = 0;
        this.mas = mas;
        this.n = mas.GetLength(0);
      
    }

    public Matrix GetLeftTopSubMatrix()
    {
        return new Matrix(mas,I,J,n/2);
    }

    public Matrix GetLeftDownSubMatrix()
    {
        return new Matrix(mas, I+n/2, J, n / 2);
    }

    public Matrix GetRightTopSubMatrix()
    {
        return new Matrix(mas, I, J+n/2, n / 2);
    }

    public Matrix GetRightDownSubMatrix()
    {
        return new Matrix(mas, I + n / 2, J + n / 2, n / 2);
    }

 
}


        public int[,] Shtrassen(Matrix mat1, Matrix mat2)
        {

            if (mat1.n > 2)
            {
                int n2 = mat1.n / 2;


                Matrix P1 = new Matrix(Shtrassen(PlusMatrix(mat1.GetLeftTopSubMatrix(), 
mat1.GetRightDownSubMatrix()), PlusMatrix(mat2.GetLeftTopSubMatrix(), mat2.GetRightDownSubMatrix())));
                Matrix P2 = new Matrix(Shtrassen(PlusMatrix(mat1.GetLeftDownSubMatrix(), 
mat1.GetRightDownSubMatrix()), mat2.GetLeftTopSubMatrix()));
                Matrix P3 = new Matrix(Shtrassen(mat1.GetLeftTopSubMatrix(), 
MinusMatrix(mat2.GetRightTopSubMatrix(), mat2.GetRightDownSubMatrix())));
                Matrix P4 = new Matrix(Shtrassen(mat1.GetRightDownSubMatrix(), 
MinusMatrix(mat2.GetLeftDownSubMatrix(), mat2.GetLeftTopSubMatrix())));
                Matrix P5 = new Matrix(Shtrassen(PlusMatrix(mat1.GetLeftTopSubMatrix(), 
mat1.GetRightTopSubMatrix()), mat2.GetRightDownSubMatrix()));
                Matrix P6 = new Matrix(Shtrassen(MinusMatrix(mat1.GetLeftDownSubMatrix(), 
mat1.GetLeftTopSubMatrix()), PlusMatrix(mat2.GetLeftTopSubMatrix(), mat2.GetRightTopSubMatrix())));
                Matrix P7 = new Matrix(Shtrassen(MinusMatrix(mat1.GetRightTopSubMatrix(), 
mat1.GetRightDownSubMatrix()), PlusMatrix(mat2.GetLeftDownSubMatrix(), mat2.GetRightDownSubMatrix())));



                Matrix R = PlusMatrix(PlusMatrix(P1, P4), MinusMatrix(P7, P5));
                Matrix S = PlusMatrix(P3, P5);
                Matrix T = PlusMatrix(P2, P4);
                Matrix U = PlusMatrix(PlusMatrix(P3, P6), MinusMatrix(P1, P2));


                Matrix Result = new Matrix(mat1.n);


                for (int i = 0; i < n2; i++) for (int j = 0; j < n2; j++)
                    {
                        Result.mas[i, j] = R.mas[i, j];
                        Result.mas[i, j + n2] = S.mas[i, j];
                        Result.mas[i + n2, j] = T.mas[i, j];
                        Result.mas[i + n2, j + n2] = U.mas[i, j];
                    }


                return Result.mas;
            }
            else
            {
                int[,] Result = Vinograd(mat1, mat2);
                return Result;
            }

            int[,] Result1 = new int[1, 1];

            return Result1;
        } 


        public Matrix PlusMatrix(Matrix mat1, Matrix mat2)
        {
            Matrix mat3 = new Matrix(mat1.n);

            for (int i = 0; i < mat1.n; i++) for (int j = 0; j < mat1.n; j++) mat3.mas[i, j] = 
mat1.mas[i + mat1.I, j + mat1.J] + mat2.mas[i + mat2.I, j + mat2.J];
            return mat3;
        }

  • Вопрос задан
  • 8588 просмотров
Пригласить эксперта
Ответы на вопрос 6
atd
@atd
алгоритм не смотрел, но уже чисто по коду:
1. int[,] mas — если нужна скорость, то юзайте [][] или ещё лучше просто плоский массив
2. public int n{get;set;} — auto property — зло
Ответ написан
opium
@opium
Просто люблю качественно работать
Заюзайте профайлер и посмотрите где медленно работает.
Ну или натыкайте таймов и выводите их в файл, а там уже анализируйте что тормозит.
Ответ написан
Shedal
@Shedal
Вообще, видно, что на каждом шаге рекурсии создается множество объектов класса Matrix. А выделение памяти тоже требует времени. Возможно, проблема в этом.
Насколько медленнее работает эта реализация в сравнении с тем, что вы от нее ожидаете?
Ответ написан
@pr0fedt Автор вопроса
Работает медленнее где то в 3,5 — 4 раза. Константа у алгоритма достаточно велика, как и требования по памяти, но на размере матриц 1000х1000 он уже должен точно обгонять традиционный алгоритм перемножения.

Есть подозрения, что в созданных объектах класса Matrix массив проталкивается не по ссылке. Если это так, то в таком случае придется удалить данный класс и работать напрямую с массивом, хотя в данном случае код будет выглядеть нечитабельно. Сейчас попробую это сделать…

Загнал в профайлер, если у меня правильно получается интерпретировать его отчет, то 70% процессорного времени уходит на перемножение алгоритмом Винограда в случае, елси размер матрицы меньше 32
Ответ написан
kulinich
@kulinich
С++ программист
Могу предложить реализацию перемножения матриц на APL (dll'ку сделаю, + в папку bin надо будет пару dll'лек кинуть), если матрицы большие, то прирост скорости в разы.
Н-р: 2000 на 2000 на APL — около 8 сек, на C# там чуть ли не минута а то и больше. (не помню честно точные результаты, но эксперименты мы с другом ставили такие)=)
Ответ написан
@pr0fedt Автор вопроса
Вопрос решен. Сразу не логадался проверить работу алгоритма на матрицах с размером больше чем 1024х1024.
В итоге на размера 4096х4096 он оказался быстрее. Оптимизировал код согласно советам, убрал класс-обертку Matrix, в итоге алгоритм стал быстрее традиционного уже на 1024х1024, хотя в литературе пишут, что алгоритм Штрассена предпочтительные использовать уже при размерах больших 128х128. Но быстрее, без использования кеширования боюсь на C# у меня не получится.
За предложение скинуть dll'ку спасибо) Это учебный проект, но к сожалению никто из преподаватель мне с ним помочь не смог.
Огромное спасибо за помощь)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы