- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
我用 C++ 编写了两个矩阵乘法程序:Regular MM (source) , 和 Strassen 的 MM (source) ,它们都在大小为 2^k x 2^k 的方阵上运行(换句话说,是偶数大小的方阵)。
结果很糟糕。对于 1024 x 1024 矩阵,Regular MM 需要 46.381 sec
, 而 Strassen 的 MM 取 1484.303 sec
(25 minutes
!!!!)。
我试图使代码尽可能简单。在网上找到的其他 Strassen 的 MM 示例与我的代码没有太大区别。 Strassen 的代码的一个问题是显而易见的——我没有切换到常规 MM 的截止点。
我的 Strassen 的 MM 代码还有什么其他问题???
谢谢!
直接链接到来源
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy
编辑1。拳头,很多很好的建议。感谢您抽出宝贵时间分享知识。
我实现了更改(保留了我的所有代码),添加了截止点。MM 的 2048x2048 矩阵,截止 512 已经给出了很好的结果。普通MM:191.49s施特拉森的 MM:112.179s很显着的提高。结果是使用 Visual Studio 2012 在配备英特尔迅驰处理器的史前联想 X61 平板电脑上获得的。我会做更多的检查(以确保我得到正确的结果),并将公布结果。
最佳答案
One issue with Strassen's code is obvious - I don't have cutoff point, that switches to regular MM.
可以公平地说,递归到 1 点是大部分(如果不是全部)问题。试图猜测其他性能瓶颈而不解决这个问题几乎没有实际意义,因为它会带来巨大的性能损失。 (换句话说,您是在将苹果与橙子进行比较。)
正如评论中所讨论的,缓存对齐可能会产生影响,但不会达到这种程度。此外,缓存对齐对常规算法的伤害可能比 Strassen 算法更大,因为后者是缓存无意识的。
void strassen(int **a, int **b, int **c, int tam) {
// trivial case: when the matrix is 1 X 1:
if (tam == 1) {
c[0][0] = a[0][0] * b[0][0];
return;
}
这太小了。虽然 Strassen 算法的复杂度较小,但它的 Big-O 常数要大得多。一方面,您的函数调用开销一直到 1 个元素。
这类似于使用合并或快速排序并一直递归到一个元素。为了提高效率,您需要在尺寸变小时停止递归并回退到经典算法。
在快速/合并排序中,您会退回到开销较低的 O(n^2)
插入或选择排序。在这里你会回到正常的 O(n^3)
矩阵乘法。
您回退经典算法的阈值应该是一个可调阈值,该阈值可能会因硬件和编译器优化代码的能力而异。
对于像 Strassen 乘法,其优势仅为 O(2.8074)
优于经典的 O(n^3)
,如果此阈值发生变化,请不要感到惊讶出来非常高。 (数千个元素?)
在某些应用程序中,可能有许多算法,每个算法的复杂度都在降低,但 Big-O 会增加。结果是多种算法在不同大小下变得最优。
大整数乘法是一个臭名昭著的例子:
*请注意,这些示例阈值是近似值,可能会发生巨大变化 - 通常超过 10 倍。
关于c++ - 为什么我的 Strassen 矩阵乘法很慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13559928/
假设我有一个 NxN 矩阵,其中充满 1 到 10 范围内的随机整数。现在我想打电话PROC(A(1:n/2, 1:n/2)+A(n/2+1:n, n/2+1:n)... 其中 n 是矩阵的大小。换句
作为作业的一部分,我试图找出 Strassen 矩阵乘法和朴素乘法算法的交叉点。但同样,当矩阵变为 256x256 时,我无法继续。有人可以建议我适当的内存管理技术,以便能够处理更大的输入。 C语言代
我们的想法是创建一个计时器,该计时器将返回执行特定功能所需的时间。我坐下来编写了一个矩阵类和一个 Strass 函数,应该将我输入其中的值相乘。 定时器函数工作正常,因为它返回执行 Strass 函数
您好,我正在尝试提高 Strassen 算法的效率,但需要一些帮助。该算法的递归关系如下: A(n) = 7A(n/2)+18(n/2)^2, for n>1, A(1) = 0. 我已经解决了这个问
使用与 Strassen's 相同的方法仅 5 次乘法就足以计算矩阵的平方。如果 A[2][2] = [a, b, c, d],则乘法为 a * a、d * d、b * (a + d)、c * (a
我正在尝试解决 Strassen 算法的奇数矩阵问题。我的实现在某个点截断递归,称之为 Q,然后切换到标准实现。因此,在进行静态填充时,我实际上不需要填充到 2 的下一个幂。我只需要填充到至少大于输入
我一直在阅读关于矩阵乘法的 Strassen 算法。 正如 Cormen 在算法导论中提到的,该算法并不直观。但是,我很想知道是否存在任何严格的算法数学证明以及算法设计中实际采用的内容。 我尝试在 G
我从某处复制了 strassen 的算法,然后执行了它。这是输出 n = 256 classical took 360ms strassen 1 took 33609ms strassen2 took
Strassen 的矩阵乘法算法仅比传统的 O(N^3) 算法略有改进。它具有更高的常数因子并且更难实现。考虑到这些缺点,strassens 算法是否真的有用,它是否在任何用于矩阵乘法的库中实现?此外
我想知道您将如何在 Strassen 算法中进行递归调用,以及它们究竟在哪里需要。 我知道 7 个乘法器比 8 个乘法器更有效,但我对如何递归计算这些乘法器感到困惑。特别是,如果我们遵循分而治之的范式
我正在尝试使用 NTT 实现 Schonhage-Strassen 乘法算法,但遇到了一个问题,即最终生成的向量实际上并不等于它应有的值。 对于两个输入向量 a 和 b,每个向量由 N 个“数字”组成
我很难构思如何实现 Strassen 版本的该算法。 对于背景,我有以下迭代版本的伪代码: def Matrix(a,b): result = [] for i in range(0,
这个问题不太可能帮助任何 future 的访问者;它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关,这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用,visit
就效率而言,Strassen 算法应该停止递归并应用乘法的最佳交叉点是多少? 我知道这与具体的实现和硬件密切相关,但对于一般情况应该有某种指南或某人的一些实验结果。 在网上搜索了一下,问了一些他们认为
我们怎样才能改变 Strassen algorithm以便它适用于任何大小的矩阵(例如 n=5)? 最佳答案 您所要做的就是用 0 的行和列填充矩阵,直到它们成为大小为 2 的幂的方阵。或者换句话说:
我接到了一项任务,要用 C++ 编写 Strassen-Winograd 算法。我已经写了两次,但我的代码的第一个版本不起作用。结果矩阵左下角的结果是正确的。我的第二个版本运行速度比原始算法慢,即使
我用 C++、Python 和 Java 编写了矩阵乘法程序,并测试了它们对两个 2000 x 2000 矩阵相乘的速度(参见 post)。标准 ikj 实现 - 在 中- 拍摄: C++:15 秒(
我用 C++ 编写了两个矩阵乘法程序:Regular MM (source) , 和 Strassen 的 MM (source) ,它们都在大小为 2^k x 2^k 的方阵上运行(换句话说,是偶数
我正在尝试在 Python 中实现 Strassen 矩阵乘法。我已经让它发挥了一些作用。这是我的代码: a = [[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]] b
我通过 Strassen 算法和 Python 3 中的朴素嵌套 for 循环实现得到了不同的矩阵乘法输出。 代码: def new_matrix(r, c): """Create a new
我是一名优秀的程序员,十分优秀!