3

据我了解，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 10541
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 纳秒

4

5 回答 5

3

只是一个想法：不要运行一次，运行 100 次。

实际上，先运行100次而不记录时间，然后运行100次记录它。如果你有时间，甚至数千次，越多越好。

System.nanoTime()有时可能非常不准确，尤其是在同时运行数十个进程的现代计算机上。运行次数越多，不准确性对结果的影响就越小。最初的非定时尝试是“加速”Java VM，确保加载每个类、内存分配和垃圾收集以稳定的节奏进行，等等。

另一个可以提高测试准确性的更改是从实际计算代码中删除各种System.out调用（或实际上是任何输出），因为这只会给两个函数增加恒定的开销，从而扭曲结果。

于 2012-02-12T23:44:43.400 回答
3

Strassen 中的常数因子非常高，因此对于大多数输入，分治会更快。尝试使用更大的矩阵（数千个元素）运行您的测试，看看 Strassen 是否超过了分治法

于 2012-02-12T22:25:40.077 回答
0

您的“经典”实现有问题。它不可能慢得多。经典应该更快，直到你得到相当大的矩阵。当然，使用标准矩阵乘法，4x4 应该快得多。

于 2012-07-04T02:17:51.493 回答
0

Strassen 的速度较慢，因为它对缓存不友好，它只是“理论上”最快的。“cache-oblivious”算法，例如你的分而治之的算法，通常更快。

于 2018-09-13T06:40:21.257 回答
0

Strassen 的算法时间复杂度是但分而治之的算法时间复杂度是（你知道，几乎是）。

当我们使用 O（或 theta）函数比较一些算法时，我们的意思是当输入大小接近无穷大时它们更快（或更慢）。

如您所见，对于较小的 n 值，具有时间复杂度的算法可能比具有时间复杂度的算法慢。这是因为常数因子（仅在输入大小较小时才显示其影响）。

图表

因此，如果您的输入大小很小，请使用您知道的最快的算法。但是，如果您的输入大小非常大，请使用具有最小渐近时间复杂度的算法。

于 2019-05-23T11:46:31.280 回答