performance - 矩阵乘法 - 分而治之 vs Strassen，分而治之更快？

Question

据我了解，Strassen 的矩阵相乘方法应该是最快的……但分而治之的方法显然是我测试中最快的……我做错了什么吗？或者这是正确的吗？

说明是:“然后将花费的总时间除以执行算法的次数，以获得解决给定实例所花费的时间”

所以我只是在每个方法中都有一个单独的“counter++”并将时间划分为“recorded/counter++”

到目前为止，这是我的时间:(按自上而下的顺序:经典、分而治之、施特拉森)(大小 = 矩阵的大小)

尺寸 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 纳秒

Answer 1

Strassen 中的常数因子非常高，因此对于大多数输入，分而治之会更快。尝试使用更大的矩阵(数千个以上的元素)运行测试，看看 Strassen 是否超越了分而治之