Эмпирическая алгоритмика - Empirical algorithmics

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

Обзор

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

Американский ученый-компьютерщик Кэтрин МакГеоч выделяет две основные ветви эмпирической алгоритмики: первая (известная как эмпирический анализ ) занимается анализом и характеристикой поведения алгоритмов , а вторая (известная как разработка алгоритмов или разработка алгоритмов ) сосредоточена на эмпирических методах. для повышения производительности алгоритмов . Первый часто полагается на методы и инструменты из статистики , а второй основан на подходах из статистики , машинного обучения и оптимизации . Инструменты динамического анализа , обычно профилировщики производительности , обычно используются при применении эмпирических методов для выбора и уточнения алгоритмов различных типов для использования в различных контекстах.

Исследования в области эмпирической алгоритмики публикуются в нескольких журналах, включая ACM Journal on Experimental Algorithmics (JEA) и Journal of Artificial Intelligence Research (JAIR). Помимо Кэтрин МакГеоч, к известным исследователям эмпирической алгоритмики относятся Бернард Морет , Джузеппе Ф. Итальяно , Хольгер Хус , Дэвид С. Джонсон и Роберто Баттити .

Профилирование производительности при разработке сложных алгоритмов

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

Профилировщик может помочь определить, когда выбрать один алгоритм вместо другого в конкретной ситуации. При профилировании отдельного алгоритма, как при анализе сложности, соображения памяти и кэша часто более важны, чем количество команд или тактовые циклы; однако результаты профилировщика можно рассматривать в свете того, как алгоритм получает доступ к данным, а не количества инструкций, которые он использует.

Профилирование может обеспечить интуитивное понимание поведения алгоритма, отображая результаты производительности в виде визуального представления. Профилирование производительности применялось, например, при разработке алгоритмов сопоставления подстановочных знаков . Ранние алгоритмы для сопоставления групповых символов, таких как Rich Salz ' wildmat алгоритм, как правило , опираются на рекурсии , метод критики на основании производительности. Соответствия Krauss подстановочные знаки алгоритм был разработан на основе попытки сформулировать нерекурсивную альтернативу с использованием тестовых случаев с последующей оптимизацией предложенных с помощью профилирования производительности, в результате чего в новой алгоритмической стратегии задуманной в свет профилирования наряду с другими соображениями. Профилировщики, которые собирают данные на уровне базовых блоков или полагаются на аппаратную помощь, предоставляют результаты, которые могут быть достаточно точными, чтобы помочь разработчикам программного обеспечения оптимизировать алгоритмы для конкретного компьютера или ситуации. Профилирование производительности может помочь разработчикам понять характеристики сложных алгоритмов, применяемых в сложных ситуациях, таких как коэволюционные алгоритмы, применяемые к произвольным тестовым задачам, и может помочь улучшить дизайн.

Смотрите также

Рекомендации