Algoritm effektivitet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 29 november 2020; verifiering kräver 1 redigering .

Effektiviteten hos en algoritm  är en egenskap hos en algoritm som är relaterad till de beräkningsresurser som används av algoritmen. Algoritmen måste analyseras för att bestämma de resurser som behövs av algoritmen. Algoritmeffektivitet kan ses som analogt med produktionsprestanda för repetitiva eller kontinuerliga processer.

För att uppnå maximal effektivitet vill vi minska resursanvändningen. Olika resurser (som tid och minne) kan dock inte jämföras direkt, så vilken av de två algoritmerna som anses vara effektivare beror ofta på vilken faktor som är viktigast, såsom kravet på hög hastighet, minimal minnesanvändning eller annan åtgärd effektivitet.

Observera att den här artikeln INTE handlar om algoritmoptimering, vilket diskuteras i artiklarna programoptimering , optimering av kompilator , loopoptimering , objektkodsoptimerare och så vidare. Termen "optimering" i sig är missvisande, eftersom allt som kan göras faller under definitionen av "förbättring".

Bakgrund

Vikten av effektivitet med tonvikt på utförandetid betonades av Ada Lovelace 1843 om Charles Babbages Mechanical Analytical Engine :

”I nästan alla beräkningar är ett brett utbud av konfigurationer möjliga för att processen ska kunna slutföras framgångsrikt, och olika konventioner bör påverka valet för att utföra beräkningarna. Det väsentliga är valet av en konfiguration som kommer att leda till minimering av den tid som krävs för att utföra beräkningen” [1] .

Tidiga elektroniska datorer var mycket begränsade i både hastighet och minne. I vissa fall har man insett att det finns en avvägning mellan tidsminne , där en uppgift antingen måste använda en stor mängd minne för att uppnå hög hastighet, eller använda en långsammare algoritm som använder en liten mängd arbetsminne. I det här fallet användes den snabbaste algoritmen, för vilken det fanns tillräckligt med minne.

Moderna datorer är mycket snabbare än de tidiga datorerna och har mycket mer minne (gigabyte istället för kilobyte). Donald Knuth betonar dock att effektiviteten fortfarande är en viktig faktor:

"Inom etablerade ingenjörsdiscipliner är en förbättring på 12% lätt att uppnå, har aldrig ansetts upprörande, och jag tror att detsamma borde vara sant i programmering" [2]

Översikt

En algoritm anses vara effektiv om resursen den förbrukar (eller kostnaden för resursen) är på eller under någon acceptabel nivå. Grovt sett betyder "acceptabelt" här "algoritmen kommer att köras under en rimlig tid på en tillgänglig dator". Eftersom det har skett en betydande ökning av datorkraft och tillgängligt minne för datorer sedan 1950-talet, var den befintliga "acceptabla nivån" inte acceptabel ens för 10 år sedan.

Datortillverkare släpper med jämna mellanrum nya modeller, ofta mer kraftfulla . Kostnaden för programvaran kan vara ganska hög, så i vissa fall är det lättare och billigare att få bättre prestanda genom att köpa en snabbare dator som är kompatibel med din befintliga dator.

Det finns många sätt att mäta resurserna som används av en algoritm. De två mest använda måtten är hastighet och använt minne. Andra mätningar kan inkludera överföringshastighet, tillfällig diskanvändning, långvarig diskanvändning, strömförbrukning, total ägandekostnad , svarstid på externa signaler och så vidare. Många av dessa mätningar beror på storleken på algoritmens indata (det vill säga de kvantiteter som behöver bearbetas). Mätningar kan också bero på hur data presenteras (till exempel fungerar vissa sorteringsalgoritmer inte bra på data som redan är sorterad eller när data sorteras i omvänd ordning).

I praktiken finns det andra faktorer som påverkar effektiviteten hos en algoritm, såsom den erforderliga noggrannheten och/eller robustheten. Som förklaras nedan kan sättet som en algoritm implementeras också ha en betydande effekt på den faktiska prestandan, även om många implementeringsaspekter är optimeringsfrågor.

Teoretisk analys

I den teoretiska analysen av algoritmer är det vanligt att utvärdera komplexiteten hos en algoritm i dess asymptotiska beteende, det vill säga att återspegla komplexiteten hos en algoritm som en funktion av storleken på ingången n , den stora "O" -notationen används . Denna uppskattning är i allmänhet ganska korrekt för stort n , men kan leda till felaktiga slutsatser för små värden på n (till exempel kan bubbelsortering, som anses vara långsam, vara snabbare än "snabbsortering" om bara ett fåtal element behöver sorterad).

Några exempel på stor O- notation :

Beteckning namn Exempel
permanent Avgöra om ett tal är jämnt eller udda. Använda en uppslagstabell av konstant storlek. Använd en lämplig hashfunktion för att välja ett element.
logaritmisk Att hitta ett element i en sorterad array med binär sökning eller balanserat träd , precis som operationer på en binomial hög .
linjär Att hitta ett element i en osorterad lista eller obalanserat träd (värsta fall). Tillägg av två n -bitars nummer med hjälp av carry through .
kvasilinjär , logaritmiskt linjär Fast Fourier-transformationsberäkning , heapsort , quicksort ( bästa och genomsnittliga fall), mergesort
fyrkant Multiplicera två n -siffriga tal med en enkel algoritm, bubbelsortering (sämsta fallet), skalsortering , snabbsortering (värsta fallet), urvalssortering , infogningssortering
exponentiell Att hitta en (exakt) lösning på problemet med resande säljare med hjälp av dynamisk programmering . Avgöra om två booleska uttalanden är likvärdiga med hjälp av uttömmande sökning

Verifieringstester: Mätning av prestanda

För nya versioner av programvara, eller för att ge jämförelser med konkurrerande system, används ibland riktmärken för att jämföra algoritmernas relativa prestanda. Om till exempel en ny sorteringsalgoritm släpps kan den jämföras med föregångare för att säkerställa att algoritmen är minst lika effektiv på känd data som de andra. Benchmarks kan användas av användare för att jämföra produkter från olika tillverkare för att utvärdera vilken produkt som bäst passar deras krav vad gäller funktionalitet och prestanda.

Vissa riktmärken ger ett sätt att jämföra olika kompilator- och tolkspråk, som Roy Longbottoms PC Benchmark Collection [3] och The Computer Language Benchmarks Game jämför prestandan för implementeringar av typiska uppgifter i vissa programmeringsspråk.

(Det är tillräckligt enkelt att skapa " hemgjorda " prestandatester för att få en uppfattning om den relativa prestandan för olika programmeringsspråk med hjälp av en uppsättning anpassade kriterier, som Christopher Covell-Shah gjorde i sin "Nine language Performance roundup") [ 4]

Implementeringsproblem

Implementeringsproblem kan också påverka faktiska prestanda. Detta inkluderar valet av programmeringsspråk och hur algoritmen faktiskt är kodad, valet av översättare för det valda språket eller kompilatoralternativ som används, och till och med vilket operativsystem som används. I vissa fall kan ett språk implementerat som tolk vara betydligt långsammare än ett språk implementerat som kompilator [5] .

Det finns andra faktorer som kan påverka tid eller minnesanvändning som är utom programmerarens kontroll. Detta inkluderar datajustering , granularitet sophämtning , parallellitet på instruktionsnivå och subrutinanrop .

Vissa processorer har förmågan att utföra vektoroperationer , vilket gör att en enda operation kan bearbeta flera operander. Det kan eller kanske inte är lätt att använda sådana funktioner på programmerings- eller kompileringsnivå. Algoritmer designade för seriell beräkning kan behöva göras om helt för att använda parallell beräkning .

Ett annat problem kan uppstå med kompatibiliteten hos processorer, där instruktioner kan implementeras annorlunda, så att instruktioner på vissa modeller kan vara relativt långsammare på andra modeller. Detta kan vara ett problem för en optimerande kompilator.

Mätning av resursanvändning

Måtten uttrycks vanligtvis som en funktion av ingångsstorleken n .

De två viktigaste måtten är:

För batteridrivna datorer (t.ex. bärbara datorer ) eller för mycket långa/stora beräkningar (t.ex. superdatorer ) är en annan typ av mätning av intresse:

I vissa fall behövs andra, mindre vanliga mätningar:

Tid

Teori

För algoritmanalys används vanligtvis algoritmtidskomplexitetsanalys för att uppskatta körtiden som en funktion av storleken på indata. Resultatet uttrycks vanligtvis i termer av "O" stort . Detta är användbart för att jämföra algoritmer, särskilt vid bearbetning av stora mängder data. Mer detaljerade uppskattningar behövs för att jämföra algoritmer när mängden data är liten (även om denna situation sannolikt inte kommer att orsaka problem). Algoritmer som involverar parallell beräkning kan vara svårare att analysera.

Öva

Jämförande tester av algoritmens gångtid används. Många programmeringsspråk innehåller funktioner som återspeglar CPU-användningstid. För långvariga algoritmer kan den förflutna tiden också vara av intresse. Resultaten i det allmänna fallet bör beräknas som ett medelvärde över en serie tester.

Denna typ av test kan vara mycket känslig för hårdvarukonfiguration och möjligheten för andra program att köras samtidigt i en multiprocessor- och multitasking- miljö.

Denna typ av tester beror också väsentligt på valet av programmeringsspråk, kompilator och dess alternativ, så att de jämförda algoritmerna måste implementeras under samma förutsättningar.

Minne

Detta avsnitt behandlar användningen av huvudminnet (ofta RAM) som krävs av algoritmen. Som med den temporala analysen ovan använder algoritmanalysen vanligtvis rymdkomplexitetsanalysen för algoritmen för att uppskatta det erforderliga körtidsminnet som en funktion av indatastorleken. Resultatet uttrycks vanligtvis i termer av "O" stort .

Det finns fyra aspekter av minnesanvändning:

  • Mängden minne som krävs för att lagra algoritmkoden.
  • Mängden minne som krävs för indata.
  • Mängden minne som krävs för alla utdata (vissa algoritmer, såsom sorteringar, arrangerar ofta om ingången och kräver inte ytterligare minne för utdata).
  • Mängden minne som behövs av beräkningsprocessen under beräkning (detta inkluderar namngivna variabler och eventuellt stackutrymme som behövs för att anropa subrutiner, vilket kan vara betydande när du använder rekursion ).

Tidiga elektroniska datorer och hemdatorer hade relativt lite arbetsminne. Så 1949 hade EDSAC ett maximalt arbetsminne på 1024 17-bitars ord, och 1980 producerades Sinclair ZX80 med 1024 byte arbetsminne.

Moderna datorer kan ha en relativt stor mängd minne (kanske gigabyte), så att det krävs mindre för att komprimera minnet som används av en algoritm till en viss mängd minne än vad det brukade göra. Det är dock viktigt att det finns tre olika kategorier av minne:

  • Cache (ofta statiskt RAM) - körs med hastigheter jämförbara med processorn
  • Huvudminne (ofta dynamiskt RAM) - något långsammare än processorn
  • Virtuellt minne (ofta på disk) - ger en illusion av enormt minne, men fungerar tusentals gånger långsammare än RAM.

En algoritm vars erforderliga minne passar in i datorns cache körs mycket snabbare än en algoritm som passar in i huvudminnet, vilket i sin tur kommer att vara mycket snabbare än en algoritm som använder virtuellt utrymme. Det komplicerade är det faktum att vissa system har upp till tre nivåer av cache. Olika system har olika mängder av dessa typer av minne, så effekten av minne på en algoritm kan variera avsevärt från ett system till ett annat.

I början av elektronisk datoranvändning, om en algoritm och dess data inte passade i huvudminnet, kunde den inte användas. Dessa dagar ger användningen av virtuellt minne enormt minne, men på bekostnad av prestanda. Om algoritmen och dess data passar i cachen kan mycket hög hastighet erhållas, så att minimera det nödvändiga minnet hjälper till att minimera tiden. En algoritm som inte passar helt i cachen, men säkerställer länklokalitet , kan köras relativt snabbt.

Exempel på effektiva algoritmer

Kritik av det nuvarande tillståndet för programmering

Program blir långsammare snabbare än datorer blir snabbare.

May säger:

I utbredda system kan halvering av instruktionsexekveringen fördubbla batteritiden, och big data möjliggör bättre algoritmer: Att minska antalet operationer från N x N till N x log(N) har en stark effekt vid stort N... För N=30 miljarder, dessa förändringar liknar 50 år av tekniska förbättringar.

  • Programmeraren Adam N. Roserburg beskrev i sin blogg " The failure of the Digital computer " det nuvarande tillståndet för programmering som att ligga nära "Software event horizon " i sin bok Hitchhiker's Guide to the Galaxy ( The Hitchhiker's Guide to the Galaxy ) [8] ). Han uppskattade ett prestandafall på 70 dB, eller "99,99999% av vad som var möjligt", jämfört med 1980-talet - "när Arthur C. Clarke jämförde 2001 års datorers beräkningskraft med HAL -datorn i boken 2001: A Space Odyssey , påpekade han att överraskande nog var datorer små och kraftfulla, men program blev tyvärr en besvikelse."

Konkurrens om den bästa algoritmen

Följande tävlingar inbjuder dig att delta i utvecklingen av de bästa algoritmerna, vars kvalitetskriterier bestäms av domarna:

Se även

  • Algoritmanalys
  • Aritmetisk kodning  - en typ av entropikodning med variabel kodlängd för effektiv datakomprimering
  • En associativ array  är en datastruktur som kan göras mer effektiv med PATRICIA-träd eller - arrayer
  • Benchmarking  - en metod för att mäta jämförande utförandetider i vissa fall
  • Best, Worst, and Average Case  - Konventioner för att uppskatta körtider för tre scenarier
  • Binär sökning  är en enkel och effektiv teknik för att söka i en sorterad lista.
  • Grentabell  - en teknik för att minska längden på instruktioner, storleken på maskinkoden och ofta minnet
  • En optimerande kompilator  är en kompilator som använder olika metoder för att producera mer optimal kod samtidigt som funktionaliteten bibehålls.
  • Beräkningskomplexitet för matematiska operationer
  • Beräkningskomplexitet  är ett begrepp inom datavetenskap som anger mängden arbetes beroende av storleken på indata.
  • Beräkningskraft för en dator  - en kvantitativ egenskap för hastigheten för att utföra operationer på en dator
  • Datakomprimering  - minska mängden dataöverföring och upptaget diskutrymme
  • Index  - data som ökar hastigheten för datahämtning från tabeller
  • Entropikodning  - kodning av en sekvens av värden med möjlighet till entydig återhämtning för att minska mängden data (sekvenslängd) genom att beräkna sannolikheterna för förekomst av element i den kodade sekvensen i genomsnitt
  • Sophämtning  - automatisk frigöring av minne efter användning
  • Green Information Technologies  - rörelsen för införandet av "grön" teknik som förbrukar mindre resurser
  • Huffman Code  - Effektiv datakodningsalgoritm
  • Förbättra prestanda för hanterad kod  - Microsoft MSDN-bibliotek
  • Referenslokal  - för att undvika förseningar orsakade av cachning på grund av icke-lokal minnesåtkomst
  • Slingoptimering
  • Minneshantering
  • Optimering (datavetenskap)
  • Prestandaanalys  - Tekniker för att mäta den faktiska prestandan för en algoritm i realtid
  • Realtidsberäkning  - ett exempel på tidskritiska applikationer
  • Dynamisk analys  - uppskattning av förväntad körtid och uppdelning av algoritmen
  • Samtidig multithreading
  • Förebyggande exekvering , där beräkningar utförs även om det ännu inte är känt om deras resultat behövs, eller omedelbar utvärdering i motsats till lat utvärdering
  • Temporal multithreading
  • Trådad kod  är ett av sätten att implementera en mellanliggande virtuell maskin vid tolkning av programmeringsspråk (tillsammans med bytekod)
  • Virtuell metodtabell  - mekanism för att stödja dynamisk matchning (eller sen bindningsmetod)

Anteckningar

  1. ↑ Grön, 2013 .
  2. ↑ Knuth, 1974 .
  3. ↑ Benchmarkhistorik .
  4. ↑ Sammanfattning av prestanda för nio språk: Benchmarking Math & File I/O | OSnews
  5. ↑ Flytpunktsriktmärke .
  6. ↑ Steele, 1977 .
  7. ↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 14 september 2017. Arkiverad från originalet 3 mars 2016. 
  8. ↑ http://www.the-adam.com/adam/rantrave/computers.htm
  9. ↑ Fagone, Jason . Teen Mathletes slåss vid Algoritm-OS , Wired  (29 november 2010).

Litteratur

Länkar

 Programvara kvalitet
Egenskaper
Inre
Extern
Standarder och rekommendationer
  • ISO/IEC 9126
  • Icke-funktionella krav
  • Systemkvalitetsegenskaper
Processer och organisationer