Умножение матриц - Разделяй и властвуй против Штрассена, Разделяй и властвуй быстрее?

Question

Насколько я понимаю, метод Штрассена для умножения матриц должен быть самым быстрым ... но метод "Разделяй и властвуй" явно самый быстрый в моем тестировании ... Я что-то не так делаю? Или это правильно?

Инструкции были следующими: «Общее время, затраченное на выполнение, делится на количество раз, которое алгоритм выполняет для получения времени, необходимого для решения данного случая»

Так что у меня просто есть отдельный «counter ++» в каждом методе и делю время «записано / 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:

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 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 наносекунды

Матрица умножения Штрассена: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
Прошедшее время: 5303 наносекунды

Answer 1

Просто идея: не запускайте его один раз, запустите 100 раз.

На самом деле, запустите его сначала 100 раз без записи времени, затем 100 раз, записав его. Или даже тысячи раз, если у вас есть время, чем больше, тем лучше.

System.nanoTime() иногда может быть очень неточным, особенно на современном компьютере, когда одновременно работают десятки процессов. Чем больше прогонов, тем меньше неточности влияют на результаты. Первоначальные несвоевременные попытки состоят в том, чтобы «наращивать» Java VM, обеспечивая загрузку каждого класса, распределение памяти и сборку мусора в устойчивом ритме и т. Д.

Еще одно изменение, которое может повысить точность вашего тестирования, состоит в удалении всех видов вызовов System.out (или даже любых выходных данных) из фактического кода вычисления, поскольку это просто добавляет постоянные издержки для обеих функций, искажая результат.

Answer 2

Постоянный коэффициент в Штрассене очень высок, поэтому для большинства входов разделяй и властвуй будет быстрее.Попробуйте запустить свои тесты с гораздо большими матрицами (тысячи + элементов), чтобы увидеть, разделяют ли завоевания Штрассена и побеждают

Answer 3

Сложность времени алгоритма Штрассена равна , но сложность времени алгоритма "разделяй и властвуй" равна (вы знаете, почти ).

Когда мы сравниваем некоторые алгоритмы, использующие функцию O (или тета), мы имеем в виду, что они быстрее (или медленнее), когда размер ввода приближается к бесконечности.

Как видите, для малых значений n алгоритм с сложностью времени может быть медленнее, чем алгоритм с сложностью времени. Это из-за постоянного фактора (который показывает свои эффекты только при небольшом размере ввода).

Итак, если ваш размер ввода невелик, используйте самый быстрый из известных вам алгоритмов. Но если ваш входной размер очень велик, используйте алгоритм с минимальной асимптотической сложностью по времени.

Answer 4

Более медленный Strassen, потому что он не дружествен к кешу, он только «теоретически» самый быстрый. «не обращающий внимания на кеш» алгоритм, такой как «разделяй и властвуй», обычно быстрее.

Answer 5

Что-то не так с вашей "классической" реализацией. Там нет никакого способа, которым это должно быть намного медленнее. Классика должна быть быстрее, пока вы не получите довольно большие матрицы. Конечно, 4x4 должно быть намного, намного быстрее при стандартном умножении матриц.