3

私が理解していることから、行列を乗算するための Strassen の方法は最速であるはずです...しかし、Divide & Conquer 方法は私のテストでは明らかに最速です...私は何か間違ったことをしていますか? それともこれは正しいですか？

指示は次のとおりです。

したがって、すべてのメソッドに個別の「カウンター++」があり、時間を「記録/カウンター++」で分割します

これまでのところ、私の時間は次のとおりです: (上/下の順に: クラシック、分割統治、ストラッセン) (サイズ = マトリックスのサイズ)

サイズ 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
2 番目のランダム生成行列: 11 70 54 79
2 51 38 71
27 53 37 86
48 87 20 41
従来の乗算行列: 4475 53144
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

Strassen の定数係数は非常に高いため、ほとんどの入力では分割と征服が高速になります。はるかに大きな行列 (数千以上の要素) でテストを実行して、Strassen の分割統治が追い越されるかどうかを確認してください

于 2012-02-12T22:25:40.077 に答える
3

アイデア: 1 回実行するのではなく、100 回実行してください。

実際には、最初は時間を記録せずに 100 回実行し、次に 100 回記録します。または、時間があれば何千回でも、多ければ多いほど良いです。

System.nanoTime()数十のプロセスが同時に実行されている最新のコンピューターでは特に、非常に不正確な場合があります。実行数が多いほど、不正確さが結果に与える影響は少なくなります。時間制限のない最初の試みは、Java VM を「立ち上げる」ことであり、すべてのクラスがロードされていることを確認し、メモリの割り当てとガベージ コレクションが安定したリズムで安定するようにすることなどです。

テストの精度を向上させることができるもう 1 つの変更はSystem.out、実際の計算コードからあらゆる種類の呼び出し (または実際にはすべての出力) を削除することです。これは、両方の関数に一定のオーバーヘッドが追加され、結果が歪むだけだからです。

于 2012-02-12T23:44:43.400 に答える
0

「クラシック」実装に何か問題があります。それほど遅くなるはずはありません。かなり大きな行列に到達するまでは、Classic の方が高速です。確かに、標準の行列乗算では、4x4 の方がはるかに高速です。

于 2012-07-04T02:17:51.493 に答える
0

Strassen が遅いのは、キャッシュに適していないためです。"理論的に" 最速であるだけです。分割統治法などの「キャッシュ無視」アルゴリズムは、通常は高速です。

于 2018-09-13T06:40:21.257 に答える