稀疏矩陣

如果矩陣中多數元素沒有資料，稱為稀疏矩陣（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++; 
                } 
            }  
        } 
        
        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
    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
            }
        }
        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
            end
        }
    }
    array
end

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

function restore(sparse) {
    let row = sparse[0][0];
    let column = sparse[0][1];
    let array = [];
    for(let i = 0; i < row; i++) {
        let lt = [];
        lt.length = column;
        lt.fill(0);
        array.push(lt);
    }
    
    let k = 1;
    
    for(let i = 0; i < row; i++) {
        for(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 += 1;
            }
        }
    }

    return array;
}

let sparse = [
                 [5, 6, 4], 
                 [1, 1, 3], 
                 [2, 3, 6],
                 [3, 2, 9], 
                 [4, 4, 12]
             ];

console.log(restore(sparse));

slice :: Int -> Int -> [a] -> [a]
slice start stop xs = take (stop - start) (drop start xs)

updated i j v mx =
    let 
        row = mx !! i
        updatedRow = (slice 0 j row) ++ [v] ++ (slice (j + 1) (length row) row)
        before = slice 0 i mx
        after = slice (i + 1) (length mx) mx
    in before ++ [updatedRow] ++ after
    
restore sparse =
    let 
        [row, column, n] = sparse !! 0
        restored = replicate row $ replicate column 0
    in _restore (slice 1 (length sparse) sparse) restored
    
_restore (x:xs) restored =
    let 
        [i, j, v] = x
        nRestored = (updated i j v restored)
    in
    if null xs 
    then nRestored
    else _restore xs (updated i j v restored)

main = print $ restore [
    [5, 6, 4], 
    [1, 1, 3], 
    [2, 3, 6],
    [3, 2, 9], 
    [4, 4, 12]]