稀疏矩陣

December 12, 2021

如果矩陣中多數元素沒有資料,稱為稀疏矩陣(sparse matrix),會造成記憶體空間的浪費,必要時可設計稀疏矩陣的儲存方式,利用較少記憶體儲存完整的矩陣資訊。

解法思路

一個儲存稀疏矩陣的簡單方式是,只儲存矩陣行數、列數、有資料的索引、值,需要矩陣資料時再還原,例如,若矩陣資料如下,其中 0 表示矩陣中該位置沒有資料:
0 0 0 0 0 0
0 3 0 0 0 0
0 0 0 6 0 0
0 0 9 0 0 0
0 0 0 0 12 0
這是個 5 x 6 矩陣,有 4 個非零元素,可使用陣列第一列記錄列數、行數與非零元素個數:

5 6 4

陣列的第二列起,記錄有資料位置的列索引、行索引與值:
1 1 3
2 3 6
3 2 9
4 4 12

原本要用 30 個元素儲存的矩陣資訊,現在只使用了 15 個元素來儲存,節省了記憶體的使用。

程式實作

#include <stdio.h> 
#include <stdlib.h> 

int main(void) { 
    int num[5][3] = {{5, 6, 4}, 
                     {1, 1, 3}, 
                     {2, 3, 6}, 
                     {3, 2, 9}, 
                     {4, 4, 12}}; 

    int k = 1;
    int i;
    for(i = 0; i < num[0][0]; i++) { 
        int j;
        for(j = 0; j < num[0][1]; j++) { 
            if(k <= num[0][2] && 
               i == num[k][0] && j == num[k][1]) { 
                printf("%4d ", num[k][2]); 
                k++; 
            } 
            else 
                printf("%4d ", 0); 
        } 
        putchar('\n'); 
    } 

    return 0; 
} 
public class Matrix {
    public static int[][] restore(int[][] sparse) {
        int row = sparse[0][0];
        int column = sparse[0][1];        
        int[][] array = new int[row][column];
        
        for(int i = 0, k = 1; i < row; i++) { 
            for(int j = 0; j < column; j++) { 
                if(k <= sparse[0][2] && 
                    i == sparse[k][0] && j == sparse[k][1]) { 
                    array[i][j] = sparse[k][2]; 
                    k++; 
                } 
                else {
                    array[i][j] = 0; 
                }
            }  
        } 
        
        return array;
    }

    public static void main(String[] args) {
        int[][] sparse = {{5, 6, 4}, 
                          {1, 1, 3}, 
                          {2, 3, 6}, 
                          {3, 2, 9}, 
                          {4, 4, 12}};
        
        for(int[] arr : Matrix.restore(sparse)) {
            for(int elm : arr) {
                System.out.print(elm + " ");
            }
            System.out.println();
        }
    }
}
def restore(sparse):
    row = sparse[0][0]
    column = sparse[0][1]
    array = [[0] * column for i in range(row)]
    k = 1
    for i in range(row):
        for j in range(column):
            if k <= sparse[0][2] and \
               i == sparse[k][0] and j == sparse[k][1]:
               array[i][j] = sparse[k][2]
               k += 1
            else:
                array[i][j] = 0
    return array

sparse = [
             [5, 6, 4], 
             [1, 1, 3], 
             [2, 3, 6],
             [3, 2, 9], 
             [4, 4, 12]
          ]
array = restore(sparse)
print(array)
object Matrix {
    def restore(sparse: Array[Array[Int]]) = {
        val row = sparse(0)(0)
        val column = sparse(0)(1)
        val array = new Array[Array[Int]](row, column)
        var k = 1
        for(i <- 0 until row; j <- 0 until column) {
            if(k <= sparse(0)(2) && i == sparse(k)(0) && j == sparse(k)(1)) {
                array(i)(j) = sparse(k)(2)
                k += 1
            }
            else {
                array(i)(j) = 0
            }
        }
        array
    }
}

val sparse = Array(
                 Array(5, 6, 4),
                 Array(1, 1, 3),
                 Array(2, 3, 6),
                 Array(3, 2, 9),
                 Array(4, 4, 12)
             )
Matrix.restore(sparse).foreach(arr => {
    arr.foreach(elm => print(elm + " "))
    println()
})
def restore(sparse)
    row = sparse[0][0]
    column = sparse[0][1]
    array = Array.new(row) {
        Array.new(column, 0)
    }
    k = 1
    row.times { |i|
        column.times { |j|
            if k <= sparse[0][2] &&
               i == sparse[k][0] && j == sparse[k][1]
                array[i][j] = sparse[k][2]
                k += 1
            else
                array[i][j] = 0
            end
        }
    }
    array
end

sparse = [
             [5, 6, 4], 
             [1, 1, 3], 
             [2, 3, 6],
             [3, 2, 9], 
             [4, 4, 12]
          ]
array = restore(sparse)
p array