什么是稀疏矩陣

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

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

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

1.直接存儲(chǔ)為二維矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

存儲(chǔ)的三個(gè)數(shù)組：

• 值 =\>單元格中的值。
• 行索引=\>單元格的行索引。
• 列偏移=\>這里每個(gè)索引都代表列，并且該數(shù)組將行開始的索引值存儲(chǔ)在 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);
    }
}

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

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

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

總結(jié)

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

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

最新評(píng)論