โปรแกรม C++ ตรวจสอบ Sparse Matrix (เมทริกซ์ลischt)

Sparse Matrix (เมทริกซ์ลischt) คือ เมทริกซ์ที่ส่วนใหญ่ของสมาชิกเป็นศูนย์ (0) โดยทั่วไปถ้าจำนวน 0 มากกว่าครึ่งหนึ่งของสมาชิกทั้งหมด จะถือว่าเป็น Sparse Matrix

ตัวอย่าง

Matrix 3x3:
5 0 0
3 0 1
0 0 9

จำนวน 0 = 5 จาก 9 ช่อง (55.5%) → Sparse Matrix ✓

โค้ดโปรแกรมตรวจสอบ Sparse Matrix

#include <iostream>
using namespace std;

int main() {
    int a[10][10] = {
        {0, 0, 9},
        {5, 0, 8},
        {7, 0, 0}
    };
    
    int row = 3, col = 3;
    int count = 0;
    
    // นับจำนวนศูนย์
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (a[i][j] == 0)
                count++;
        }
    }
    
    // แสดงเมทริกซ์
    cout << "The matrix is:" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    
    cout << "Number of zeros: " << count << endl;
    
    // ตรวจสอบ Sparse Matrix
    int total = row * col;
    if (count > total / 2)
        cout << "This is a sparse matrix" << endl;
    else
        cout << "This is not a sparse matrix" << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

The matrix is:
0 0 9
5 0 8
7 0 0
Number of zeros: 5
This is a sparse matrix

การจัดเก็บ Sparse Matrix อย่างมีประสิทธิภาพ

แทนที่จะเก็บทั้งเมทริกซ์ (waste memory) ใช้รูปแบบ Compressed Format:

1. Coordinate List (COO) - Triplets

เก็บเฉพาะ (row, col, value) ของค่าที่ไม่ใช่ 0
(0, 2, 9)
(1, 0, 5)
(1, 2, 8)
(2, 0, 7)

2. Compressed Sparse Row (CSR)

values:     [9, 5, 8, 7]
col_index:  [2, 0, 2, 0]
row_ptr:    [0, 1, 3, 4]  // index เริ่มต้นของแต่ละแถวใน values

3. Compressed Sparse Column (CSC)

คล้าย CSR แต่บีบอัดตามคอลัมน์

โค้ดแปลงเป็น COO Format

#include <iostream>
#include <vector>
using namespace std;

struct Triplet {
    int row, col, value;
};

int main() {
    int a[3][3] = {{0,0,9}, {5,0,8}, {7,0,0}};
    vector<Triplet> sparse;
    
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (a[i][j] != 0)
                sparse.push_back({i, j, a[i][j]});
    
    cout << "COO Format (row, col, value):" << endl;
    for (auto& t : sparse)
        cout << "(" << t.row << ", " << t.col << ", " << t.value << ")" << endl;
    
    cout << "Space saved: " << (9 - sparse.size()*3) << " integers" << endl;
    return 0;
}

ผลลัพธ์

COO Format (row, col, value):
(0, 2, 9)
(1, 0, 5)
(1, 2, 8)
(2, 0, 7)
Space saved: 9 - 12 = -3 (สำหรับเมทริกซ์เล็ก ใช้พื้นที่มากกว่า)

เมื่อไหร่ควรใช้ Sparse Matrix Storage?

• เมทริกซ์ขนาดใหญ่ (1000x1000 ขึ้นไป)
• Density (Non-zero %) ต่ำกว่า 10-20%
• ต้องทำ Matrix Operations (Multiply, Solve) บ่อย
• ใช้ Library: Eigen, Armadillo, SuiteSparse

การดำเนินการบน Sparse Matrix

nnz = number of non-zero elements