矩陣的壓縮存儲
- 2019 年 10 月 3 日
- 筆記
前言
一入編程深似海，從此磚頭是愛人，日日搬，夜夜搬，搬到天荒地老，精盡人亡，直教人失去了自我，忘記了時間，忽然之間發現九月份快沒了，趕緊寫篇部落格打個卡，證明一下我還活著。。。
數組與矩陣
數組是由一組相同類型的數據元素構成的有限序列，訪問數據元素的方式是使用元素各自的序號進行訪問，也就是下標。數組它本身是線性表的推廣，一維數組就是一個向量形式的線性表，二維數組就是由一維數組組成的線性表。
在許多科學計算和工程應用中，經常要用到矩陣的概念，我們用的最多的其實就是Mysql的表，表數據都是行列存儲，這就是矩陣。
由於矩陣具有元素數目固定以及元素按下標關係有序排列等特點，所以在使用高級語言編程時，一般都是用二維數組來存儲矩陣。
數組的順序存儲
為什麼是順序存儲？
我想問這個問題就太低級了。因為它是數組，數據的存儲方式分為順序存儲和鏈式存儲兩種，數組一旦被定義，他的維數和維界就已固定，除結構的初始化和銷毀外，數組只會有存取元素和修改元素的操作，不存在插入和刪除操作，所以數組適合用順序存儲。
數組存放在記憶體中的映射關係
數組可以是多維的，但是記憶體空間卻是一維的，所以我們就要把多維數組通過一定的映射順序把它變成一維的，然後存儲到記憶體空間之中。
在大多數高級程式語言中，多維數組在記憶體中通常有兩種不同的順序存儲方式，按行優先順序存儲 和 按列優先順序存儲。
舉個例子，以下3行4列的一個二維數組矩陣：
a1,a2,a3,a4
b1,b2,b3,b4
c1,c2,c3,c4
按行優先順序存儲：
按列優先順序存儲：
地址計算
地址計算的意思就是給定數組下標，求在一維記憶體空間的地址，從而取出數據。
我們先來看一維數組的地址計算
一維數組內的元素只有一個下標，存儲方法和普通的線性表一樣。
如一維數組 A = [a1,a2,a3,……ai,………,an]，每個元素佔用size個存儲單元（就是記憶體大小），那麼元素ai的存儲地址為 A[0]的位置 + (i-1)*size
再來看二維數組的地址計算
以二維數組Amn為例，首元素為A[0][0]，數組中任意元素A[i][j]的地址為：A[0][0]的位置 + （n * (i-1) + (j-1)）* size；
比如：一個5行4列的二維數組A，按行存儲，其中每個元素佔2個存儲單元，首元素地址是1000，求第3行第2列的元素在記憶體中的地址。
我們把參數套進公式中，答案 = 1000 + (4 * (3-1) + (2-1)) * 2 = 1018;
如果把矩陣畫在紙上觀察就一目了然：
公式的內容就是求出格子數，乘以每個格子所佔用的存儲單元，再加上首地址。
矩陣轉置
設計一個演算法，實現矩陣A(m*n) 轉置為矩陣B(n*m)，簡單的說，就是行列互換。
$arr = [ ['張三','男','北京'], ['李四','女','上海'], ['王五','男','廣州'], ]; function transpose($a){ $b = []; for ($i = 0;$i < count($a); $i ++){ for($j = 0;$j < count($a[$i]); $j ++){ $b[$j][$i] = $a[$i][$j]; } } return $b; } $result = transpose($arr);
結果為：
$result = [
[‘張三’,’李四’,’王五’],
[‘男’,’女’,’男’],
[‘北京’,’上海’,’廣州’],
];
特殊矩陣
特殊矩陣的壓縮存儲
特殊矩陣指的是具有許多相同元素或者零元素，並且這些元素的分布有一定規律性的矩陣。
這種矩陣如果還使用前面的方式來存儲，就會產生大量的空間浪費，為了節省存儲空間，可以對這類矩陣採用壓縮存儲，壓縮存儲的方式是把那些呈現規律性分布的相同元素只分配一個存儲空間，對零元素不分配存儲空間。
三角矩陣
三角矩陣我們以下三角來做例子，如圖所示：
所有空格之中裝的數據都是null或者都是同一常量，也就是空格中全都是相同的數據。
按行方式存儲的情況下，一維存儲記憶體空間的大小是：1+2+3+4+5+6+7 = n(n+1)/2 = 7 * (7+1) / 2 = 28，當然，在最後還要加一個存儲空間，用來存儲上三角中相同的數據。
那麼對於任意元素aij，在一維存儲記憶體空間中的地址仍然是要靠計算格子來得到，先算出佔滿行的總格子數，再加上當前行的格子數：a[0][0]的位置 + (i * (i+1) / 2 + j) * size;
我們使用公式來驗證一下，a42的所在格子數 = (i * (i+1) / 2 + j) = 4 * 5 / 2 + 2 = 12
帶狀矩陣
帶狀矩陣也叫做對角矩陣，如圖所示：
帶狀矩陣的特徵是：所有非0元素都集中在以主對角線為中心的3條對角線區域，其他區域的元素都為0。
除了第一行和最後一行僅2個非零元素，其餘行都是3個非零元素，換句話說就是每行都是3個非零元素，但是第一行少了1個，最後一行少了1個，所以所需的一維空間大小為：3n – 2；
那麼對於任意一個元素 aij，怎麼計算它在記憶體空間的地址呢？
經過觀察可以得知i和j都在對角線附近，相減後的結果與分布情況分別如下
j – i = 1；對角線上面
j – i = 0; 對角線
j – i = -1;對角線下面
不管是在對角線的哪個位置，我們都可以使用通用的辦法來計算地址，也就是先計算出上面行所佔的格子，再加上當前行的格子。
上面的行數：i，由於行列都是0開頭計數，所以上面的行數就是i這個值。
上面的格子數： 3 * i – 1，減1是因為第一行少一個格子。
當前行格子數： j – i + 1；根據i和j的關係，我們把相減後的值加1，得到當前行的格子數。
那麼最後aij的記憶體地址 = a00首地址 + ((3 * i -1) + ( j-i+1)) * size； size為每個數據所佔用的存儲單元大小。
比如首地址為1000，每個數據佔用2個存儲單元，那麼a45在記憶體中的地址 = 1000 + 13 * 2 = 1026；
稀疏矩陣的壓縮存儲
由於特殊矩陣中非零元素的分布是有規律的，所以總是可以找到矩陣元素與一維數組下標的對應關係，但還有一種矩陣，矩陣中大多數元素都為0，一般情況下非零元素個數只佔矩陣元素總數的30%以下，並且元素的分布是沒有任何規律的，這樣的矩陣我們稱為稀疏矩陣。
如果採用常規方法存儲稀疏矩陣，就會相當浪費存儲空間，因此我們需要只存儲非零元素。由於稀疏矩陣中非零元素的分布是沒有規律的，所以除了存儲非零元素的值之外，我們還需要同時存儲非零元素的行、列位置，也就是三元組（i,j,aij）。
如圖：
所謂三元組，也就是一個矩陣，一個二維數組，每一行都三個列，分別為行號、列號、元素值。
由於三元組在稀疏矩陣與記憶體地址間扮演了一個中間人的角色，所以稀疏矩陣進行壓縮存儲後，便失去了隨機存取的特性。
