矩阵乘法-分治与Strassen，分治更快？
据我所知，Strassen的矩阵乘法应该是最快的.但在我的测试中，分而治之的方法显然是最快的。我做错了什么吗？或者这是正确的吗？
这些指令是：“所花费的总时间除以执行算法的次数，以获得求解给定实例所需的时间。”
所以我在每种方法中都有一个单独的"counter++“，并将时间划分为"recorded / counter++”
到目前为止，这是我的时间：(按从上到下的顺序:经典，分治，strassen) (大小=矩阵的大小)
尺寸2
耗时:8660纳秒
耗时:3849纳秒
耗时:5377纳秒
大小4
耗时:24864纳秒
耗时:3080纳秒
耗时:5229纳秒
大小8
耗时:125435纳秒
耗时:2920纳秒
耗时:5196纳秒
大小为16
耗时:867149纳秒
耗时:1559纳秒
耗时:2853纳秒
尺寸32
耗时:5191721纳秒
耗时:972纳秒
耗时:1722纳秒
大小64
耗时:8155785纳秒
耗时:874纳秒
耗时:1696纳秒
输出示例下面是我对一个大小为4的矩阵的输出示例：
第一个随机生成的矩阵: 10 57 33 70
6 12 38 70
20 41 65 98
83 0 31 73
第二个随机生成的矩阵: 11 70 54 79
2 51 38 71
27 53 37 86
48 87 20 41
经典乘法矩阵: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
耗时:21232纳秒
分治乘法矩阵: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
耗时:3042纳秒
Strassen乘法矩阵: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
耗时:5303纳秒
回答 5
Stack Overflow用户
发布于 2012-02-13 06:25:40
Strassen中的常量因子非常高，因此对于大多数输入，分而治之会更快。试着用更大的矩阵(thousands+元素)运行测试，看看Strassen是否超过了divide&conquer
Stack Overflow用户
发布于 2012-02-13 07:44:43
只是一个想法:不要运行一次，要运行100次。
实际上，首先运行100次而不记录时间，然后运行100次记录时间。如果你有时间，甚至上千次，越多越好。
System.nanoTime()有时可能非常不准确，特别是在一台同时运行数十个进程的现代计算机上。运行次数越多，不准确对结果的影响就越小。最初的非计时尝试是“加速”Java VM，确保每个类都被加载，内存分配和垃圾收集以稳定的节奏完成，等等。
另一个可以提高测试准确性的更改是从实际计算代码中删除所有类型的System.out调用(或者实际上是任何输出)，因为这只会给两个函数增加恒定的开销，从而扭曲结果。
Stack Overflow用户
发布于 2012-07-04 10:17:51
你的“经典”实现出了问题。它不可能慢那么多。Classic应该更快，直到你得到非常大的矩阵。当然，使用标准矩阵乘法，4x4应该要快得多。
https://stackoverflow.com/questions/9253286
复制相似问题
腾讯云开发者
