稀疏矩陣的概念

一個(gè)m×n的矩陣是一個(gè)由m行n列元素排列成的矩形陣列。矩陣?yán)锏脑乜梢允菙?shù)字、符號(hào)及其他的類型的元素。

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

我們?nèi)粘Ｊ褂玫碾娮颖砀褚彩且粋€(gè)典型的稀疏矩陣場(chǎng)景，電子表格（SpreadJS, Excel，Google Sheet等等），整體看起來像一個(gè)table表格。

其中列名稱依次為A, B, C … …， 行名稱依次為1, 2, 3 … …

舉例一個(gè)比較極端的場(chǎng)景，在A1和ZZ2000單元格分別賦值，這樣我們就需要一個(gè)2000行，26*26 26=702列的矩陣來表示它，這個(gè)矩陣是一個(gè)明顯的稀疏矩陣。

稀疏矩陣的存儲(chǔ)方式及優(yōu)化

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

直接使用二維矩陣會(huì)簡(jiǎn)單直接地存儲(chǔ)整個(gè)電子表格，這樣你不必每次都創(chuàng)建或刪除一段內(nèi)存。
但這是一種非常暴力的存儲(chǔ)值的方法，這種方式下會(huì)消耗大量?jī)?nèi)容來存儲(chǔ)毫無內(nèi)容的單元格。
簡(jiǎn)單來看一下它的復(fù)雜度：

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

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

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

在這種方法中，只有在單元格有值時(shí)，我們才將單元格的值和位置存儲(chǔ)在一起，使用HashMap或者Dictionary這些數(shù)據(jù)結(jié)構(gòu)可以很容易的做到。

下圖我們可以看到，鍵值對(duì)中分別存儲(chǔ)了單元格位置和單元格值。

來看一下它的復(fù)雜度：

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

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

通過稀疏矩陣存儲(chǔ)方式優(yōu)化

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

1. 值 =>單元格中的值。
2. 行索引=>單元格的行索引。
3. 列偏移=>這里每個(gè)索引都代表列，并且該數(shù)組將行開始的索引值存儲(chǔ)在 Row 數(shù)組中。

左圖中的稀疏矩陣被存儲(chǔ)為右圖的三個(gè)數(shù)組：

稀疏矩陣具體的插入、刪除、搜索、訪問的代碼，大家可以自己來搜索，這方面的資料網(wǎng)上有很多，這里不一一列舉。

和上面一樣，來看看這種方式的復(fù)雜度：

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

相較于傳統(tǒng)的數(shù)組存儲(chǔ)或是鍵值對(duì)存儲(chǔ)，稀疏矩陣存儲(chǔ)構(gòu)建了基于行索引為 Key 的數(shù)據(jù)字典，在松散布局的表格數(shù)據(jù)中，稀疏矩陣只會(huì)對(duì)非空數(shù)據(jù)進(jìn)行存儲(chǔ)，而不需要對(duì)空數(shù)據(jù)開辟額外的內(nèi)存空間。使用這種特殊的存儲(chǔ)策略，使得數(shù)據(jù)片段化變得容易，可以隨時(shí)框取整個(gè)數(shù)據(jù)層中的一片數(shù)據(jù)，進(jìn)行序列化或反序列化。如果我們?cè)陧?xiàng)目開發(fā)中需要存儲(chǔ)類似結(jié)構(gòu)的數(shù)據(jù)，稀疏矩陣這種存儲(chǔ)方式，無論從時(shí)間還是空間上都能大大地提升性能。

在葡萄城的 SpreadJS 和 GcExcel 表格組件中，也巧妙地使用了稀疏矩陣這一特性，可以隨時(shí)替換或恢復(fù)整個(gè)存儲(chǔ)結(jié)構(gòu)中的任何一個(gè)級(jí)別的節(jié)點(diǎn)，以改變引用的方式更高效地解決表格數(shù)據(jù)回滾和恢復(fù)問題，而這一點(diǎn)也為葡萄城表格組件支持多人在線協(xié)同打下了一個(gè)良好的基礎(chǔ)。

由于底層采用了稀疏矩陣來優(yōu)化存儲(chǔ)，SpreadJS在前端頁面中，實(shí)現(xiàn)了100W級(jí)別數(shù)據(jù)秒級(jí)響應(yīng)的能力：

純前端百萬級(jí)數(shù)據(jù)請(qǐng)求、加載、篩選和排序

點(diǎn)擊此處可以在線體驗(yàn)：性能演示

同時(shí)，結(jié)合SpreadJS中使用的Canvas 繪制模型，雙緩存畫布渲染等專利技術(shù)，讓SpreadJS的前端性能相比于同類產(chǎn)品遙遙領(lǐng)先。