Účinnost algoritmu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. listopadu 2020; ověření vyžaduje 1 úpravu .

Účinnost algoritmu  je vlastnost algoritmu , která souvisí s výpočetními zdroji používanými algoritmem. Algoritmus musí být analyzován , aby se určily zdroje potřebné pro algoritmus. Efektivitu algoritmu lze považovat za analogickou s produkčním výkonem opakujících se nebo kontinuálních procesů.

Pro dosažení maximální efektivity chceme snížit spotřebu zdrojů. Různé zdroje (jako je čas a paměť) však nelze přímo porovnávat, takže který z těchto dvou algoritmů je považován za efektivnější, často závisí na tom, který faktor je důležitější, jako je požadavek na vysokou rychlost, minimální využití paměti nebo jiné opatření. účinnosti.

Všimněte si, že tento článek NENÍ o optimalizaci algoritmů, o které pojednávají články optimalizace programu , optimalizace kompilátoru , optimalizace smyčky , optimalizátor objektového kódu atd. Termín „optimalizace“ je sám o sobě zavádějící, protože vše, co lze udělat, spadá pod definici „zlepšení“.

Pozadí

Důležitost efektivity s důrazem na dobu provedení zdůraznila Ada Lovelace v roce 1843 na Mechanical Analytical Engine Charlese Babbage :

„Téměř u všech výpočtů je pro úspěšné dokončení procesu možná široká škála konfigurací a výběr pro provádění výpočtů by měly ovlivnit různé konvence. Zásadní je volba takové konfigurace, která povede k minimalizaci času potřebného k provedení výpočtu“ [1] .

Rané elektronické počítače byly velmi omezené jak v rychlosti, tak v paměti. V některých případech bylo zjištěno, že existuje kompromis mezi časem a pamětí , ve kterém úkol musí buď použít velké množství paměti, aby dosáhl vysoké rychlosti, nebo použít pomalejší algoritmus využívající malé množství pracovní paměti. V tomto případě byl použit nejrychlejší algoritmus, pro který byl dostatek volné paměti.

Moderní počítače jsou mnohem rychlejší než ty rané počítače a mají mnohem více paměti (gigabajty místo kilobajtů). Donald Knuth však zdůrazňuje, že účinnost zůstává důležitým faktorem:

"V zavedených inženýrských disciplínách je 12% zlepšení snadno dosažitelné, nikdy to nebylo považováno za pobuřující a věřím, že totéž by mělo platit v programování" [2]

Přehled

Algoritmus je považován za účinný, pokud zdroj, který spotřebovává (nebo náklady na zdroj), je na nebo pod nějakou přijatelnou úrovní. Zhruba řečeno, „přijatelné“ zde znamená „algoritmus poběží po rozumnou dobu na dostupném počítači“. Vzhledem k tomu, že od 50. let došlo k výraznému nárůstu výpočetního výkonu a dostupné paměti počítačů, nebyla stávající „akceptovatelná úroveň“ přijatelná ani před 10 lety.

Výrobci počítačů pravidelně uvolňují nové modely, často výkonnější . Náklady na software mohou být poměrně vysoké, takže v některých případech je snazší a levnější získat lepší výkon zakoupením rychlejšího počítače, který je kompatibilní s vaším stávajícím počítačem.

Existuje mnoho způsobů, jak měřit zdroje používané algoritmem. Dvě nejpoužívanější měření jsou rychlost a použitá paměť. Další měření mohou zahrnovat přenosovou rychlost, dočasné využití disku, dlouhodobé využití disku, spotřebu energie, celkové náklady na vlastnictví , dobu odezvy na externí signály a tak dále. Mnoho z těchto měření závisí na velikosti vstupů algoritmu (tj. na množství, které je třeba zpracovat). Měření mohou také záviset na způsobu, jakým jsou data prezentována (například některé třídicí algoritmy nefungují dobře na datech, která jsou již setříděna, nebo když jsou data řazena v opačném pořadí).

V praxi existují další faktory, které ovlivňují účinnost algoritmu, jako je požadovaná přesnost a/nebo robustnost. Jak je vysvětleno níže, způsob implementace algoritmu může mít také významný vliv na skutečný výkon, ačkoli mnoho aspektů implementace je otázkami optimalizace.

Teoretická analýza

V teoretické analýze algoritmů je běžnou praxí hodnotit složitost algoritmu v jeho asymptotickém chování, to znamená odrážet složitost algoritmu jako funkci velikosti vstupu n , velký zápis "O" . se používá . Tento odhad je obecně poměrně přesný pro velké n , ale může vést k nesprávným závěrům pro malé hodnoty n (například třídění podle bublin, které je považováno za pomalé, může být rychlejší než „rychlé třídění“, pokud je potřeba pouze několik prvků. seřazeno).

Některé příklady velkého zápisu 'O' :

Označení název Příklady
trvalý Určení, zda je číslo sudé nebo liché. Použití vyhledávací tabulky konstantní velikosti. Pomocí vhodné hashovací funkce vyberte prvek.
logaritmický Hledání prvku v seřazeném poli pomocí binárního vyhledávání nebo vyváženého stromu , stejně jako operace na binomické hromadě .
lineární Hledání prvku v netříděném seznamu nebo nevyváženém stromu (nejhorší případ). Sčítání dvou n - bitových čísel pomocí carry through .
kvazilineární , logaritmicky lineární Výpočet rychlé Fourierovy transformace , heapsort , quicksort (nejlepší a průměrný případ), mergesort
náměstí Násobení dvou n -ciferných čísel pomocí jednoduchého algoritmu, bublinové třídění (nejhorší případ), shellové třídění , rychlé třídění (nejhorší případ), výběrové třídění , vkládání třídění
exponenciální Nalezení (přesného) řešení problému obchodního cestujícího pomocí dynamického programování . Určení, zda jsou dva booleovské příkazy ekvivalentní pomocí vyčerpávajícího vyhledávání

Ověřovací testy: Měření výkonu

Pro nové verze softwaru nebo pro srovnání s konkurenčními systémy se někdy používají benchmarky k porovnání relativní výkonnosti algoritmů. Pokud je například vydán nový třídicí algoritmus , lze jej porovnat s předchůdci, aby bylo zajištěno, že algoritmus bude na známá data přinejmenším stejně účinný jako ostatní. Benchmarky mohou uživatelé použít k porovnání produktů od různých výrobců, aby vyhodnotili, který produkt bude nejlépe vyhovovat jejich požadavkům z hlediska funkčnosti a výkonu.

Některé benchmarky poskytují způsob, jak porovnávat různé jazyky kompilátoru a interpretu, jako je Roy Longbottom's PC Benchmark Collection [3] a The Computer Language Benchmarks Game porovnává výkon implementací typických úloh v některých programovacích jazycích.

(Je dostatečně snadné vytvořit „ domácí “ testy výkonu, abyste získali představu o relativním výkonu různých programovacích jazyků pomocí sady vlastních kritérií, jako to udělal Christopher Covell-Shah ve svém „shrnutí výkonu devíti jazyků“) [ 4]

Problémy s implementací

Problémy s implementací mohou také ovlivnit skutečný výkon. To zahrnuje volbu programovacího jazyka a způsobu, jakým je algoritmus skutečně kódován, volbu překladače pro zvolený jazyk nebo použité možnosti kompilátoru a dokonce i použitý operační systém. V některých případech může být jazyk implementovaný jako interpret výrazně pomalejší než jazyk implementovaný jako kompilátor [5] .

Existují další faktory, které mohou ovlivnit využití času nebo paměti, které jsou mimo kontrolu programátora. To zahrnuje zarovnání dat , granularitu garbage collection , paralelismus na úrovni instrukcí a volání podprogramů .

Některé procesory mají schopnost provádět vektorové operace , což umožňuje jediné operaci zpracovat více operandů. Může nebo nemusí být snadné používat takové funkce na úrovni programování nebo kompilace. Algoritmy navržené pro sériové výpočty bude možná nutné zcela přepracovat, aby mohly používat paralelní výpočty .

Další problém může nastat s kompatibilitou procesorů, ve kterých mohou být instrukce implementovány odlišně, takže instrukce na některých modelech mohou být na jiných modelech relativně pomalejší. To může být problém pro optimalizační kompilátor.

Měření využití zdrojů

Měření se obvykle vyjadřují jako funkce vstupní velikosti n .

Dvě nejdůležitější měření jsou:

Pro počítače napájené bateriemi (např. notebooky ) nebo pro velmi dlouhé/velké výpočty (např. superpočítače ) je zajímavý jiný druh měření:

V některých případech jsou zapotřebí jiná, méně běžná měření:

Čas

Teorie

Pro analýzu algoritmů se obvykle používá analýza časové složitosti algoritmu k odhadu doby běhu jako funkce velikosti vstupních dat. Výsledek je obvykle vyjádřen jako "O" velké . To je užitečné pro porovnávání algoritmů, zejména při zpracování velkého množství dat. Je-li množství dat malé, jsou potřebné podrobnější odhady pro porovnání algoritmů (ačkoli tato situace pravděpodobně nezpůsobí problémy). Algoritmy, které zahrnují paralelní výpočty, může být obtížnější analyzovat.

Cvičení

Používají se srovnávací testy doby běhu algoritmu. Mnoho programovacích jazyků obsahuje funkce, které odrážejí dobu využití procesoru. U dlouhotrvajících algoritmů může být zajímavý také uplynulý čas. Výsledky v obecném případě by měly být zprůměrovány ze série testů.

Tento druh testu může být velmi citlivý na konfiguraci hardwaru a na schopnost jiných programů běžet současně v prostředí s více procesory a multitaskingem .

Tento typ testů také výrazně závisí na volbě programovacího jazyka, kompilátoru a jeho možnostech, takže porovnávané algoritmy musí být implementovány za stejných podmínek.

Paměť

Tato část se zabývá použitím hlavní paměti (často RAM) vyžadované algoritmem. Stejně jako u časové analýzy výše, analýza algoritmu obvykle používá analýzu prostorové složitosti algoritmu k odhadu požadované paměti za běhu jako funkce velikosti vstupu. Výsledek je obvykle vyjádřen jako "O" velké .

Existují čtyři aspekty využití paměti:

  • Množství paměti potřebné k uložení kódu algoritmu.
  • Množství paměti potřebné pro vstupní data.
  • Množství paměti požadované pro jakýkoli výstup (některé algoritmy, jako například řazení, často mění uspořádání vstupu a nevyžadují další paměť pro výstup).
  • Množství paměti potřebné pro výpočetní proces během výpočtu (to zahrnuje pojmenované proměnné a jakýkoli zásobníkový prostor potřebný k volání podprogramů, což může být významné při použití rekurze ).

Rané elektronické počítače a domácí počítače měly relativně malou pracovní paměť. Takže v roce 1949 měl EDSAC maximální pracovní paměť 1024 17bitových slov a v roce 1980 byl vyroben Sinclair ZX80 s 1024 bajty pracovní paměti.

Moderní počítače mohou mít relativně velké množství paměti (možná gigabajty), takže komprimace paměti používané algoritmem do daného množství paměti trvá méně, než tomu bylo dříve. Podstatná je však existence tří různých kategorií paměti:

  • Cache (často statická RAM) – běží rychlostí srovnatelnou s CPU
  • Hlavní fyzická paměť (často dynamická RAM) – o něco pomalejší než CPU
  • Virtuální paměť (často na disku) – vytváří iluzi obrovské paměti, ale pracuje tisíckrát pomaleji než RAM.

Algoritmus, jehož požadovaná paměť se vejde do mezipaměti počítače, běží mnohem rychleji než algoritmus, který se vejde do hlavní paměti, která bude zase mnohem rychlejší než algoritmus využívající virtuální prostor. Vše komplikuje skutečnost, že některé systémy mají až tři úrovně mezipaměti. Různé systémy mají různé množství těchto typů paměti, takže vliv paměti na algoritmus se může mezi jednotlivými systémy výrazně lišit.

V počátcích elektronických počítačů, pokud se algoritmus a jeho data nevešly do hlavní paměti, nemohl být použit. V dnešní době používání virtuální paměti poskytuje obrovskou paměť, ale za cenu výkonu. Pokud se algoritmus a jeho data vejdou do mezipaměti, lze dosáhnout velmi vysoké rychlosti, takže minimalizace požadované paměti pomáhá minimalizovat čas. Algoritmus, který se zcela nevejde do mezipaměti, ale zajišťuje lokalitu odkazu , může běžet relativně rychle.

Příklady efektivních algoritmů

Kritika současného stavu programování

Programy se zpomalují rychleji než počítače.

May říká:

V rozšířených systémech může snížení provádění instrukcí na polovinu zdvojnásobit životnost baterie a velká data umožňují lepší algoritmy: Snížení počtu operací z N x N na N x log(N) má silný účinek u velkých N... Pro N=30 miliard, tyto změny jsou podobné 50 letům technologických vylepšení.

  • Programátor Adam N. Roserburg ve svém blogu " The failure of the Digital computer " popsal současný stav programování jako blízko " horizontu softwarových událostí " ve své knize Stopařův průvodce po galaxii ( Stopařův průvodce po galaxii ) [8] ). Odhadl pokles výkonu o 70 dB, neboli „99,99999 % toho, co bylo možné“, ve srovnání s 80. léty – „kdy Arthur C. Clarke porovnával výpočetní výkon počítačů z roku 2001 s počítačem HAL v knize 2001: A Space Odyssey , poukázal na to, že počítače byly překvapivě malé a výkonné, ale programy se staly bohužel zklamáním.

Soutěž o nejlepší algoritmus

Následující soutěže vás zvou k účasti na vývoji nejlepších algoritmů, jejichž kvalitativní kritéria určují porotci:

Viz také

  • Analýza algoritmů
  • Aritmetické kódování  - typ entropického kódování s proměnnou délkou kódu pro efektivní kompresi dat
  • Asociativní pole  je datová struktura, kterou lze zefektivnit pomocí stromů PATRICIA nebo polí
  • Benchmarking  – metoda měření komparativních časů provádění v určitých případech
  • Nejlepší, nejhorší a průměrný případ  – Konvence pro odhadování doby provedení pro tři scénáře
  • Binární vyhledávání  je jednoduchá a efektivní technika pro vyhledávání v seřazeném seznamu.
  • Branch table  - technika pro snížení délky instrukcí, velikosti strojového kódu a často i paměti
  • Optimalizační kompilátor  je kompilátor, který používá různé metody k vytvoření optimálnějšího kódu při zachování funkčnosti.
  • Výpočetní složitost matematických operací
  • Výpočetní složitost  je v informatice pojem, který označuje závislost množství práce na velikosti vstupních dat.
  • Výpočetní výkon počítače  - kvantitativní charakteristika rychlosti provádění operací na počítači
  • Komprese dat  – snižuje objem přenášených dat a zabrané místo na disku
  • Index  - data zvyšující rychlost načítání dat z tabulek
  • Entropické kódování  - kódování sekvence hodnot s možností jednoznačné obnovy za účelem snížení množství dat (délky sekvence) zprůměrováním pravděpodobností výskytu prvků v zakódované sekvenci
  • Odvoz odpadu  - automatické uvolnění paměti po použití
  • Green Information Technologies  – hnutí za zavedení „zelených“ technologií, které spotřebují méně zdrojů
  • Huffmanův kód  - Efektivní algoritmus kódování dat
  • Zlepšení výkonu spravovaného kódu  – Microsoft MSDN Library
  • Referenční lokalita  - aby se zabránilo zpožděním způsobeným ukládáním do mezipaměti kvůli nelokálnímu přístupu do paměti
  • Optimalizace smyčky
  • Správa paměti
  • Optimalizace (informatika)
  • Analýza výkonu  - Techniky pro měření skutečného výkonu algoritmu v reálném čase
  • Real-time computing  - příklad časově kritických aplikací
  • Dynamická analýza  - odhad očekávané doby běhu a rozdělení algoritmu
  • Simultánní multithreading
  • Preemptivní provádění , kdy se výpočty provádějí, i když ještě není známo, zda jsou jejich výsledky potřeba, nebo okamžité vyhodnocení na rozdíl od líného hodnocení
  • Dočasný multithreading
  • Vláknový kód  je jedním ze způsobů, jak implementovat přechodný virtuální stroj při interpretaci programovacích jazyků (spolu s bajtkódem)
  • Tabulka virtuálních metod  – mechanismus pro podporu dynamického párování (nebo metody pozdní vazby)

Poznámky

  1. ↑ Zelená, 2013 .
  2. ↑ Knuth, 1974 .
  3. ↑ Historie benchmarků .
  4. ↑ Shrnutí výkonu devíti jazyků: Srovnávací matematika a I/O souborů | OSnews
  5. ↑ Benchmark s pohyblivou řádovou čárkou .
  6. ↑ Steele, 1977 .
  7. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 14. září 2017. Archivováno z originálu 3. března 2016. 
  8. ↑ http://www.the-adam.com/adam/rantrave/computers.htm
  9. ↑ Fagone, Jason . Teen Mathletes bojují na Algorithm Olympics , Wired  (29. listopadu 2010).

Literatura

Odkazy

 Kvalita softwaru
Charakteristika
Vnitřní
Externí
Normy a doporučení
  • ISO/IEC 9126
  • Nefunkční požadavky
  • Charakteristiky kvality systému
Procesy a organizace