什么是稀疏矩陣

稀疏矩陣是指矩陣中大部分元素為零的矩陣。在實際應(yīng)用中，很多矩陣都是稀疏的，比如網(wǎng)絡(luò)圖、文本數(shù)據(jù)等。由于矩陣中存在大量的零元素，因此稀疏矩陣的存儲和計算都具有一定的特殊性。

一般來說，在矩陣中，若數(shù)值為0的元素數(shù)目遠遠多于非0元素的數(shù)目，并且非0元素分布沒有規(guī)律時，則稱該矩陣為稀疏矩陣；與之相反，若非0元素數(shù)目占大多數(shù)時，則稱該矩陣為稠密矩陣。下面的矩陣就是一個典型的稀疏矩陣：

優(yōu)化稀疏矩陣數(shù)據(jù)存儲的方法

1.直接存儲為二維矩陣

使用二維矩陣作為電子表格的存儲方法具有簡單直接的優(yōu)點，可以避免頻繁地創(chuàng)建或刪除內(nèi)存段。然而，需要指出的是，這種方式在存儲值時可能會有一些不太高效的方面，因為它會占用大量的存儲空間來保存沒有實際內(nèi)容的單元格。

在實際應(yīng)用中通常使用三元組表示稀疏矩陣：

三元組的表示方法是：對于一個 m×n 的稀疏矩陣 A，我們只存儲矩陣中非零元素的信息，具體來說，將每個非零元素的行下標(biāo)、列下標(biāo)和值存儲下來，得到一個三元組(i,j,Ai,j)，其中 i 是行下標(biāo)，j 是列下標(biāo)，Ai,j 是 A 中對應(yīng)位置的值。

以前面舉的稀疏矩陣為例，其三元組表示如下：

(1, 4, 6)
(2, 2, 5)
(3, 3, 4)

直接存儲為二維矩陣的復(fù)雜度：

• 占用空間：O(N2) 。
• 插入數(shù)據(jù)：需要破壞矩陣。
• 刪除數(shù)據(jù)：需要破壞矩陣。
• 搜索數(shù)據(jù)：O(N2)。
• 訪問數(shù)據(jù)：O(1)。

N是假設(shè)行和列具有相同長度并形成正方形矩陣的行/列數(shù)。

2.通過鍵值對(Map, Dictionary)優(yōu)化

通過鍵值對(Map, Dictionary)來優(yōu)化，主要是利用哈希表的特性來快速查找元素。具體來說，可以將需要查找的元素作為鍵，將存儲這些元素的數(shù)據(jù)結(jié)構(gòu)作為值，然后將它們存儲在一個哈希表中。這樣，當(dāng)需要查找某個元素時，只需要使用該元素作為鍵，通過哈希表的查找操作即可快速找到對應(yīng)的值。

在實際應(yīng)用中，常見的情況包括：

• 緩存數(shù)據(jù)：在需要頻繁訪問數(shù)據(jù)的場景中，通過建立一個緩存，將數(shù)據(jù)存儲在一個鍵值對的數(shù)據(jù)結(jié)構(gòu)中，可以顯著提高數(shù)據(jù)的訪問效率。
• 字符串處理：在需要對字符串進行匹配、查找等操作的場景中，可以將字符串作為鍵，將相應(yīng)的處理結(jié)果作為值，存儲在一個鍵值對的數(shù)據(jù)結(jié)構(gòu)中，可以大幅提高字符串處理的效率。
• 數(shù)據(jù)庫操作：在需要對數(shù)據(jù)庫進行訪問的場景中，可以使用鍵值對數(shù)據(jù)結(jié)構(gòu)來存儲查詢結(jié)果，避免重復(fù)執(zhí)行查詢操作，減輕數(shù)據(jù)庫的負載。

在下圖中，將單元格位置和對應(yīng)的單元格值以鍵值對的形式進行了存儲。

通過鍵值對(Map, Dictionary)優(yōu)化稀疏數(shù)組的復(fù)雜度：

• 空間：O(N)。
• 插入：O(1)。
• 刪除：O(1)。
• 搜索：O(N)。
• 訪問：O(1)。

N為所記錄的條目數(shù)。

3.通過數(shù)組存儲方式優(yōu)化

在稀疏矩陣中，我們可以使用三個不同的數(shù)組來存儲行索引、列偏移、和其中的值，而不是直接在二維矩陣中存儲值。

存儲的三個數(shù)組：

• 值 =\>單元格中的值。
• 行索引=\>單元格的行索引。
• 列偏移=\>這里每個索引都代表列，并且該數(shù)組將行開始的索引值存儲在 Row 數(shù)組中。

下圖為將稀疏數(shù)組轉(zhuǎn)化為數(shù)組的形式：

稀疏矩陣具體的插入，刪除，搜索，訪問的代碼：

import java.util.HashMap;
import java.util.Map;
class SparseMatrix {
    private int rows;
    private int cols;
    private Map<String, Integer> matrix;
    public SparseMatrix(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.matrix = new HashMap<>();
    }
    public void insert(int row, int col, int value) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            throw new IndexOutOfBoundsException("Invalid matrix index");
        }
        if (value != 0) {
            String key = row + "," + col;
            matrix.put(key, value);
        }
    }
    public void delete(int row, int col) {
        String key = row + "," + col;
        matrix.remove(key);
    }
    public int search(int row, int col) {
        String key = row + "," + col;
        return matrix.getOrDefault(key, 0);
    }
    public int access(int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            throw new IndexOutOfBoundsException("Invalid matrix index");
        }
        String key = row + "," + col;
        return matrix.getOrDefault(key, 0);
    }
}

在上述代碼中，定義了一個 SparseMatrix 類來表示稀疏矩陣。在構(gòu)造函數(shù)中，我們傳入矩陣的行數(shù)和列數(shù)，并創(chuàng)建了一個 HashMap 對象 matrix 來存儲非零元素。insert 方法用于向矩陣中插入元素，如果插入的值不為零，則將其加入 matrix 中，其中鍵為字符串形式的 row,col。delete 方法用于刪除指定位置的元素，通過 remove 方法從 matrix 中移除對應(yīng)的鍵值對。search 方法用于搜索指定位置的元素，通過調(diào)用 getOrDefault 方法從 matrix 中獲取對應(yīng)的值，如果不存在則返回默認值 0。access 方法用于訪問指定位置的元素，如果超出矩陣邊界則拋出異常，通過調(diào)用 getOrDefault 方法從 matrix 中獲取對應(yīng)的值。

通過稀疏矩陣存儲方式優(yōu)化的復(fù)雜度：

• 空間：O(N)。
• 插入：O(N)。
• 刪除：O(N)。
• 搜索：O(N)。
• 訪問：O(1)。

總結(jié)

相較于傳統(tǒng)的數(shù)組存儲或鍵值對存儲，稀疏矩陣存儲采用一種基于行索引的數(shù)據(jù)字典存儲方法，這種方法在處理松散布局的表格數(shù)據(jù)時表現(xiàn)出色。與其他存儲方式不同，稀疏矩陣只存儲非空數(shù)據(jù)，無需額外開辟內(nèi)存空間來存儲空數(shù)據(jù)。這種特殊存儲策略使得數(shù)據(jù)片段化變得容易，可以隨時框取整個數(shù)據(jù)層中的一片數(shù)據(jù)進行序列化或反序列化。如果在項目開發(fā)中需要存儲類似結(jié)構(gòu)的數(shù)據(jù)，使用稀疏矩陣存儲方式能夠顯著提升性能，無論從時間還是空間上都有很大的優(yōu)勢，葡萄城公司的純前端表格控件——SpreadJS正是借助此功能實現(xiàn)了高性能渲染能力（100 毫秒內(nèi)加載 10 萬行數(shù)據(jù)）。

以上就是解析java稀疏數(shù)組如何幫助我們節(jié)省內(nèi)存提升性能的詳細內(nèi)容，更多關(guān)于java稀疏數(shù)組提升內(nèi)存的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論