JAVA稀疏矩陣算法

陳新龍

假設(shè)我們要編寫一個五子棋的程序，過程中需要考慮保存黑棋和白棋的位置，這個時候你會用什么樣的解決方法呢？相信很多人第一時間想到的肯定是二維數(shù)組（Array[x][y]），因為二維數(shù)組本質(zhì)上是以數(shù)組作為數(shù)組元素的數(shù)組。數(shù)組的X坐標正好對應(yīng)棋盤上的X軸，Y坐標正好對應(yīng)棋盤上的Y坐標，例如圖1中黑色棋子的位置就是（1，2），藍色棋子的位置就是（2，3）;將對應(yīng)棋盤中的棋子通過數(shù)字的形式存入到二維數(shù)組中，0代表不存在任何數(shù)字，1代表黑色棋子，2代表藍色棋子（圖1）。

雖然通過二維數(shù)組的方法可以保存棋盤的位置，但是保存過程中會出現(xiàn)一個問題，比如數(shù)組中的0太多了，因為二維數(shù)組中很多值都是默認值0，如果把這些0記錄下來就會產(chǎn)生很多沒有意義的數(shù)組，為了解決重復(fù)性的問題，我們可以考慮使用稀疏矩陣數(shù)組來解決問題。

什么是稀疏矩陣呢？矩陣是一個由m行和n列組成的二維數(shù)據(jù)對象，因此一共有m×n個數(shù)值。當這個矩陣的絕大部分數(shù)值為零，且非零元素呈不規(guī)律分布時，則稱該矩陣為稀疏矩陣。如上圖就是一個11×11的稀疏矩陣，由于稀疏矩陣含有許多數(shù)值為零的元素，我們可以運用特定算法做很多重要的事情：比如壓縮矩陣對象的內(nèi)存空間、加速多數(shù)機器學習程序等。

存儲稀疏矩陣時在普通情況下必須為矩陣中的每個零值位點分配32位乃至64位存儲器，這明顯是過于浪費內(nèi)存資源的行為，因為這些零值不包含任何信息。我們可以利用壓縮技術(shù)使我們需要存儲的數(shù)據(jù)量最小化。稀疏矩陣中有很多零值，我們也知道零乘以任何數(shù)還是零，如果依然按照常規(guī)辦法計算機就會不可避免地進行很多無意義的運算，大大拖延了處理時間。顯然，只操作那些返回非零數(shù)值的元素才是更加有效率的辦法。而稀疏矩陣數(shù)組正可以將無意義的零值從運算中剔除出去，因此，任何用到基本數(shù)學運算（比如乘法）的算法都能從稀疏矩陣實施中獲益。

當一個數(shù)組中大部分元素為0，或者為同一個值的數(shù)組時，可以使用稀疏數(shù)組來保存該二維數(shù)組。其實稀疏數(shù)組的處理方法并沒有多么復(fù)雜。首先需要記錄數(shù)組一共有幾行幾列，并記錄數(shù)組中一共有多少個不同的數(shù)字，其次把不同數(shù)值的元素和行列及值記錄在一個更小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模。當然這個過程是可逆的，還可以通過稀疏數(shù)組還原成原始的二維數(shù)組（圖2）。

創(chuàng)建一個原始的二維數(shù)組（11×11）并給數(shù)組中的所有元素賦予初始值0，將棋盤上的黑棋和藍棋的坐標表示在二維數(shù)組中（0：表示沒有棋子;1：表示黑棋;2：表示藍棋）。通過遍歷原始的二維數(shù)組，我們可以得到有效數(shù)據(jù)的個數(shù)并存入sum中。根據(jù)sum的個數(shù)可以創(chuàng)建稀疏數(shù)組sparseArr int[sum+1][3]。你可能會奇怪sparseArr稀疏數(shù)組中Y坐標的值為什么是3，其實這個數(shù)字3代表的是row【橫坐標】、col【縱坐標】、val【數(shù)值】，存放有效數(shù)據(jù)的數(shù)據(jù)坐標。通過遍歷的方式將有效的數(shù)據(jù)存入到稀疏數(shù)組中即可。

下面給大家展示一下代碼核心部分，有興趣的同學還可以思考一下從稀疏數(shù)組轉(zhuǎn)換為原始的二維數(shù)組的過程哦（圖3、圖4）。

當然稀疏數(shù)組不僅僅適合用在五子棋中，掃雷、圍棋等一系列無效數(shù)據(jù)較多或矩陣中也可以用，你還能不能舉出稀疏數(shù)組的案例呢？