稀疏矩陣

說明

如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（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

這個矩陣是5X6矩陣，非零元素有4個，您要使用的陣列第一列記錄其列數、行數與非零元素個數：

5 6 4

陣列的第二列起，記錄其位置的列索引、行索引與儲存值：

1 1 3
2 3 6
3 2 9
4 4 12

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

實作：C Java Python Scala aaas

#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; 
}

Java

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();
        }
    }
}

Python

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)

Scala

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()
})

Ruby

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