Macierze

WPROWADZENIE

Działania na macierzach kwadratowych potrzebne są w wielu zastosowaniach (algebra, obroty). Zdarza się, że macierze mają dużą liczbę zer (macierze rzadkie). Wtedy można zastosować specjalne struktury danych, aby przyspieszyć obliczenia i zmniejszyć zapotrzebowanie na pamięć. Wg typowej definicji, macierz rzadka ma co najwyżej jeden niezerowy element w każdym wierszu i każdej kolumnie. Przykładem macierzy rzadkiej jest macierz diagonalna.

+----------------+--------+--------+
| Działanie      | Dense  | Sparse |
+----------------+--------+--------+
| dodawanie      | O(n^2) | O(n)   |
| odejmowanie    | O(n^2) | O(n)   |
| transponowanie | O(n^2) | O(n)   |
| mnożenie       | O(n^3) | O(n^2) |
+----------------+--------+--------+

MACIERZE KWADRATOWE GĘSTE (DENSE)

n = 3
# Macierz zerowa to lista list z zerami.
a = [[0]*n for i in range(n)]
a[1][2] = 3         # [[0, 0, 0], [0, 0, 3], [0, 0, 0]]

MACIERZE KWADRATOWE RZADKIE (SPARSE)

# Macierz zerowa to pusty słownik.
a = dict()
a[1, 2] = 3         # {(1, 2): 3}

DODAWANIE MACIERZY

# Dodawanie a + b = c.
c = [[0]*n for i in range(n)]   # macierz zerowa
for i in range(n):
    for j in range(n):
        c[i][j] = a[i][j] + b[i][j]

c = dict()   # macierz zerowa
for pair in a:
    c[pair] = c.get(pair, 0) + a[pair]
# prościej c = dict(a)
for pair in b:
    c[pair] = c.get(pair, 0) + b[pair]

ODEJMOWANIE MACIERZY

# Dodawanie a - b = c.
c = [[0]*n for i in range(n)]   # macierz zerowa
for i in range(n):
    for j in range(n):
        c[i][j] = a[i][j] - b[i][j]

c = dict()   # macierz zerowa
for pair in a:
    c[pair] = c.get(pair, 0) + a[pair]
# prościej c = dict(a)
for pair in b:
    c[pair] = c.get(pair, 0) - b[pair]

TRANSPONOWANIE MACIERZY

# Otrzymujemy a_tr.
a_tr = [[0]*n for i in range(n)]   # macierz zerowa
for i in range(n):
    for j in range(n):
        a_tr[j][i] = a[i][j]

a_tr = dict()   # macierz zerowa
for (row, col) in a:
    a_tr[col, row] = a[row, col]

MNOŻENIE MACIERZY

# Mnożenie a * b = c.
c = [[0]*n for i in range(n)]   # macierz zerowa
for i in range(n):
    for j in range(n):
        for k in range(n):
            c[i][j] = c[i][j] + a[i][k] * b[k][j]

# Przygotowanie do uogólnienia.
for i in range(n):
    for j in range(n):
        for k in range(n):
            for s in range(n):
                if k == s:
                    c[i][j] = c[i][j] + a[i][k] * b[s][j]

c = dict()   # macierz zerowa
for (row1, col1) in a:
    for (row2, col2) in b:
        if col1 == row2:
            c[row1, col2] = c.get((row1, col2), 0) + a[row1, col1] * b[row2, col2]