Algorytmika empiryczna - Empirical algorithmics

W informatyce , algorytmika empiryczne (lub algorytmika eksperymentalne ) jest praktyka stosowania metod empirycznych do badania zachowania algorytmów . Praktyka łączy rozwój algorytmów i eksperymentowanie: algorytmy są nie tylko projektowane, ale także wdrażane i testowane w różnych sytuacjach. W tym procesie analizowany jest wstępny projekt algorytmu, tak aby algorytm mógł być rozwijany w sposób etapowy.

Przegląd

Metody z algorytmiki empirycznej uzupełniają teoretyczne metody analizy algorytmów . Dzięki zasadowemu zastosowaniu metod empirycznych, zwłaszcza statystycznych , często można uzyskać wgląd w zachowanie algorytmów, takich jak wysokowydajne algorytmy heurystyczne dla trudnych problemów kombinatorycznych, które są (obecnie) niedostępne dla analizy teoretycznej. Metody empiryczne można również wykorzystać do osiągnięcia znacznej poprawy wydajności algorytmicznej .

Amerykańska informatyk Catherine McGeoch identyfikuje dwie główne gałęzie algorytmiki empirycznej: pierwsza (znana jako analiza empiryczna ) zajmuje się analizą i charakteryzacją zachowania algorytmów , a druga (znana jako projektowanie algorytmów lub inżynieria algorytmów ) koncentruje się na metodach empirycznych do poprawy wydajności algorytmów . Ta pierwsza często opiera się na technikach i narzędziach ze statystyki , podczas gdy druga opiera się na podejściach ze statystyki , uczeniu maszynowym i optymalizacji . Narzędzia do analizy dynamicznej , zazwyczaj profilery wydajności , są powszechnie używane przy stosowaniu metod empirycznych do wyboru i udoskonalania algorytmów różnego typu do użytku w różnych kontekstach.

Badania w zakresie algorytmiki empirycznej są publikowane w kilku czasopismach, w tym w ACM Journal on Experimental Algorithmics (JEA) i Journal of Artificial Intelligence Research (JAIR). Oprócz Catherine McGeoch znanymi badaczami algorytmiki empirycznej są Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson i Roberto Battiti .

Profilowanie wydajności w projektowaniu złożonych algorytmów

W przypadku braku algorytmiki empirycznej analiza złożoności algorytmu może obejmować różne metody teoretyczne mające zastosowanie do różnych sytuacji, w których algorytm może być użyty. Zagadnienia dotyczące pamięci i pamięci podręcznej są często istotnymi czynnikami, które należy wziąć pod uwagę przy teoretycznym wyborze złożonego algorytmu lub podejścia do jego optymalizacji dla danego celu. Profilowanie wydajności to technika dynamicznej analizy programów używana zwykle do znajdowania i analizowania wąskich gardeł w kodzie całej aplikacji lub do analizowania całej aplikacji w celu zidentyfikowania kodu o niskiej wydajności. Profiler może ujawnić kod najbardziej odpowiedni dla problemów z wydajnością aplikacji.

Profiler może pomóc w określeniu, kiedy wybrać jeden algorytm zamiast innego w konkretnej sytuacji. Gdy profilowany jest indywidualny algorytm, jak w przypadku analizy złożoności, kwestie dotyczące pamięci i pamięci podręcznej są często ważniejsze niż liczba instrukcji lub cykle zegara; jednakże ustalenia profilera można rozpatrywać w świetle sposobu, w jaki algorytm uzyskuje dostęp do danych, a nie liczby instrukcji, których używa.

Profilowanie może zapewnić intuicyjny wgląd w zachowanie algorytmu, ujawniając wyniki wydajności w postaci wizualnej reprezentacji. Profilowanie wydajności zostało zastosowane na przykład podczas opracowywania algorytmów dopasowywania symboli wieloznacznych . Wczesne algorytmy pasujących symboli wieloznacznych, takich jak Rich Salz ' wildmat algorytmu, zazwyczaj podniesiony rekursji , technika krytykowane ze względu na wydajność. Krauss dopasowanie symboli wieloznacznych Algorytm został opracowany w oparciu o próbę sformułowania nierekursywnych alternatywę za pomocą testów następnie optymalizacje sugerowanych przez profilowania wydajności, w wyniku nowej strategii algorytmicznych poczętego w świetle profili wraz z innymi względami. Programy profilujące, które zbierają dane na poziomie podstawowych bloków lub polegają na pomocy sprzętowej, zapewniają wyniki, które mogą być wystarczająco dokładne, aby pomóc twórcom oprogramowania w optymalizacji algorytmów dla określonego komputera lub sytuacji. Profilowanie wydajności może pomóc programistom w zrozumieniu charakterystyk złożonych algorytmów stosowanych w złożonych sytuacjach, takich jak algorytmy koewolucyjne stosowane do dowolnych problemów związanych z testami, i może pomóc w ulepszeniu projektu.

Zobacz też

Bibliografia