兩個實用的稀疏矩陣函數: nnz和nonzeros

來自專欄 MATLAB

封面圖片可以通過下面命令得到:

spy

這個算是MATLAB的一個彩蛋.

spy函數是用來可視化稀疏矩陣的. 藍色的像素點是矩陣的一個非零元素, 白色(空白)的像素點為零元素.

稀疏矩陣可以用在矩陣元素大部分為0的情況, 這種情況下, 使用稀疏矩陣這種數據格式可以用來: 1 節省空間 2 加快速度.

這是很明顯的, 稀疏矩陣只要考慮那些非零元素即可.

有興趣的讀者可以在命令行中輸入下面命令, 查看相關的幫助:

web(fullfile(docroot, matlab/sparse-matrices.html))

這篇文章不打算講這麼宏大的主題了.只講其中的兩個函數: nnz和nonzeros.

之所以講這兩個函數, 原因:

1 內置函數, 速度很快

2 應用場景很常見(不要以為它們只能用在稀疏矩陣上, 我之前誤以為是這樣的:( )

3 感覺大部分讀者不熟悉這兩個函數(原因還是因為它們放在了稀疏矩陣這個主題下, 實際上可以用來普通的矩陣上)

考慮一個常見的應用場景:

1 矩陣中符合條件的元素的個數有多少個?

比如一個矩陣A中取值為1到10的元素有多少個?

相信對MATLAB稍微熟悉點的讀者秒出程序:

sum(sum(A >= 1 & A <= 10))

假設A = magic(4);

A = magic(4)A = 16 2 3 13 5 11 10 8 9 7 6 12 4 14 15 1

運行上面兩行的程序的結果為:

sum(sum(A >= 1 & A <= 10))ans = 10

結果沒問題, 程序看起來很簡潔, 是標準化的向量化編程方法.

我之前就已經滿足於這樣的方法了. 直到我學到了函數nnz.

nnz(A): A中非零元素的個數

nnz(A >= 1 & A <= 10)ans = 10

nnz符合要求.

相比那個sum版本( sum(sum(A >=1& A <=10)) ), 好處是明顯的.

nnz只調用了一次, 而sum調用了兩次(速度不談, 起碼是打字更多), 而且sum的調用次數與A的維度是有關的. A如果是一維的話, sum調用1次(當然, 調用2次也沒有關係, 但顯得很啰嗦), A如果是三維的話, sum調用3次.

接下來比較一下nnz與sum版本的速度.

A = randn(10000, 1000) >= 0;timeit(@() nnz(A))timeit(@() sum(sum(A)))timeit(@() sum(A(:)))ans = 0.0052ans = 0.0021ans = 0.0021

我換了個例子, 因為將A弄大點, 更方便比較速度.

edit nnz

可以看到nnz是內置函數.

這樣的速度結果就不奇怪了, 可以說nnz與相應的sum版的速度是差不多的.

nonzeros: 提取非零元素

考慮一個常見的應用場景:

從一個矩陣中提取出所有的非零元素.

這個為什麼很常見呢?

因為我們分配一個矩陣經常使用zeros函數, 預設矩陣的大小, 然後用循環對每個元素進行賦值(當然, 這個比較適合於複雜的運算, 簡單的運算最好用向量化的方法).

會有一些位置的元素被pass掉, 被pass掉的元素值自然就是0了(因為一開始預設為zeros)

nonzeros就是要提取出那些非pass掉的元素.

從一個矩陣中提取出所有的非零元素, 相信很多讀者秒出程序:

C = A(A~=0);

但是使用nonzeros更簡潔:

B = nonzeros(A);

可能有些讀者不同意我的說法了, 如果把A替換成一個複雜的運算(最後輸出一個矩陣), 那麼哪個更簡潔, 就顯而易見了.

測試一下性能:

A = randi([0, 5], 10000, 1000);tic;B = nonzeros(A);toc;tic;C = A(A~=0);toc;tic;[~, ~, D] = find(A);toc;assert(isequal(B, C));assert(isequal(C, D));時間已過 0.059481 秒。時間已過 0.077852 秒。時間已過 0.104345 秒。

nonzeros速度最快, 索引法次之, find最慢.

edit nonzeros

可以看到它也是一個內置函數, 這樣的結果就不奇怪了.

總結:

1 nnz和nonzeros經常可以更簡潔的實現功能.

2 nnz和nonzeros的速度還非常快.

推薦閱讀：