稀疏矩陣的概念

一個m×n的矩陣是一個由m行n列元素排列成的矩形陣列。矩陣里的元素可以是數(shù)字、符號及其他的類型的元素。

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

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

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

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

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

直接存儲為二維矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

點擊此處可以在線體驗：性能演示

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