Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/10: Рейтинг темы: голосов - 10, средняя оценка - 4.60
galayko
5 / 5 / 3
Регистрация: 20.10.2013
Сообщений: 68
1

Сложение разреженных матриц в схеме CSR / CRS / Метод разряженных строк / Схема Чанга и Густавсона

08.03.2015, 13:22. Просмотров 2068. Ответов 2
Метки нет (Все метки)

Здравствуйте, нужна ваша помощь!

Стоит задача "свернуть" две разреженные матрицы в CRS схему (названий у нее много, в заголовке написал все, что нашел), сложить их в "свернутом" виде, а потом "развернуть" результат.

CSR схема состоит в следующем - матрица записывается в три массива:
  1. массив ненулевых элементов матрицы A, в котором они перечислены по строкам от первой до последней (обозначим его как values);
  2. массив номеров столбцов для соответствующих элементов массива values (обозначим его как cols);
  3. массив указателей позиций, с которых начинается описание очередной строки (обозначим его pointer).
Пример:
Кликните здесь для просмотра всего текста
Матрица:
1 1 0 3 0
2 5 0 0 0
0 0 4 6 4
4 0 2 7 0
0 8 0 0 5

Она же в "свернутом" виде:
values: 1 1 3 2 5 4 6 4 4 2 7 8 5
__cols: 0 1 3 0 1 2 3 4 0 2 3 1 4 //сместил для наглядности
pointer: 0 3 5 8 11

(Так как пример скорее наглядный, чем корректный, то и "сворачивание" совсем неэффективно)

Метод "сворачивания" написал, вот он, может пригодится:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void Comprass()
        {
            for (int i = 0; i < n; i++)
            {
                pointer.Add(cols.Count);
 
                for (int j = 0; j < m; j++)
                {
                    if (matrix[i, j] != 0)
                    {
                        values.Add(matrix[i, j]);
                        cols.Add(j);
                    }
                }
            }
        }


А вот как сложить "свернутые" матрицы ума не приложу... Подскажите!

Добавлено через 20 часов 17 минут
Никто не сталкивался что ли? Удивительно...

Добавлено через 12 минут
Метод "сворачивания" (старый не совсем верен):
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void Comprass()
        {
            pointer.Clear();
            values.Clear();
            cols.Clear();
            for (int i = 0; i < n; i++)
            {
                pointer.Add(cols.Count);
 
                for (int j = 0; j < m; j++)
                {
                    if (matrix[i, j] != 0)
                    {
                        values.Add(matrix[i, j]);
                        cols.Add(j);
                    }
                }
            }
            pointer.Add(cols.Count);
        }

Метод разворачивания дописал:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void deComprass()
        {
            //заполняем матрицу нулями
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    matrix[i,j] = 0;
            //заполняем ненулевыми элементами
            int matrix_i = 0;
            for (int i = 0; i < pointer.Count - 1; i++)
            {
                for (int j = pointer[i]; j < pointer[i+1]; j++)
                    matrix[matrix_i, cols[j]] = values[j];
                matrix_i++;
            }
        }
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2015, 13:22
Ответы с готовыми решениями:

Умножение треугольных матриц«Методы обработки разреженных матриц»
Нужно перемножить треугольные матрицы в обычном виде и в свёрнутом. С обычным проблем нет. Доступ...

Определители разреженных матриц
Здравствуйте! Помогите посчитать определители следующих матриц: 1) \begin{vmatrix}1 &amp; 2 &amp; 0 &amp; ......

Найти сумму двух сильно разреженных матриц
Найти сумму двух сильно разреженных матриц A(m,n) и B(m,n), хранящихся в упакованном виде....

Разработать способ экономного хранения в памяти разреженных матриц
Помогите плз зделать Задание 1 Разработать способ экономного хранения в памяти разреженных матриц...

Разработать способ экономического хранения в памяти разреженных матриц
задание Разработать способ экономического хранения в памяти разреженных матриц. Разработать...

2
castaway
08.03.2015, 13:34
  #2

Не по теме:

Просто ты не во время.. Подожди немного. Сегодня праздник у девчат. Сегодня будут танцы!

0
galayko
5 / 5 / 3
Регистрация: 20.10.2013
Сообщений: 68
10.03.2015, 09:18  [ТС] 3
Что-то получилось... но очень криво написано и работает не всегда.
Кликните здесь для просмотра всего текста
C++ (Qt)
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
private Matrix SumMatrix(Matrix m1, Matrix m2)
        {
            Matrix ans = new Matrix(n, m);
            //сколько элементов уже прошли в конечном массиве
            int sum_length = 0;
            //сколько было в старой паре массивов
            int old_mas1_count = 0;
            int old_mas2_count = 0;
            //сколько элементов прошли в массиве
            int cols1_done = 0;
            int cols2_done = 0;
            for (int i = 0; i < m1.pointer.Count - 1; i++)
            {
                //добавляем текущую строку
                ans.pointer.Add(ans.cols.Count);
                //два массива для каждой строки матрицы
                List<int> mas1 = new List<int>();
                List<int> mas2 = new List<int>();
                for (int j = m1.pointer[i]; j < m1.pointer[i + 1]; j++)
                    mas1.Add(m1.cols[j]);
                for (int j = m2.pointer[i]; j < m2.pointer[i + 1]; j++)
                    mas2.Add(m2.cols[j]);
 
                //выбираем длинный массив и записываем его в ans
                //mas1 - должен быть длиннее
                bool swap = false;
                if (mas2.Count > mas1.Count)
                {
                    List<int> buff = mas1;
                    mas1 = mas2;
                    mas2 = buff;
                    swap = true;
                }
                
                //записываем длинный массив в ответ
                for (int j = 0; j < mas1.Count; j++)
                {
                    ans.cols.Add(mas1[j]);
                    if (!swap)
                        ans.values.Add(m1.values[cols1_done + j]);
                    else
                        ans.values.Add(m2.values[cols2_done + j]);
                }
                //количество обработанных элементов в данном куске готового массива
                int kol = 0;
                //проводилось ли в строке только сложение
                bool onlySum = true;
                //количество сумм подряд
                int kolSum = 0;
                //добавляем в первый массив элементы второго массива, если таких нет там и складываем с существующими, если есть
                for (int j = 0; j < mas2.Count; j++)
                {
     
                    //есть ли текущий элемент второго в ответе
                    bool IS = false;
                    for (int k = sum_length; k < ans.cols.Count && !IS; k++)
                        if (mas2[j] == ans.cols[k])
                            IS = true;
                    //если нет, вставляем его по возрастанию
                    if (!IS)
                    {
                        int k;
                        for (k = sum_length; k < ans.cols.Count; k++)
                            if (ans.cols[k] > mas2[j])
                                break;
                        //вставляем индекс
                        ans.cols.Insert(k, mas2[j]);
                        //если была перестановка, вставляем из первого, иначе из второго
                        if (swap)
                            ans.values.Insert(k, m1.values[cols1_done + j]);
                        else
                            ans.values.Insert(k, m2.values[cols2_done + j]);
                        onlySum = false;
                        kol++;
                    }
                    else //если да, складываем value
                    {
                        if (swap)
                            ans.values[sum_length + j + kol - kolSum] += m1.values[cols1_done + j];
                        else
                            ans.values[sum_length + j + kol - kolSum] += m2.values[cols2_done + j];
                        kol++;
                        kolSum++;
                    }
                }
                sum_length = (mas1.Count == mas2.Count && !onlySum) ? sum_length + 2 * mas1.Count : sum_length + mas1.Count;
                if (swap)
                {
                    old_mas1_count = mas2.Count;
                    old_mas2_count = mas1.Count;
                    cols1_done += mas2.Count;
                    cols2_done += mas1.Count;
                }
                else
                {
                    old_mas1_count = mas1.Count;
                    old_mas2_count = mas2.Count;
                    cols1_done += mas1.Count;
                    cols2_done += mas2.Count;
                }
            }
            ans.pointer.Add(ans.cols.Count);
 
                return ans;
        }


Все еще актуально!

Добавлено через 21 час 1 минуту
Поднимаю последний раз... Больше не буду.

Добавлено через 16 часов 26 минут
Все! Теперь вроде работает всегда.
Кликните здесь для просмотра всего текста
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
private Matrix SumMatrix(Matrix m1, Matrix m2)
        {
            Matrix ans = new Matrix(n, m);
            //сколько элементов уже прошли в конечном массиве
            int sum_length = 0;
            //сколько было в старой паре массивов
            int old_mas1_count = 0;
            int old_mas2_count = 0;
            //сколько элементов прошли в массиве
            int cols1_done = 0;
            int cols2_done = 0;
            for (int i = 0; i < m1.pointer.Count - 1; i++)
            {
                //добавляем текущую строку
                ans.pointer.Add(ans.cols.Count);
                //два массива для каждой строки матрицы
                List<int> mas1 = new List<int>();
                List<int> mas2 = new List<int>();
                for (int j = m1.pointer[i]; j < m1.pointer[i + 1]; j++)
                    mas1.Add(m1.cols[j]);
                for (int j = m2.pointer[i]; j < m2.pointer[i + 1]; j++)
                    mas2.Add(m2.cols[j]);
 
                //выбираем длинный массив и записываем его в ans
                //mas1 - должен быть длиннее
                bool swap = false;
                if (mas2.Count > mas1.Count)
                {
                    List<int> buff = mas1;
                    mas1 = mas2;
                    mas2 = buff;
                    swap = true;
                }
                
                //записываем длинный массив в ответ
                for (int j = 0; j < mas1.Count; j++)
                {
                    ans.cols.Add(mas1[j]);
                    if (!swap)
                        ans.values.Add(m1.values[cols1_done + j]);
                    else
                        ans.values.Add(m2.values[cols2_done + j]);
                }
                //проводилось ли в строке только сложение
                bool onlySum = true;
                //добавляем в первый массив элементы второго массива, если таких нет там и складываем с существующими, если есть
                for (int j = 0; j < mas2.Count; j++)
                {
     
                    //есть ли текущий элемент второго в ответе
                    bool IS = false;
                    int pos = 0;
                    for (int k = sum_length; k < ans.cols.Count && !IS; k++)
                        if (mas2[j] == ans.cols[k])
                        {
                            IS = true;
                            pos = k;
                        }
                    //если нет, вставляем его по возрастанию
                    if (!IS)
                    {
                        int k;
                        for (k = sum_length; k < ans.cols.Count; k++)
                            if (ans.cols[k] > mas2[j])
                                break;
                        //вставляем индекс
                        ans.cols.Insert(k, mas2[j]);
                        //если была перестановка, вставляем из первого, иначе из второго
                        if (swap)
                            ans.values.Insert(k, m1.values[cols1_done + j]);
                        else
                            ans.values.Insert(k, m2.values[cols2_done + j]);
                        onlySum = false;
                    }
                    else //если да, складываем value
                    {
                        if (swap)
                            ans.values[pos] += m1.values[cols1_done + j];
                        else
                            ans.values[pos] += m2.values[cols2_done + j];
                    }
                }
                sum_length = (mas1.Count == mas2.Count && !onlySum) ? sum_length + 2 * mas1.Count : sum_length + mas1.Count;
                if (swap)
                {
                    old_mas1_count = mas2.Count;
                    old_mas2_count = mas1.Count;
                    cols1_done += mas2.Count;
                    cols2_done += mas1.Count;
                }
                else
                {
                    old_mas1_count = mas1.Count;
                    old_mas2_count = mas2.Count;
                    cols1_done += mas1.Count;
                    cols2_done += mas2.Count;
                }
            }
            ans.pointer.Add(ans.cols.Count);
 
                return ans;
        }
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.03.2015, 09:18

Перемножение матриц, умножение матриц на вектор, сложение матриц
Помогите пожалуйста написать программу, которая производит основные действия с матрицами...

Транспонирование, умножение матриц, сложение матриц Реализовать в одной программере
транспонирование, умножение матриц, сложение матриц; B^3-A^T Реализовать в одной программере....

Скалярное произведение векторов, сложение матриц, транспонирование матриц
Необходимо составить что то вроде калькулятора с процедурами, что бы вычислял скалярное...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru