根据我的理解,Strassen的乘法矩阵的方法应该是最快的......但是Divide&Conquer方法显然是我测试中最快的......我做错了什么?或者这是正确的吗?
说明是:“然后将花费的总时间除以执行算法的次数,以获得解决给定实例所花费的时间”
所以我只是在每个方法中都有一个单独的“counter ++”并将时间除以“录制/计数器++”
到目前为止,这里是我的时代:(按顺序上下/下:经典,分而治之,strassen)(size =矩阵的大小)
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的矩阵的示例:
第1随机生成矩阵: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纳秒
Strassen的常数因素非常高,因此对于大多数输入,分而治之的速度会更快。尝试使用更大的矩阵(数千+元素)运行测试,看看Strassen的超越是否分裂和征服
只是一个想法:不要运行一次,运行100次。
实际上,首先运行100次而不记录时间,然后记录100次。如果你有时间,甚至数千次,越多越好。
System.nanoTime()
有时可能非常不准确,特别是在现代计算机上同时运行数十个进程时。运行越多,不准确性对结果的影响就越小。最初的非定时尝试是“加速”Java VM,确保每个类都被加载,内存分配和垃圾收集以稳定的节奏稳定下来,等等。
另一个可以提高测试准确性的变化是从实际计算代码中删除所有类型的System.out
调用(或实际上是任何输出),因为这只会给两个函数增加一个恒定的开销,从而扭曲结果。
你的“经典”实现有些问题。它不应该那么慢。经典应该更快,直到你得到相当大的矩阵。当然,使用标准矩阵乘法,4x4应该更快,更快。
Strassen的速度较慢,因为它不是缓存友好的,它只是“理论上”最快的。 “缓存 - 忘记”算法,例如你的分而治之一,通常更快。