在（非）对角矩阵中寻找非零元素的速度

查看完整矩阵，查找操作在非对角矩阵上更快。相反，获得稀疏表示在对角矩阵上更快（这似乎是合理的）。稀疏矩阵上的查找操作几乎相等。

为了好奇，有人能告诉我这里发生了什么？为什么在整个矩阵上找到非零元素要比在对角矩阵上找到它们要快？

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

在（非）对角矩阵中寻找非零元素的速度

回答

相关问题