在（非）對角矩陣中尋找非零元素的速度

查看完整矩陣，查找操作在非對角矩陣上更快。相反，獲得稀疏表示在對角矩陣上更快（這似乎是合理的）。稀疏矩陣上的查找操作幾乎相等。

爲了好奇，有人能告訴我這裏發生了什麼？爲什麼在整個矩陣上找到非零元素要比在對角矩陣上找到它們要快？

printf("Diagonal Mat:\n\n") 
A = eye(10000); 

printf("Full mat: ") 
tic 
find(A); 
toc 

printf("Building sparse representation: ") 
tic 
As = sparse(A); 
toc 

printf("Sparse mat: ") 
tic 
find(As); 
toc 

printf("\n\nNon-Diagonally flagged Mat:\n\n") 
A = A | A; # This removes the "Diagonal Matrix" flag from A 

printf("Full mat: ") 
tic 
find(A); 
toc 

printf("Building sparse representation: ") 
tic 
As = sparse(A); 
toc 

printf("Sparse mat: ") 
tic 
find(As); 
toc 

printf("\n\nActually Non-Diagonal Mat:\n\n") 
A(:,:) = 0; 
A(:,1) = 1; 
printf("Full mat: ") 
tic 
find(A); 
toc 

printf("Building sparse representation: ") 
tic 
As = sparse(A); 
toc 

printf("Sparse mat: ") 
tic 
find(As); 
toc

輸出：

Diagonal Mat: 

Full mat: Elapsed time is 0.204636 seconds. 
Building sparse representation: Elapsed time is 5.19753e-05 seconds. 
Sparse mat: Elapsed time is 7.60555e-05 seconds. 


Non-Diagonally flagged Mat: 

Full mat: Elapsed time is 0.0800331 seconds. 
Building sparse representation: Elapsed time is 0.0924602 seconds. 
Sparse mat: Elapsed time is 7.48634e-05 seconds. 


Actually Non-Diagonal Mat: 

Full mat: Elapsed time is 0.0799708 seconds. 
Building sparse representation: Elapsed time is 0.092248 seconds. 
Sparse mat: Elapsed time is 7.70092e-05 seconds.

來源

2017-04-13 nils

首先，下面將是衡量一個更好的方式：

for i = 1:10, find (d); endfor 
t = cputime(); 
for i = 1:100, find (d); endfor 
cputime() -t 


for i = 1:10, find (f); endfor 
t = cputime(); 
for i = 1:100, find (f); endfor 
cputime() -t

這是一個很好的問題。八度對於只存儲對角線值的對角矩陣具有內部專門化。你可以看到它是如何更少的內存使用：

octave> d = eye (10000); 
octave> f = full (eye (10000)); 
octave> typeinfo (d) 
ans = diagonal matrix 
octave> typeinfo (f) 
ans = matrix 
octave> whos d f 
Variables in the current scope: 

    Attr Name  Size      Bytes Class 
    ==== ====  ====      ===== ===== 
     d  10000x10000     80000 double 
     f  10000x10000    800000000 double 

Total is 200000000 elements using 800080000 bytes

專業化是針對地方對角矩陣是常見的情況下，降低內存和性能。這種專業化的問題在於，他們會在整個地方添加特殊情況，特別是當您想要直接訪問Octave常用的數據時。

在find的情況下，它對於布爾數組，整數陣列，置換矩陣和稀疏矩陣具有special cases。沒有對角矩陣的特殊處理，因此使用real type double precision array的情況代替。這意味着無論如何，調用find時對角線矩陣都會內部轉換爲完整陣列。

奇怪的是，在調用find之前在對角矩陣上調用full似乎仍然更有效，所以也許我的推理是錯誤的。我已經打開了一個performance bug report

來源

2017-04-13 13:19:47 carandraug

這已經在錯誤報告中複製，所以我將其設置爲正確的答案。 – nils

它是與如何在您的計算機（或詳細，你的CPU）是堆和棧的處理和緩衝值。當你爲你的數組在堆上分配內存時，它會一個接一個地分配一個「列表」值。因此，當你迭代一個數組的值時，cpu將從該列表上的一個值跳到下一個值（非常快），但是如果你從值i跳到值i + n，其中n不是1 ，這意味着CPU必須在該列表中的其他位置找到下一個值。因此，在編程環境中保存值的方式以及迭代這些值的方式會影響以下過程的速度。

這只是一個簡短而非常簡單的嘗試來解釋這個話題。實際上，隨着更多的因素和不同的cpu和內存技術的發展，它會變得更加複雜。如果你對這類事情感興趣，我會建議從這裏開始：https://en.wikipedia.org/wiki/System_programming（要在主題上有俯視圖）。

來源

2017-04-13 08:02:53 Andre

在（非）對角矩陣中尋找非零元素的速度

回答

相關問題