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

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

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

Студворк — интернет-сервис помощи студентам
Здраствуйте, мне нужна помощь с распараллеливанием функции для нахождения определителя квадратной двухмерной матрицы, размеры которой могут быть более 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
22.01.2020, 19:19
Ответы с готовыми решениями:

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

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

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

20
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 20:01
Цитата Сообщение от JariXx Посмотреть сообщение
"задумывается".
Т.е. долго считает или намертво подвисает?
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 20:05  [ТС]
Считает очень долго (23 минуты спустя ответ не получил)
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 20:15
А на маленьких матрицах точно все нормально? Может просто ошибка в коде.
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 20:16  [ТС]
Проверял на матрице 4*4, быстро посчитал
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 20:33
Попробовать 10x10 ?
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 20:40  [ТС]
На секунду задумался, но посчитал
проверил результат через калькулятор матриц
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:06
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  [ТС]
Массив ниже используется
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:12
Сама выделение памяти для массива штука дорогостоящая, длительная.
Не говоря о потреблении памяти.
1
0 / 0 / 0
Регистрация: 12.11.2018
Сообщений: 57
22.01.2020, 21:16  [ТС]
Попробую сделать, спс
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
22.01.2020, 21:20
Называется "Правило Саррюса"

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
фрилансер
 Аватар для Алексей1153
6466 / 5688 / 1131
Регистрация: 11.10.2019
Сообщений: 15,143
22.01.2020, 21:21
JariXx, также можно заменить рекурсию на самодельный локальный стек, это и скорость чуток увеличит, и отладку упростит

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

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

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

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

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

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

Не по теме:

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

0
23.01.2020, 18:01

Не по теме:

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

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
23.01.2020, 18:01
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
Уведомление о неверно выбранном значении справочника
Maks 06.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru