密集和稀疏向量的总和

Question

我需要在 Matlab 中总结一个密集向量和一个稀疏向量，以及这样做的简单方法，即：

w = rand(1e7,1);
d = sprand(1e7,1,.001);
tic
for k = 1 : 100
    w = w + d;
end
toc

大约需要 3.5 秒，比我期望 Matlab 在后台实现它的方式慢大约 20 倍：

for k = 1 : 100
    ind = find(d);
    w(ind) = w(ind) + d(ind);
end

（当然这个更快版本的时间取决于稀疏度）。

那么，为什么 Matlab 不这样做 'the fast way'？到目前为止，我使用 Matlab 的经验表明它非常擅长利用稀疏性。

更重要的是，是否还有其他 'sparse' 我应该怀疑效率不高的操作？

Answer 1

我不确定答案，但我会告诉你我对正在发生的事情的猜测。我不懂 Fortran，但从 C++ 的角度来看，您所展示的内容是有道理的，我们只需要解构该语句即可。

a = b + c 的伪代码翻译，其中 a,b 是完整的，c 是稀疏的，看起来像 a.operator= ( b.operator+ (c) )。

很可能，Matlab 中的全矩阵容器应该有专门的算术运算符来处理稀疏输入，即类似 full full::operator+ ( const sparse& ) 的东西。这里主要要注意的是混合full/sparse算术运算的结果必须是满的。所以我们将需要创建一个新的完整容器来存储结果，即使几乎没有更新的值。 [ 注意： 返回的完整容器是临时的，因此分配 a.operator= ( ... ) 可以避免完整的额外副本，例如 full& full::operator= ( full&& )。 ]

不幸的是，没有办法返回一个新的完整容器，因为 Matlab 中没有算术复合运算（即 operator +=）。这就是为什么 Matlab 无法利用这样一个事实，即在您的示例中 a 与 b 相同（尝试用 x = w + d 代替循环计时，没有运行时差异），这就是开销来自海事组织。 [ 注意： 即使没有显式赋值，例如 b+c;，也会赋值通用答案变量 ans。 ]

有趣的是，full full::operator+ ( const sparse& ) 和 full sparse::operator+ ( const full& ) 之间似乎存在显着差异，即 a = b + c 和 a = c + b 之间；我不能多说为什么会这样，但后者似乎更快。

无论如何，我的简短回答是 "because Matlab doesn't have arithmetic compound operators"，这很不幸。不过，如果您知道自己将要执行很多这些操作，那么实施 ad hoc 优化版本（如您建议的版本）应该不会太难。希望这对您有所帮助！

密集和稀疏向量的总和

Summation of dense and sparse vectors

matlab

sparse-matrix