（非）対角行列で非ゼロ要素を見つけるスピード

Question

この例ではどうなっていますか？

完全行列を見ると、非対角行列上での検索操作が高速になります。 逆に、疎な表現を得るのが対角行列上で高速です（これは妥当と思われます）。 スパース行列の検索操作はほぼ同じです。

ここでは何が起こっているのか誰かに教えてもらえますか？対角行列でそれらを見つけるよりも、完全な行列上の非ゼロ要素を見つける方が早いのはなぜですか？

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. 

Answer 1

まず、次はそれを測定するためのよりよい方法だろう：

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の場合、boolean配列、整数配列、置換行列、および疎行列に対してはspecial casesです。対角行列の特別な処理はありませんので、代わりにreal type double precision arrayの場合が使用されます。これは、とにかくfindを呼び出すと、対角行列が内部的に完全な配列に変換されることを意味します。

奇妙なことに、findを呼び出す前に対角行列にfullを呼び出すと、依然として効率が良いように見えるので、私の推論は間違いです。私は開封しましたperformance bug report

Answer 2

それはあなたのコンピュータ（または詳細に、あなたのCPU）は、スタックとヒープの処理およびバッファリングの値であるかとは何かを持っています。あなたの配列のヒープ上にメモリを割り当てると、順番に値の "リスト"を割り当てます。したがって、値を配列として反復すると、CPUはそのリストのある値から次の値へジャンプしますが、値iから値i + nにジャンプすると（nは1ではありません）つまり、CPUはそのリストのどこかでこの次の値を見つけなければなりません。したがって、プログラミング環境で値を保存する方法と、それらの値を反復する方法は、次のプロセスの速度に影響します。

これは、このトピックを説明するための簡単で簡単な試みでした。実際には、より多くの要因と異なるCPUとメモリ技術が可能になるにつれて、より複雑になります。このようなことに興味がある場合は、ここから始めてください：https://en.wikipedia.org/wiki/System_programming（トピックをトップダウンで表示することをお勧めします）。すべての