060_Разреженные матрицы

1.

Разреженные
матрицы
1 из 50

2.

РАЗРЕЖЕННЫЕ МАТРИЦЫ
Разреженными называются матрицы, в которых
количество ненулевых элементов много меньше общего
числа элементов
Хранение разреженной матрицы в памяти должно
обеспечивать:
1) экономию памяти
– N×M – размерность матрицы
– NZ – количество ненулевых элементов
– NZ << N×M.
2) быстрый доступ к нулевым и
ненулевым элементам по их индексу.
2

3.

Координатный формат хранения
□ Матрица хранится в виде трех одномерных массивов:
- Массив значений A
- Массив номеров строк LI
- Массив номеров столбцов LJ
Исходная матрица
Схема хранения
0
0
2
0
0
0
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
9
1
0
0
0
0
0
3
8
0
0
4
0
0
N:
1
2
3
4
5
6
7
A:
2
5
9
1
3
8
4
LJ:
3
2
5
6
6
1
4
LI:
1
3
4
4
5
6
6
3

4.

Координатный формат хранения
Координатный формат может быть:
Упорядоченный (по строкам/столбцам)
o Быстрый доступ к строкам/столбцам
o Необходимость перепаковки при вставке/удалении элементов
Неупорядоченный
o «Переборный» доступ к элементам
o Быстрая вставка/удаление элементов
Затраты памяти для массива с количеством
ненулевыми элементов NZ
NZ ячеек под элементы массива
NZ ячеек под массив LJ
NZ ячеек под массив LI
4

5.

Разреженный строчный формат
CRS (Compressed Row Storage) или CSR(Compressed Sparse Rows)
□ Матрица хранится в виде трех одномерных массивов:
- Массив значений A (построчно, сверху вниз)
- Массив LJ (номера столбцов)
- Массив LI (местоположение первого элемента каждой строки)
□ LI[i] указывает на начало i-ой строки
□ Элементы строки i в массиве A находятся по индексам
от LI[i] до LI[i
+ 1] - 1 включительно
- Обрабатываются пустые строки (LI[p] = LI[p + 1])
- Единообразно обрабатывается последняя строка (LI[N+1]=NZ+1).
5

6.

Разреженный строчный формат
□ Объем памяти для хранения массива N×M с NZ
ненулевыми элементами:
- Массив значений A - NZ ячеек
- Массив LJ – NZ ячеек
- Массив LI - (N+1) ячейка
Исходная матрица
Схема хранения
0
2
0
1
0
0
0
0
0
0
0
0
0
5
0
0
0
1
0
0
0
0
9
1
0
0
0
0
0
0
0
8
0
4
0
3
N:
1
2
3
4
5
6
7
8
9
A:
2
1
5
1
9
1
8
4
3
LJ:
2
4
2
6
5
6
2
4
6
LI:
1
3
3
5
7
7
10
6

7.

Разреженный строчный формат
Алгоритм доступа к элементу с индексами ij:
int procedure(i,j)
{
AA=0; // значение искомого элемента
N1=LI[i];
N2=LI[i+1];
for(k=N1;k<N2;k++)
{
if (LJ[k]==j)
{
AA=A[k];
<break>;
}
}
return AA;
}
7

8.

Модификации формата CRS
□ В CRS строки рассматриваются по порядку (быстрый
доступ к строке), но элементы внутри строки могут быть:
- Упорядочены (быстрый поиск элемента, нужно
поддерживать упорядоченность);
- Не упорядочены (переборный поиск, упорядоченность
не поддерживается).
□ CRS с четырьмя массивами.
- Три массива - аналогично CRS.
- Четвертый массив хранит индексы элементов,
идущих в конце строки.
- Строки могут не быть упорядочены (перестановка строк
проводится без перепаковки, только изменением индексов.
8

9.

Разреженный столбцовый формат
CCS (Compressed Colomn Storage) или CSC(Compressed Sparse Colomns)
□ Матрица хранится в виде трех одномерных массивов:
- Массив значений A (по столбцам, слева на право)
- Массив LI (номера строк)
- Массив LJ (местоположение первого элемента каждого
столбца)
□ LJ[j] указывает на начало j-ого столбца
□ Элементы столбца j в массиве A находятся по индексам
от LJ[j] до LJ[j
+ 1] - 1 включительно
- Обрабатываются пустые столбцы (LJ[p] = LJ[p + 1])
- Единообразно обрабатывается последний столбец (LJ[N+1]=NZ).
9

10.

Разреженный столбцовый формат
□ Объем памяти для хранения массива N×M с NZ
ненулевыми элементами:
- Массив значений A
- NZ ячеек
- Массив LI – NZ ячеек
- Массив LJ - (N+1) ячейка
Исходная матрица
Схема хранения
0
2
0
1
0
0
0
0
0
0
0
0
0
5
0
0
0
1
0
0
0
0
9
1
0
0
0
0
0
0
0
8
0
4
0
3
N:
1
2
3
4
5
6
7
8
9
A:
2
5
8
1
4
9
1
1
3
LI:
1
3
6
1
6
4
3
4
6
LJ:
1
1
4
4
6
7
10
10

11.

Разреженные структурно-симметричные
матрицы
□ Матрица квадратная N×N
□ Условие структурно - симметричности:
- Если aij
≠ 0, то и aji ≠ 0;
- Если aij = 0, то и aji = 0;
□ (2*NZ) – количество ненулевых элементов (за исключением
диагонали)
11

12.

Разреженные структурно-симметричные
матрицы
□ Матрица хранится в виде пяти одномерных массивов:
- Массив для диагонали AD
- Массив элементов стоящих над диагональю AU(по строкам,
сверху вниз)
- Массив элементов стоящих под диагональю AL(по столбцам,
слева на право)
- Массив LJ (номера столбцов элементов, хранимых в матрице
AU или строк, хранимых в матрице AL)
- Массив LI (местоположение первого элемента каждой строки в
AU или каждого столбца в AL)
12

13.

Разреженные структурно-симметричные
матрицы
□ LI[i] указывает на начало i-ой строки в массиве AU
□ Элементы строки i в массиве AU находятся по индексам
от LI[i] до LI[i
+ 1] - 1 включительно
- Обрабатываются пустые строки (LI[p] = LI[p + 1])
- Единообразно обрабатывается последняя строка (LI[N]=NZ+1).
□ LI[j] указывает на начало j-ого столбца в массиве AL
□ Элементы столбца j в массиве AL находятся по индексам
от LI[j] до LI[j
+ 1] - 1 включительно
- Обрабатываются пустые столбцы (LI[p] = LI[p + 1])
- Единообразно обрабатывается последний столбец (LI[N]=NZ+1).
13

14.

Разреженные структурно-симметричные
матрицы
□ Объем памяти для хранения массива N×N с 2*NZ
ненулевыми
элементами (исключая диагональ):
- Массив значений AD - N ячеек
- Массив значений AU - NZ ячеек
- Массив значений AL - NZ ячеек
- Массив LJ – NZ ячеек
- Массив LI - N ячеек
Исходная матрица
Схема хранения
0
2
0
1
0
0
1
0
0
0
0
0
0
0
5
0
0
0
AD:
0
0
5
7
AU:
2
1
9
1
AL:
1
5
4
4
5
0
0
7
9
1
0
0
0
4
0
0
LJ:
2
4
5
6
0
0
0
4
0
3
LI:
1
3
3
3
0
3
5
5
14

15.

Разреженные структурно-симметричные
матрицы
□
Алгоритм доступа
-доступ диагональному элементу тривиален.
-если искомый элемент лежит в верхнем треугольнике,
т.е. i<j, то применяем алгоритм из CRS для массива AU
-если искомый элемент лежит в нижнем треугольнике,
т.е. i>j применяем тот же алгоритм из CСS для массива AL,
заменив в нем i на j
15

16.

Использование связных списков
16

17.

Ленточные матрицы
Матрица A называется ленточной, если все ее ненулевые
элементы заключены внутри ленты, образованной между
диагоналями, параллельными главной.
Свойства ленточных матриц
□ Матрица квадратная N×N
□ aij = 0, при i > (j + р)
(р - нижняя шириной ленты)
□ aij = 0, при j > (i + q),
(q - верхней шириной ленты)
□ величина m = р + q + 1 называется шириной
ленты матрицы A.
17

18.

Ленточные матрицы
верхняя ширина ленты q
ширина
ленты m
размер
квадратной
матрицы - n
Общая ширина
ленты составляет
m=p+q+1
диагональ
нижняя ширина ленты p
18

19.

Ленточный строчный формат матрицы
□ Строчный ленточный формат для хранения исходной
матрицы A использует массив размера NхM, в котором
построчно хранятся ненулевые элементы матрицы А.
□ Побочные диагонали доопределяются нулями до
размерности n:
- в начале диагоналей для нижнего треугольника
- в конце диагоналей для верхнего треугольника.
0
0
ОБЩИЙ ВИД
0
0 0
0 0 0
0
0
0 0
19

20.

Ленточный строчный формат матрицы
□ если aij находятся в пределах упакованного массива, т.е.
- если i < j и (j-i) ≤ q
- если i > j и (i-j) ≤ p
то,
A[i,j] = P[i,j-i+p+1]
Пример хранения
Исходная матрица A
Упакованная матрица P
n=6; p=1; q=2; m=4;
5
8
2
0
0
0
0
5
8
2
7
9
0
8
0
0
7
9
0
8
0
4
0
2
5
0
4
0
2
5
0
0
1
3
9
1
1
3
9
1
0
0
0
0
4
3
0
4
3
0
0
0
0
0
6
0
6
0
0
0
20

21.

Ленточный столбцовый формат матрицы
□ Столбцовый ленточный формат
для хранения исходной матрицы A
использует массив размера MхN, в
котором по столбцам хранятся
ненулевые элементы матрицы А.
0
0 0
0 0 0
□ Побочные диагонали
доопределяются нулями до
размерности n:
- в конце диагоналей для нижнего
треугольника
- в начале диагоналей для верхнего
треугольника.
ОБЩИЙ ВИД
0
000
00
0
0
21

22.

Ленточный столбцовый формат матрицы
Исходная матрица
n=6; p=1; q=2; m=4;
□ если aij находятся в пределах
упакованного массива, т.е.
5
8
2
0
0
0
7
9
0
8
0
0
- если i < j и (j-i) ≤ q
- если i > j и (i-j) ≤ p
0
4
0
2
5
0
то,
0
0
1
3
9
1
0
0
0
0
4
3
0
0
0
0
6
0
0
0
2
8
5
1
0
8
0
2
9
3
5
9
0
3
4
0
7
4
1
0
6
0
Упакованная матрица
A[i,j] = P[i-j+q+1,j]
22

23.

Ленточный формат матрицы
с одинаковыми полуширинами ленты
□ Частный случай ленточной матрицы
- β = p =q – полуширина ленты
- A[i,j]=0 если |i-j|> β
- столбец (β+1) соответствует главной диагонали матрицы А.
□ если |i-j|> β, то aij = 0
□ если |i-j|< β, то A[i,j] = P[i,j-i+β+1]
23

24.

Ленточный формат матрицы
с одинаковыми полуширинами ленты
Пример хранения
Исходная матрица
Упакованная матрица
n=8;
β = p = q = 2; m = 2β +1 = 5;
5
8
2
0
0
0
0
0
0
0
5
8
2
7
9
0
8
0
0
0
0
0
7
9
0
8
1
4
0
2
5
0
0
0
1
4
0
2
5
0
9
1
3
9
1
0
0
9
1
3
9
1
0
0
7
0
4
3
0
0
7
0
4
3
0
0
0
0
0
6
0
0
0
0
6
0
0
0
0
0
0
0
6
0
4
3
6
0
4
3
0
0
0
0
0
0
3
6
0
3
6
0
0
0
24

25.

Диагональный формат хранения
□ Диагональный формат хранения матриц используется, когда все
ненулевые элементы матрицы расположены на различных, не плотно
расположенных- диагоналях.
□ Для хранение используется массив размера N×M, где
- n - размерность исходной матрицы
- m - количество ненулевых диагоналей
□ Побочные диагонали доопределяются до общей размерности
нулями аналогично ленточному формату.
□ Дополнительно хранится массив целых чисел Index размера m, в
котором указывается сдвиг каждой диагонали от главной положительные индексы для верхнего треугольника, отрицательные
для нижнего треугольника.
□ Доступ к элементу A[i,j]
-если элемент (j-i) – есть в матрице Index и он расположен в k-ой
позиции, то берем элемент P[i, k] и 0 – в другом случае
25

26.

Диагональный формат хранения
□ Index будет содержать элементы (-i1;-i2;0;i3;i4;i5;i6;)
i3 i4 i5 i6
i2
i1
главная
диагональ
размер
квадратной
матрицы - n×n
Количество
диагоналей m
26

27.

Диагональный формат хранения
Пример хранения
Исходная матрица
aij, (j-i) k, P[i,k]
Упакованный вид
n=6; m = 4;
5
8
0
1
0
0
0
5
8
1
0
9
0
0
2
0
0
9
0
2
1
0
0
2
0
3
1
0
2
3
0
9
0
3
9
0
9
3
9
0
0
0
7
0
4
3
7
4
3
0
0
0
0
0
0
0
0
0
0
0
Index: -2
0
1
3
27

28.

Общий алгоритм работы с
разреженными матрицами
Неправильная структура программы
ВВОД МАТРИЦЫ
УПАКОВКА МАТРИЦЫ
ОБРАБОТКА МАТРИЦЫ
РАСПАКОВКА МАТРИЦЫ
ВЫВОД МАТРИЦЫ
28

29.

Общий алгоритм работы с
разреженными матрицами
Правильная структура программы
ВВОД МАТРИЦЫ
С УПАКОВКОЙ
ОБРАБОТКА МАТРИЦЫ
РАСПАКОВКА И
ВЫВОД МАТРИЦЫ
29

30.

Недостатки разреженных матриц
□ Работа с разреженной матрицей значительно сложнее, чем со
стандартным массивом.
□ Скорость работы алгоритма использующего разреженную матрицу
значительно увеличивает время решения поставленной задачи по
сравнению с решением той же задачи с помощью стандартных
массивов.
□ Экономия памяти, быстро сводится на нет, если набор данных с
течением времени становится все менее разрежен.
30

31.

Задание на дом «ИГРА ЖИЗНЬ»
□ На сетку наносится начальная (как правило, случайная)
конфигурация, которая далее развивается во времени. Правила, по
которым клетки живут и умирают, следующие:
Количество
занятых
соседних клеток
Процесс
0
Смерть
1
Смерть
2
Выживание
3
Выживание или рождение
4
Смерть
5
Смерть
6
Смерть
7
Смерть
8
Смерть
31

32.

Задание на дом «ИГРА ЖИЗНЬ»
32

33.

Задание на дом «ИГРА ЖИЗНЬ»
33

34.

34