6.7 KiB
| title | description | sections | tags | canonical_url | url_translated | title_translated | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Код с комментариями | Заметки на тему программирования с примерами кода и комментариями. Решения задач и описания решений. |
|
|
/ | /en/ | Code with comments |
{%- assign articles = "" | split: "" %} {%- assign articles = articles | push: "Алгоритм Винограда — Штрассена" %} {%- capture article_brief %} Рассмотрим модификацию алгоритма Штрассена для умножения квадратных матриц с меньшим количеством сложений между блоками, чем в обычном алгоритме — 15 вместо 18 и таким же количеством умножений как в обычном алгоритме — 7. Будем использовать потоки Java Stream.
Рекурсивное дробление матриц на блоки при перемножении имеет смысл до определенного предела, а дальше теряет смысл, так как алгоритм Штрассена не использует кеш среды выполнения. Поэтому для малых блоков будем использовать параллельный вариант вложенных циклов, а для больших блоков параллельно будем выполнять рекурсивное дробление.
Границу между двумя алгоритмами определяем экспериментально — подстраиваем под кеш среды выполнения. Выгода алгоритма Штрассена становится заметнее на больших матрицах — отличие от алгоритма на вложенных циклах становится больше и зависит от среды выполнения. Сравним время работы двух алгоритмов. {%- endcapture %} {%- assign articles = articles | push: article_brief %} {%- assign articles = articles | push: "Умножение матриц в параллельных потоках" %} {%- capture article_brief %} Рассмотрим алгоритм перемножения прямоугольных матриц с использованием потоков Java Stream. Возьмём оптимизированный вариант алгоритма на трёх вложенных циклах и заменим внешний цикл на поток. Сравним время работы двух алгоритмов.
Строки результирующей матрицы обрабатываем в параллельном режиме, а каждую строку заполняем слоями.
За счёт параллельного использования кеша среды выполнения на многоядерных машинах время вычислений
можно сократить более чем в два раза. Для проверки возьмём две прямоугольные матрицы: {L×M} и {M×N}.
{%- endcapture %}
{%- assign articles = articles | push: article_brief %}
{%- assign articles = articles | push: "Поворот матрицы на 180 градусов" %}
{%- capture article_brief %}
Рассмотрим алгоритм разворота матрицы на 180 градусов. В отличие от алгоритма транспонирования,
здесь в результирующей матрице строки и колонки не меняются местами, но отображаются зеркально.
Напишем метод на Java для поворота матрицы {m×n} на 180 градусов. Для примера возьмём
прямоугольную матрицу {4×3}.
{%- endcapture %}
{%- assign articles = articles | push: article_brief %}
{%- assign articles = articles | push: "Поворот матрицы на 90 градусов" %}
{%- capture article_brief %}
Рассмотрим алгоритм поворота матрицы на 90 градусов по часовой стрелке и против часовой стрелки.
Этот алгоритм похож на транспонирование матрицы с тем отличием, что здесь для каждой точки
одна из координат отображается зеркально.
Напишем метод на Java для поворота матрицы {m×n} на 90 градусов. Дополнительный параметр задаёт
направление поворота: по часовой стрелке или против часовой стрелки. Для примера возьмём
прямоугольную матрицу {4×3}.
{%- endcapture %}
{%- assign articles = articles | push: article_brief %}
{%- assign articles = articles | push: "Оптимизация умножения матриц" %}
{%- capture article_brief %}
Рассмотрим алгоритм перемножения матриц с использованием трёх вложенных циклов. Сложность такого
алгоритма по определению должна составлять O(n³), но есть особенности, связанные со средой
выполнения — скорость работы алгоритма зависит от последовательности, в которой выполняются циклы.
Сравним различные варианты перестановок вложенных циклов и время выполнения алгоритмов.
Возьмём две матрицы: {L×M} и {M×N} → три цикла → шесть перестановок:
LMN, LNM, MLN, MNL, NLM, NML.
Быстрее других отрабатывают те алгоритмы, которые пишут данные в результирующую матрицу построчно слоями:
LMN и MLN, — разница в процентах к другим алгоритмам значительная и зависит от среды выполнения.
{%- endcapture %}
{%- assign articles = articles | push: article_brief %}
{%- include main_page.html articles = articles -%}