Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
1

Параллельная рекурсия

22.01.2020, 19:19. Показов 2349. Ответов 20

Author24 — интернет-сервис помощи студентам
Здраствуйте, мне нужна помощь с распараллеливанием функции для нахождения определителя квадратной двухмерной матрицы, размеры которой могут быть более 100*100. Код нашёл на просторах интернета, рабочий проверил, однако при больших матрица "задумывается".
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//Возвращает матрицу matrix без row-ой строки и col-того столбца, результат в newMatrix
void getMatrixWithoutRowAndCol(double **matrix, int size, int row, int col, double **newMatrix) {
    int offsetRow = 0; //Смещение индекса строки в матрице
    int offsetCol = 0; //Смещение индекса столбца в матрице
    for (int i = 0; i < size - 1; i++) {
        //Пропустить row-ую строку
        if (i == row) {
            offsetRow = 1; //Как только встретили строку, которую надо пропустить, делаем смещение для исходной матрицы
        }
 
        offsetCol = 0; //Обнулить смещение столбца
        for (int j = 0; j < size - 1; j++) {
            //Пропустить col-ый столбец
            if (j == col) {
                offsetCol = 1; //Встретили нужный столбец, проускаем его смещением
            }
 
            newMatrix[i][j] = matrix[i + offsetRow][j + offsetCol];
        }
    }
}
 
 
//Вычисление определителя матрицы разложение по первой строке
double matrixDet(double **matrix, int size) {
    double det = 0;
    int degree = 1; // (-1)^(1+j) из формулы определителя
    //Условие выхода из рекурсии
    if (size == 1) {
        return matrix[0][0];
    }
    //Условие выхода из рекурсии
    else if (size == 2) {
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
    }
    else {
        //Матрица без строки и столбца
        double **newMatrix = new double*[size - 1];
        for (int i = 0; i < size - 1; i++) {
            newMatrix[i] = new double[size - 1];
        }
 
        //Раскладываем по 0-ой строке, цикл бежит по столбцам
        for (int j = 0; j < size; j++) {
            //Удалить из матрицы i-ю строку и j-ый столбец
            //Результат в newMatrix
            getMatrixWithoutRowAndCol(matrix, size, 0, j, newMatrix);
 
            //Рекурсивный вызов
            //По формуле: сумма по j, (-1)^(1+j) * matrix[0][j] * minor_j (это и есть сумма из формулы)
            //где minor_j - дополнительный минор элемента matrix[0][j]
            // (напомню, что минор это определитель матрицы без 0-ой строки и j-го столбца)
            det = det + (degree * matrix[0][j] * matrixDet(newMatrix, size - 1));
            //"Накручиваем" степень множителя
            degree = -degree;
        }
 
        //Чистим память на каждом шаге рекурсии(важно!)
        for (int i = 0; i < size - 1; i++) {
            delete[] newMatrix[i];
        }
        delete[] newMatrix;
    }
 
    return det;
}
Пример вызова
C++
1
double de = matrixDet(D[1], n1n2n3);
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.01.2020, 19:19
Ответы с готовыми решениями:

Параллельная матрица не считает при большом количестве элементов
Составил распаралеленный алгоритм умножения матрицы, при нескольких тысяч элементов считает все...

Параллельная программа для метода холецкого с помощью openMp и mpi
Товарищи,помогите пожалуйста с параллельным программированием: надо написать параллельную...

параллельная конфигурация
Добрый день. В VS C++ 2008 создаю программку, которая должна бы работать на компах, где не...

Параллельная прямая
Надо по заданным A,B,C найти две прямые на расстоянии от заданной от R. Кто-нибудь парочку формул...

20
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 20:01 2
Цитата Сообщение от JariXx Посмотреть сообщение
"задумывается".
Т.е. долго считает или намертво подвисает?
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 20:05  [ТС] 3
Считает очень долго (23 минуты спустя ответ не получил)
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 20:15 4
А на маленьких матрицах точно все нормально? Может просто ошибка в коде.
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 20:16  [ТС] 5
Проверял на матрице 4*4, быстро посчитал
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 20:33 6
Попробовать 10x10 ?
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 20:40  [ТС] 7
На секунду задумался, но посчитал
проверил результат через калькулятор матриц
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:06 8
C++
1
2
3
4
5
6
7
8
double matrixDet(double **matrix, int size) 
{
// ...
else {
        //Матрица без строки и столбца
        double **newMatrix = new double*[size - 1];
        for (int i = 0; i < size - 1; i++) {
            newMatrix[i] = new double[size - 1];
Не стоит при расчете определителя выделять каждый раз память это будет тормозить. Без этого можно по идее обойтись.

Я считал не через миноры, я считал методом дописывания столбцов и строки матрицы.

Тут есть примеры моего кода:

https://github.com/Avazart/Bic... r/Matrix.h
https://ideone.com/7yK0up

Но что там там все же не так, по тому как 100x100 чет всегда выдает ноль 0. Что скорее всего не верно.

Очевидно что нужно еще следить как-то за переполнением int при таких размерах матрицы ...
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 21:09  [ТС] 9
Массив ниже используется
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:12 10
Сама выделение памяти для массива штука дорогостоящая, длительная.
Не говоря о потреблении памяти.
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 21:16  [ТС] 11
Попробую сделать, спс
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:20 12
Называется "Правило Саррюса"

https://ru.wikipedia.org/wiki/... 1%81%D0%B0

Вот куски кода, но возможно есть ошибки

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//------------------------------------------------
template<typename T>
T& Matrix<T>::item(int row,int col) // дает элемент с учетом тех случаях когда индексы мнимые (дописанные элементы)
{
  row%= (int)rowSize_;
  col%= (int)colSize_;
 
  row= (row>=0)?row:(row+rowSize_);
  col= (col>=0)?col:(col+colSize_);
 
  return data_[row][col];
}
//------------------------------------------------
template<typename T>
T Matrix<T>::det()const
{
  if(!isSquare())
    throw std::runtime_error("Matrix is not square!");
 
  if(colSize_==2)
    return data_[0][0]*data_[1][1]-data_[1][0]*data_[0][1];
 
  T d(0);
  for(std::size_t c=0; c<colSize_;  ++c)
  {
    T p(1),n(1);
    for(std::size_t i=0; i<rowSize_;  ++i)
    {
      p*= item(c+i,i);
      n*= item(int(rowSize_)-1-c-i,i);
    }
    d+= p-n;
  }
  return d;
}
2
фрилансер
5835 / 5353 / 1101
Регистрация: 11.10.2019
Сообщений: 14,314
22.01.2020, 21:21 13
JariXx, также можно заменить рекурсию на самодельный локальный стек, это и скорость чуток увеличит, и отладку упростит

а тут только Си или C++ можно ?
0
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 21:22  [ТС] 14
С++
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:24 15
Цитата Сообщение от Алексей1153 Посмотреть сообщение
JariXx, также можно заменить рекурсию на самодельный локальный стек, это и скорость чуток увеличит, и отладку упростит
Суть в математическом методе который и делает нам рекурсию.
На каждом этапе нужно из матрицы делать минор который сам по себе матрица.
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 21:25  [ТС] 16
А разве Саррюс не для матрицы 3*3?
0
Эксперт С++
8482 / 6149 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 22:09 17
Цитата Сообщение от Avazart Посмотреть сообщение
Правило Саррюса
Помогает избавиться от рекурсии вовсе.
Но боюсь я что-то накосячил с определение дописываемых элементов.

Добавлено через 20 секунд
Цитата Сообщение от JariXx Посмотреть сообщение
А разве Саррюс не для матрицы 3*3
Для любых.

Добавлено через 7 минут
В теории можно и обойтись и без выделения памяти при разложении на миноры, но там все равно будет рекурсия и легче запутаться с индексами элементов.
И опять же нужно следить за переполнением int

Добавлено через 35 минут
Короче я перепроверил свой код, вроде как из-за того что в int не влазиет происходит переполнение при суммирование и перемножении довольно быстро при таких размерах матрицы.
Нужно брать int64 и больше (вроде в новых стандартах должны были появится).
Так же по идее можно использовать библиотеку mpir
1
715 / 675 / 110
Регистрация: 29.05.2015
Сообщений: 4,064
23.01.2020, 09:49 18
Цитата Сообщение от JariXx Посмотреть сообщение
На секунду задумался, но посчитал
1. Ну так чего ж на этом остановился? Нужно дальше проверять - 11х11, 12х12 и т.д. и смотреть, как растёт время выполнения. Возможно при увеличении матрицы на 1 время выполнения в 2 (и более) раз растет. Что-бы дождаться результата 100х100 тебе жизни не хватит.

2. Рекурсия потребляет много лишней памяти - программа с рекурсией быстрее "выберет" всю доступную память и рухнет. Да на быстродействие рекурсия скорее всего плохо влияет - необходимость записывать в стек всю функцию, что бы вызвать следующую. Для больших вычислений лучше обходиться без неё.

А что там за алгоритм, можно как-то проще объяснить на примере маленькой матрицы? А то неохота в чужом коде разбираться.
0
Avazart
23.01.2020, 13:35
  #19

Не по теме:

alexu_007, В школе что плохо было с матрицами? Стандартный алгоритм у него - разложения на миноры

0
zayats80888
23.01.2020, 18:01     Параллельная рекурсия
  #20

Не по теме:

Цитата Сообщение от Avazart Посмотреть сообщение
В школе что плохо было с матрицами?
А в школе уже матрицы преподают? :)

0
23.01.2020, 18:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.01.2020, 18:01
Помогаю со студенческими работами здесь

Параллельная обработка
Добрый день! Подскажите, пожалуйста, как параллельно считать содержимое всех файлов из...

Параллельная обработка файлов
Здравствуйте. Подскажите пожалуйста как на с++ реализовать обработку файлов параллельно в несколько...

Параллельная обработка файлов
Не понимаю как организовать параллельную обработку файлов в данной программе. Смысл в том что есть...

Параллельная конфигурация неправильна
Здравствуйте! Написал программу, которая работает на моем компьютере, но не работает на другом....

Параллельная сортировка Бэтчера
Доброго времени суток всем. есть код: #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define N 16 ...

Параллельная работа с файлами
Помогите, есть такое задание: На компьютере существует папка с файлами. Файлов много, их имена...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru