我用 C++、Python 和 Java 编写了矩阵乘法程序,并测试了它们对两个 2000 x 2000 矩阵相乘的速度(参见 post)。标准 ikj 实现 - 在 中- 拍摄:
现在我已经实现了 Strassen algorithm for matrix multiplication - 位于 - 在 Python 和 C++ 中,就像在维基百科上一样。这些是我的时间:
为什么 Strassen 矩阵乘法比标准矩阵乘法慢很多?
想法:
- 一些缓存效果
- 实现:
- 错误(生成的 2000 x 2000 矩阵是正确的)
- null 乘法(对于 2000 x 2000 -> 2048 x 2048 应该没那么重要)
这尤其令人惊讶,因为它似乎与其他人的经历相矛盾:
- Why is my Strassen Matrix multiplier so fast?
- Matrix multiplication: Strassen vs. Standard - Strassen 对他来说也较慢,但至少在同一数量级。
编辑:在我的情况下,Strassen 矩阵乘法较慢的原因是:
- 我让它完全递归(参见 tam)
- 我有两个函数
strassen
和strassenRecursive
。如果需要,第一个将矩阵的大小调整为 2 的幂,并调用第二个。但是strassenRecursive
并没有递归调用自己,而是strassen
。
最佳答案
基本问题是您使用 strassen 实现递归到叶大小为 1。 Strassen 的算法具有更好的 Big O 复杂度,但常数确实在现实中很重要,这意味着实际上对于较小的问题规模,您最好使用标准的 n^3 矩阵乘法。
所以要大大改进你的程序而不是这样做:
if (tam == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}
在此处使用 if (tam == LEAF_SIZE)//迭代解决方案
。 LEAF_SIZE
应该是一个常量,您必须为给定的架构通过实验确定。根据架构的不同,它可能会更大或更小 - 有些架构中 strassen 的常数因子非常大,以至于对于合理的矩阵大小,它基本上总是比简单的 n^3 实现更差。这一切都取决于。
关于c++ - 为什么 Strassen 矩阵乘法比标准矩阵乘法慢得多?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11495723/