Empirické algoritmy - Empirical algorithmics

V informatice je empirická algoritmus (nebo experimentální algoritmus ) praxí používání empirických metod ke studiu chování algoritmů . Tato praxe kombinuje vývoj algoritmů a experimentování: algoritmy nejsou pouze navrženy, ale také implementovány a testovány v různých situacích. V tomto procesu je analyzován počáteční návrh algoritmu, takže algoritmus může být vyvinut postupně.

Přehled

Metody empirické algoritmy doplňují teoretické metody pro analýzu algoritmů . Prostřednictvím principiální aplikace empirických metod, zejména ze statistik , je často možné získat vhled do chování algoritmů, jako jsou vysoce výkonné heuristické algoritmy pro těžké kombinatorické problémy, které jsou (v současné době) nepřístupné teoretické analýze. Empirické metody lze také použít k dosažení podstatného zlepšení algoritmické účinnosti .

Americká počítačová vědkyně Catherine McGeochová identifikuje dvě hlavní větve empirických algoritmů: první (známá jako empirická analýza ) se zabývá analýzou a charakterizací chování algoritmů a druhá (známá jako návrh algoritmu nebo inženýrství algoritmů ) je zaměřena na empirické metody pro zlepšení výkonu algoritmů . První se často spoléhá na techniky a nástroje ze statistik , zatímco druhá je založena na přístupech ze statistiky , strojového učení a optimalizace . Nástroje pro dynamickou analýzu , obvykle výkonnostní profily , se běžně používají při aplikaci empirických metod pro výběr a upřesnění algoritmů různých typů pro použití v různých kontextech.

Výzkum empirických algoritmů je publikován v několika časopisech, včetně ACM Journal on Experimental Algorithmics (JEA) a Journal of Artificial Intelligence Research (JAIR). Mezi známé výzkumníky empirických algoritmů patří kromě Catherine McGeoch také Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson a Roberto Battiti .

Profilování výkonu při návrhu složitých algoritmů

Při absenci empirických algoritmů může analýza složitosti algoritmu zahrnovat různé teoretické metody použitelné v různých situacích, ve kterých lze algoritmus použít. Úvahy o paměti a mezipaměti jsou často významnými faktory, které je třeba vzít v úvahu při teoretické volbě složitého algoritmu nebo přístupu k jeho optimalizaci pro daný účel. Profilování výkonu je technika dynamické analýzy programu, která se obvykle používá k hledání a analýze úzkých míst v kódu celé aplikace nebo k analýze celé aplikace k identifikaci špatně fungujícího kódu. Profilovač může odhalit kód nejrelevantnější pro problémy s výkonem aplikace.

Profilovač může pomoci určit, kdy zvolit konkrétní algoritmus nad jiným v konkrétní situaci. Když je individuální algoritmus profilován, stejně jako u analýzy složitosti, jsou úvahy o paměti a mezipaměti často významnější než počet instrukcí nebo hodinové cykly; Zjištění profilovače však lze považovat ve světle toho, jak algoritmus přistupuje k datům, spíše než podle počtu použitých instrukcí.

Profilování může poskytnout intuitivní pohled na chování algoritmu odhalením zjištění výkonu jako vizuální reprezentace. Profilování výkonu bylo použito například během vývoje algoritmů pro porovnávání zástupných znaků . Rané algoritmy pro porovnávání zástupné znaky, jako například Rich Salz " wildmat algoritmu, typicky se spoléhal na rekurzi , technika kritizována z důvodu výkonu. Odpovídající Krauss zástupné znaky algoritmus byl vyvinut na základě pokusu formulovat nerekurzívní alternativu použití testovacích případů následuje optimalizace navrhovaných prostřednictvím výkonu profilování, což vede v novém algoritmického strategie pojaté s ohledem na profilování spolu s dalšími aspekty. Profilery, které shromažďují data na úrovni základních bloků nebo se spoléhají na hardwarovou pomoc, poskytují výsledky, které mohou být dostatečně přesné, aby pomohly vývojářům softwaru při optimalizaci algoritmů pro konkrétní počítač nebo situaci. Profilování výkonu může vývojářům pomoci porozumět charakteristikám složitých algoritmů používaných ve složitých situacích, jako jsou koevoluční algoritmy aplikované na libovolné problémy založené na testech, a může pomoci vést k vylepšení designu.

Viz také

Reference