Эмпирическая алгоритмика
В информатике ) — эмпирическая алгоритмика (или экспериментальная алгоритмика это практика использования эмпирических методов для изучения поведения алгоритмов . Практика сочетает разработку алгоритмов и экспериментирование: алгоритмы не просто разрабатываются, но также реализуются и тестируются в самых разных ситуациях. В этом процессе анализируется первоначальный проект алгоритма, чтобы алгоритм можно было разрабатывать поэтапно. [1]
Обзор
[ редактировать ]Методы эмпирической алгоритмики дополняют теоретические методы анализа алгоритмов . [2] Благодаря принципиальному применению эмпирических методов, особенно статистических , часто можно получить представление о поведении алгоритмов, таких как высокопроизводительные эвристические алгоритмы, для сложных комбинаторных задач , которые (в настоящее время) недоступны для теоретического анализа. [3] Эмпирические методы также могут быть использованы для достижения существенного повышения эффективности алгоритмов . [4]
Американский ученый-компьютерщик Кэтрин МакГеоч выделяет две основные ветви эмпирической алгоритмики: первая (известная как эмпирический анализ ) занимается анализом и характеристикой поведения алгоритмов , а вторая (известная как разработка алгоритмов или разработка алгоритмов ) ориентирована на эмпирические методы. для улучшения производительности алгоритмов . [5] Первый часто опирается на методы и инструменты статистики , а второй основан на подходах статистики , машинного обучения и оптимизации . Инструменты динамического анализа , обычно профилировщики производительности , обычно используются при применении эмпирических методов выбора и уточнения алгоритмов различных типов для использования в различных контекстах. [6] [7] [8]
Исследования в области эмпирической алгоритмики публикуются в нескольких журналах, включая Журнал ACM по экспериментальной алгоритмике (JEA) и Журнал исследований искусственного интеллекта (JAIR). Помимо Кэтрин МакГеоч, среди известных исследователей эмпирической алгоритмики Бернар Море , Джузеппе Ф. Итальяно , Хольгер Х. Хоос , Дэвид С. Джонсон и Роберто Баттити . [9]
Профилирование производительности при разработке сложных алгоритмов
[ редактировать ]В отсутствие эмпирической алгоритмики анализ сложности алгоритма может включать различные теоретические методы, применимые к различным ситуациям, в которых может использоваться алгоритм. [10] Соображения памяти и кэша часто являются важными факторами, которые следует учитывать при теоретическом выборе сложного алгоритма или подхода к его оптимизации для конкретной цели. [11] [12] производительности Профилирование — это метод динамического анализа программ, обычно используемый для поиска и анализа узких мест во всем коде приложения. [13] [14] [15] или для анализа всего приложения для выявления неэффективного кода. [16] Профилировщик может выявить код, наиболее соответствующий проблемам производительности приложения. [17]
Профилировщик может помочь определить, когда в конкретной ситуации следует выбрать один алгоритм вместо другого. [18] При профилировании отдельного алгоритма, как при анализе сложности, соображения памяти и кэша часто более важны, чем количество команд или тактовые циклы; однако выводы профилировщика можно рассматривать с точки зрения того, как алгоритм получает доступ к данным, а не с точки зрения количества используемых им инструкций. [19]
Профилирование может дать интуитивное представление о поведении алгоритма. [20] путем раскрытия результатов производительности в виде визуального представления. [21] Профилирование производительности применялось, например, при разработке алгоритмов сопоставления подстановочных знаков . Ранние алгоритмы сопоставления подстановочных знаков, такие как Рича Зальца алгоритм подстановки , [22] обычно полагались на рекурсию — метод, который критиковали из-за производительности. [23] Алгоритм сопоставления подстановочных знаков Краусса был разработан на основе попытки сформулировать нерекурсивную альтернативу с использованием тестовых примеров. [24] с последующей оптимизацией, предложенной с помощью профилирования производительности, [25] в результате появилась новая алгоритмическая стратегия, разработанная с учетом профилирования и других соображений. [26] Профилировщики, собирающие данные на уровне базовых блоков [27] или которые полагаются на аппаратную поддержку [28] предоставлять результаты, которые могут быть достаточно точными, чтобы помочь разработчикам программного обеспечения оптимизировать алгоритмы для конкретного компьютера или ситуации. [29] Профилирование производительности может помочь разработчику понять характеристики сложных алгоритмов, применяемых в сложных ситуациях, таких как коэволюционные алгоритмы, применяемые к произвольным задачам, основанным на тестировании, и может способствовать улучшению конструкции. [30]
См. также
[ редактировать ]- Алгоритмическая инженерия
- Анализ алгоритмов
- Профилирование (компьютерное программирование)
- Настройка производительности
- Разработка программного обеспечения
Ссылки
[ редактировать ]- ^ Флейшер, Рудольф; и др., ред. (2002). Экспериментальная алгоритмика: от разработки алгоритмов к надежному и эффективному программному обеспечению . Спрингер Интернэшнл Паблишинг АГ.
- ^ Море, Бернар М.Е. (1999). К дисциплине экспериментальной алгоритмики . Серия DIMACS по дискретной математике и теоретической информатике. Том. 59. Серия DIMACS по дискретной математике и теоретической информатике. стр. 197–213. дои : 10.1090/dimacs/059/10 . ISBN 9780821828922 . S2CID 2221596 .
- ^ Хромкович, Юрай (2004). Алгоритмы решения сложных задач . Спрингер Интернэшнл Паблишинг АГ.
- ^ Гусман, Джон Пол; Лимоанко, Тересита (2017). «Эмпирический подход к анализу алгоритмов, приводящий к аппроксимации большой тета-временной сложности» (PDF) . Журнал программного обеспечения . 12 (12).
- ^ МакГеоч, Кэтрин (2012). Руководство по экспериментальной алгоритмике . Издательство Кембриджского университета. ISBN 978-1-107-00173-2 .
- ^ Коппа, Эмилио; Деметреску, Камил; Финокки, Ирен (2014). «Профилирование, чувствительное к вводу» . Транзакции IEEE по разработке программного обеспечения . 40 (12): 1185–1205. CiteSeerX 10.1.1.707.4347 . дои : 10.1109/TSE.2014.2339825 .
- ^ Море, Бернар М.Э.; Бадер, Дэвид А.; Варнау, Тэнди (2002). «Высокопроизводительные алгоритмы для вычислительной филогенетики» (PDF) . Журнал суперкомпьютеров . 22 (1): 99–111. дои : 10.1023/а:1014362705613 . S2CID 614550 .
- ^ Запаранукс, Дмитрий; Хаусвирт, Матиас (2012). Алгоритмическое профилирование . 33-я конференция ACM SIGPLAN по разработке и реализации языков программирования . Цифровая библиотека ACM. стр. 67–76. CiteSeerX 10.1.1.459.4913 .
- ^ «Об экспериментальной алгоритмике: интервью с Кэтрин МакГеоч и Бернаром Море» . Вездесущность . 2011 (август). Цифровая библиотека ACM. 2011.
- ^ Гжегож, Мирек (2018). «Большая двусмысленность» . код исполнителя_.
- ^ Кёлькер, Йонас (2009). «Когда нотация Big-O дает сбой?» . Переполнение стека .
- ^ Лемир, Дэниел (2013). «Обозначение Big-O и реальная производительность» . WordPress.
- ^ «Нахождение узких мест приложения» . Справка dotTrace 2018.1 . ДжетБрэйнс. 2018.
- ^ Шмельцер, Шей (2005). «Обнаружение узких мест в вашем коде с помощью профилировщика событий» . Документация JDeveloper Oracle Technology Network . Корпорация Оракл.
- ^ Шен, Ду; Пошиваник, Денис; Ло, Ци; Гречаник, Марк (2015). «Автоматическое обнаружение узких мест в производительности с помощью профилирования приложений на основе поиска» (PDF) . Материалы Международного симпозиума по тестированию и анализу программного обеспечения 2015 г. Цифровая библиотека ACM. стр. 270–281. дои : 10.1145/2771783.2771816 . ISBN 9781450336208 . S2CID 8625903 .
- ^ «Профилирование производительности и памяти и покрытие кода» . Профильный учебный центр . Программное обеспечение SmartBear. 2018.
- ^ Янссен, Торбен (2017). «11 простых советов по настройке производительности Java» . Советы, подсказки и ресурсы для разработчиков Stackify .
- ^ О'Салливан, Брайан; Стюарт, Дон; Герцен, Джон (2008). «25. Профилирование и оптимизация» . Реальный мир Haskell . О'Рейли Медиа.
- ^ Линден, Дуг (2007). «Профилирование и оптимизация» . Вторая жизнь вики.
- ^ Паттис, Ричард Э. (2007). «Анализ алгоритмов, Расширенное программирование/Практикум, 15-200» . Школа компьютерных наук Университета Карнеги-Меллон.
- ^ Уикхэм, Хэдли (2014). «Оптимизация кода» . Продвинутый Р. Чепмен и Холл/CRC.
- ^ Зальц, Рич (1991). "wildmat.c" . Гитхаб .
- ^ Канаторе, Алессандро (2003). «Алгоритмы сопоставления подстановочных знаков» .
- ^ Краусс, Кирк (2008). «Сопоставление подстановочных знаков: алгоритм» . Журнал доктора Добба .
- ^ Краусс, Кирк (2014). «Сопоставление подстановочных знаков: эмпирический способ приручить алгоритм» . Журнал доктора Добба .
- ^ Краусс, Кирк (2018). «Сопоставление подстановочных знаков: улучшенный алгоритм для больших данных» . Развивайтесь ради производительности.
- ^ Грехан, Рик (2005). «Профилировщики кода: выбор инструмента для анализа производительности» (PDF) . Свободный полупроводник. Если, с другой стороны, вам нужно выполнить код с микроскопической точностью, настраивая отдельные машинные инструкции, тогда активный профилировщик с подсчетом циклов не сможет превзойти.
- ^ Хаф, Ричард; и др. (2006). «Оценка производительности микроархитектуры с точностью до цикла». Материалы семинара по интроспективной архитектуре . Технологический институт Джорджии. CiteSeerX 10.1.1.395.9306 .
- ^ Хампария, Адитья; Бану, Сайра (2013). Анализ программы с помощью динамического инструментирования и инструментов производительности . Международная конференция IEEE, посвященная новым тенденциям в области вычислений, связи и нанотехнологий . Цифровая библиотека IEEE Xplore.
- ^ Ясковский, Войцех; Лисковский, Павел; Шуберт, Марцин Гжегож; Кравец, Кшиштоф (2016). «Профиль производительности: многокритериальный метод оценки производительности для решения задач, основанных на тестировании» (PDF) . Прикладная математика и информатика . 26 . Де Грюйтер: 216.