public Matrix Inv
{
get
{
if (!IsSquare)
throw new MatrixMustBeSquare("Матрица должна быть квадратной");
if (this.Det == 0)
throw new Exception("Матрица вырожденная. Ошибка Inv");
Matrix res = new Matrix(this);
res = res.Join(Eye(this.rows), RowOrColumn.Row);
for (int j = 0; j < res.rows; j++)
{
if (res[j, j] == 0)
{
Matrix tm = res.GetRow(j);
for (int i = j + 1; i < res.rows; i++)
if (res[i, j] != 0)
{
res = res.SetRow(j, res.GetRow(i));
res = res.SetRow(i, tm);
break;
}
}
for (int i = j + 1; i < res.rows; i++)
{
Matrix tm1 = res.GetRow(i) - res.GetRow(j) * res[i, j] / res[j, j];
res = res.SetRow(i, tm1);
}
}
for (int j = res.rows - 1; j >= 0; j--)
{
if (res[j, j] == 0)
{
Matrix tm = res.GetRow(j);
for (int i = j + 1; i < res.rows; i++)
if (res[i, j] != 0)
{
res = res.SetRow(j, res.GetRow(i));
res = res.SetRow(i, tm);
break;
}
}
for (int i = j - 1; i >= 0; i--)
{
Matrix tm1 = res.GetRow(i) - res.GetRow(j) * res[i, j] / res[j, j];
res = res.SetRow(i, tm1);
}
Matrix tm2 = res.GetRow(j) / res[j, j];
res = res.SetRow(j, tm2);
}
return res.GetSubMatrix(0, res.rows - 1, res.columns / 2, res.columns - 1);
}
}
Помогите оптимизировать код
Что происходит: есть матрица, надо найти обратную, взял метод Гаусса и получил вот такой код:
Вырезка из кода ( C# ):
Описание некоторых функций и свойств класса:
IsSquare - Являится ли матрица квадратной (true - да, false - нет);
Det - детерминант (определитель) матрицы;
Join - соединяет две матрицы в строку или столбец;
напрмер: A = A.Join(B, RowOrColumn.Row) - соединить матрицу A c матрицей B в строку и записать результат в матрицу A;
GetRow - считать указанную строку в матрице;
SetRow - заполняет указанную строку матрицы вектор столбцом/строкой
например: A = A.SetRow(0, B) - заполнить первую (нулевую) строку матрицы вектором B и записать результат в матрицу A;
GetSubMatrix - вырезать под матрицу из матрицы.
Проблема: медленно работает... тестил на матрице 100х100 секунд 25 думал...
Надо: или оптимизировать или написать какую-нть другую прогу (с комментариями) или еще чё-нть, но что-б это повлияло в лучшую сторону.... =)
Полный исходник в аттаче.
Вырезка из кода ( C# ):
Код:
Описание некоторых функций и свойств класса:
IsSquare - Являится ли матрица квадратной (true - да, false - нет);
Det - детерминант (определитель) матрицы;
Join - соединяет две матрицы в строку или столбец;
напрмер: A = A.Join(B, RowOrColumn.Row) - соединить матрицу A c матрицей B в строку и записать результат в матрицу A;
GetRow - считать указанную строку в матрице;
SetRow - заполняет указанную строку матрицы вектор столбцом/строкой
например: A = A.SetRow(0, B) - заполнить первую (нулевую) строку матрицы вектором B и записать результат в матрицу A;
GetSubMatrix - вырезать под матрицу из матрицы.
Проблема: медленно работает... тестил на матрице 100х100 секунд 25 думал...
Надо: или оптимизировать или написать какую-нть другую прогу (с комментариями) или еще чё-нть, но что-б это повлияло в лучшую сторону.... =)
Полный исходник в аттаче.
Если переписать на Visual C, с использованием указателей,
тогда программа будет работать намного быстрее.
И есть такой код в Inv
Допустим j = res.rows - 1 и res[j, j] == 0. Тогда само собой, res[j, j] == 0 не будет заменен на ненулевой элемент. У тебя нет проверки на неравентсво нуля. И пару строками ниже тот же самый код.
тогда программа будет работать намного быстрее.
И есть такой код в Inv
Код:
for (int j = 0; j < res.rows; j++)
{
if (res[j, j] == 0)
{
Matrix tm = res.GetRow(j);
for (int i = j + 1; i < res.rows; i++)
{
if (res[j, j] == 0)
{
Matrix tm = res.GetRow(j);
for (int i = j + 1; i < res.rows; i++)
Допустим j = res.rows - 1 и res[j, j] == 0. Тогда само собой, res[j, j] == 0 не будет заменен на ненулевой элемент. У тебя нет проверки на неравентсво нуля. И пару строками ниже тот же самый код.
мож тогда вообще на asm'e написать???
Допустим j = res.rows - 1 и res[j, j] == 0. Тогда само собой, res[j, j] == 0 не будет заменен на ненулевой элемент. У тебя нет проверки на неравентсво нуля. И пару строками ниже тот же самый код.
Это ты все к чему????
Допустим j = res.rows - 1 и res[j, j] == 0. Тогда само собой, res[j, j] == 0 не будет заменен на ненулевой элемент. У тебя нет проверки на неравентсво нуля. И пару строками ниже тот же самый код.
Это ты все к чему????
[QUOTE=alektrik]мож тогда вообще на asm'e написать???
Допустим j = res.rows - 1 и res[j, j] == 0. Тогда само собой, res[j, j] == 0 не будет заменен на ненулевой элемент. У тебя нет проверки на неравентсво нуля. И пару строками ниже тот же самый код.
Это ты все к чему????[/QUOTE]Это я к тому, что в зависимости от входных данных, есть шанс деления на ноль, в командах
Matrix tm1 = res.GetRow(i) - res.GetRow(j) * res[i, j] / res[j, j];
Нет смысла на asm-е писать. И если убрать ВСЕ операции SetRow(), то и эта прога работала бы намного быстрее.
Допустим j = res.rows - 1 и res[j, j] == 0. Тогда само собой, res[j, j] == 0 не будет заменен на ненулевой элемент. У тебя нет проверки на неравентсво нуля. И пару строками ниже тот же самый код.
Это ты все к чему????[/QUOTE]Это я к тому, что в зависимости от входных данных, есть шанс деления на ноль, в командах
Matrix tm1 = res.GetRow(i) - res.GetRow(j) * res[i, j] / res[j, j];
Нет смысла на asm-е писать. И если убрать ВСЕ операции SetRow(), то и эта прога работала бы намного быстрее.
конечно могут быть разне варианты с нулём... единственно, глюк будет, если элементы по главной диагонале будут равны 0... (понял о чем ты) в принципе это не столь сильная проблема...
сильная проблемма в алгоритме... понимаешь, надо оптимизировать сам АЛГОРИТМ нахождения... а с оптимизацие кода не хочу связываться, потому что ухудшится читаемость алгоритма...
сильная проблемма в алгоритме... понимаешь, надо оптимизировать сам АЛГОРИТМ нахождения... а с оптимизацие кода не хочу связываться, потому что ухудшится читаемость алгоритма...
[QUOTE=alektrik]конечно могут быть разне варианты с нулём... единственно, глюк будет, если элементы по главной диагонале будут равны 0... (понял о чем ты) в принципе это не столь сильная проблема...
сильная проблемма в алгоритме... понимаешь, надо оптимизировать сам АЛГОРИТМ нахождения... а с оптимизацие кода не хочу связываться, потому что ухудшится читаемость алгоритма...[/QUOTE]imho в первую очередь алгоритм должен быть правильным и эффективным. Вариант без GetRow(). Но на Visual C c помощью указателей можно бы вообще убрать [i, j].
сильная проблемма в алгоритме... понимаешь, надо оптимизировать сам АЛГОРИТМ нахождения... а с оптимизацие кода не хочу связываться, потому что ухудшится читаемость алгоритма...[/QUOTE]imho в первую очередь алгоритм должен быть правильным и эффективным. Вариант без GetRow(). Но на Visual C c помощью указателей можно бы вообще убрать [i, j].
Код:
public Matrix Inv
{
get
{
if (!IsSquare)
throw new MatrixMustBeSquare("Матрица должна быть квадратной");
if (this.Det == 0)
throw new Exception("Матрица вырожденная. Ошибка Inv");
Matrix res = new Matrix(this);
res = res.Join(Eye(this.rows), RowOrColumn.Row);
int a, rjj, rij;
for (int j = 0; j < res.rows; j++)
{
rjj = res[j, j];
if (rjj == 0)
{
for (int i = j + 1; i < res.rows; i++)
if (res[i, j] != 0)
{
rjj = res[i, j];
for(int k = 0; k < res.cols; k++)
{
a = res[i, k];
res[i, k] = res[j, k];
res[j, k] = a;
}
break;
}
}
for (int i = j + 1; i < res.rows; i++)
{
rij = res[i, j];
for(int k = 0; k < res.cols; k++)
{
res[i, k] = res[i,k] - res[j, k] * rij / rjj;
}
}
}
for (int j = res.rows - 1; j >= 0; j--)
{
if (res[j, j] == 0)
{
for (int i = j + 1; i < res.rows; i++)
if (res[i, j] != 0)
{
rjj = res[i, j];
for(int k = 0; k < res.cols; k++)
{
a = res[i, k];
res[i, k] = res[j, k];
res[j, k] = a;
}
break;
}
}
for (int i = j - 1; i >= 0; i--)
{
rij = res[i, j];
for(int k = 0; k < res.cols; k++)
{
res[i, k] = res[i,k] - res[j, k] * rij / rjj;
}
}
for(int k = 0; k < res.cols; k++)res[j, k]/=rjj;
}
return res.GetSubMatrix(0, res.rows - 1, res.columns / 2, res.columns - 1);
}
}
{
get
{
if (!IsSquare)
throw new MatrixMustBeSquare("Матрица должна быть квадратной");
if (this.Det == 0)
throw new Exception("Матрица вырожденная. Ошибка Inv");
Matrix res = new Matrix(this);
res = res.Join(Eye(this.rows), RowOrColumn.Row);
int a, rjj, rij;
for (int j = 0; j < res.rows; j++)
{
rjj = res[j, j];
if (rjj == 0)
{
for (int i = j + 1; i < res.rows; i++)
if (res[i, j] != 0)
{
rjj = res[i, j];
for(int k = 0; k < res.cols; k++)
{
a = res[i, k];
res[i, k] = res[j, k];
res[j, k] = a;
}
break;
}
}
for (int i = j + 1; i < res.rows; i++)
{
rij = res[i, j];
for(int k = 0; k < res.cols; k++)
{
res[i, k] = res[i,k] - res[j, k] * rij / rjj;
}
}
}
for (int j = res.rows - 1; j >= 0; j--)
{
if (res[j, j] == 0)
{
for (int i = j + 1; i < res.rows; i++)
if (res[i, j] != 0)
{
rjj = res[i, j];
for(int k = 0; k < res.cols; k++)
{
a = res[i, k];
res[i, k] = res[j, k];
res[j, k] = a;
}
break;
}
}
for (int i = j - 1; i >= 0; i--)
{
rij = res[i, j];
for(int k = 0; k < res.cols; k++)
{
res[i, k] = res[i,k] - res[j, k] * rij / rjj;
}
}
for(int k = 0; k < res.cols; k++)res[j, k]/=rjj;
}
return res.GetSubMatrix(0, res.rows - 1, res.columns / 2, res.columns - 1);
}
}
В смысле совсем убрать [i,j]... просто представить как одномерный массив что-ли???
[QUOTE=alektrik]В смысле совсем убрать [i,j]... просто представить как одномерный массив что-ли???[/QUOTE]Нет только работать как с одномерным массивом. Напр. перестановка столбцов i и j
Конечно, кому в программировании главное т.н. удобочитаемость кода, то код выше может показаться довольно диким. :)
Код:
const int N = 100;
int a[N][N];
...
int i = 2;
int j = 3;
int *ip = &a[0][0] + i*N;
int *jp = &a[0][0] + j*N;
int *iend = ip + N;
while(ip<iend)
{
int a = *ip;
*ip++ = *jp;
*jp++ = a;
}
int a[N][N];
...
int i = 2;
int j = 3;
int *ip = &a[0][0] + i*N;
int *jp = &a[0][0] + j*N;
int *iend = ip + N;
while(ip<iend)
{
int a = *ip;
*ip++ = *jp;
*jp++ = a;
}
так... парень постой... что-т ты разогнался... я конечно рад за тебя, что ты умеешь указателями пользоваться... вот те вопросик на засыпку... ты хочешь сказать, что алгоритм тормозит из-за того что перестановки строк долго выполняются... какова вероятность того что элемент [j, j] будет равен 0... ведь только в этом случае будет выполнятся перестановка... и если даже она будет выполнятся, то для матрицы 100х100 - это всего лишь 100 итераций... подумай, что такое для современных машин 100 подобных (как у меня в коде) итераций...
По сути можешь этот кусок кода вооще можешь выкинуть... единственный глюк будет, если в матрице главный элемент (который [j,j]) будет равен нулю, то прога выдаст ошибку... вот его (алгоритм без данного куска кода) и надо оптимизировать... ведь только одна группа вложенных циклов для матрицы 100x100 будет забирать окло 5000 итераций... а группы 2 штуки, то бишь это около 10 тыс. итераций...
и на счет нуля есть другой вариант - http://www.exponenta.ru/educat/class/test/showitem/?item=455
На худой конец фиг с этим Гауссом, напиши алгоритм побыстрее.. или напиши алгоритм с помощью LU-разложения... просто мне щас не особо до этого, есть задачи и поважнее честно гря...
Вот например если взять пакет Matlab, то он обратную матрицу для матрицы 100х100 вычисляет за доли секунды... если кто-то (Mathworks) это сделал, чем мы все хуже их???
По сути можешь этот кусок кода вооще можешь выкинуть... единственный глюк будет, если в матрице главный элемент (который [j,j]) будет равен нулю, то прога выдаст ошибку... вот его (алгоритм без данного куска кода) и надо оптимизировать... ведь только одна группа вложенных циклов для матрицы 100x100 будет забирать окло 5000 итераций... а группы 2 штуки, то бишь это около 10 тыс. итераций...
и на счет нуля есть другой вариант - http://www.exponenta.ru/educat/class/test/showitem/?item=455
На худой конец фиг с этим Гауссом, напиши алгоритм побыстрее.. или напиши алгоритм с помощью LU-разложения... просто мне щас не особо до этого, есть задачи и поважнее честно гря...
Вот например если взять пакет Matlab, то он обратную матрицу для матрицы 100х100 вычисляет за доли секунды... если кто-то (Mathworks) это сделал, чем мы все хуже их???
Основной тормоз из-за GetRows().
Как переставляются строки на С++ с помощью указателей я привел только для примера, чтоб показать как работать с массивом, как с одномерным.
Если MatLab обратную матрицу вычисляет за доли секунды, а твоя прога за 25 секунд, то вопрос "...чем мы все хуже их???" не уместен.
Как переставляются строки на С++ с помощью указателей я привел только для примера, чтоб показать как работать с массивом, как с одномерным.
Если MatLab обратную матрицу вычисляет за доли секунды, а твоя прога за 25 секунд, то вопрос "...чем мы все хуже их???" не уместен.
Цитата:
На худой конец фиг с этим Гауссом, напиши алгоритм побыстрее.. или напиши алгоритм с помощью LU-разложения... просто мне щас не особо до этого, есть задачи и поважнее честно гря...
Вообще-то я немношко запутался. Кому нужна эта прога? Тебе или мне? :)