Algoritmin tehokkuus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29.11.2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Algoritmin tehokkuus on algoritmin  ominaisuus , joka liittyy algoritmin käyttämiin laskentaresursseihin . Algoritmi on analysoitava , jotta voidaan määrittää algoritmin tarvitsemat resurssit. Algoritmin tehokkuutta voidaan pitää analogisena toistuvien tai jatkuvien prosessien tuotannon suorituskyvyn kanssa.

Maksimaalisen tehokkuuden saavuttamiseksi haluamme vähentää resurssien käyttöä. Erilaisia ​​resursseja (kuten aikaa ja muistia) ei kuitenkaan voida suoraan verrata, joten kumpi kahdesta algoritmista katsotaan tehokkaammaksi, riippuu usein siitä, kumpi tekijä on tärkeämpi, kuten vaatimus suuresta nopeudesta, minimaalisesta muistinkäytöstä tai muusta. tehokkuudesta.

Huomaa, että tämä artikkeli EI käsittele algoritmin optimointia, jota käsitellään artikkeleissa ohjelman optimointi , optimointikääntäjä , silmukan optimointi , objektikoodin optimoija ja niin edelleen. Termi "optimointi" itsessään on harhaanjohtava, koska kaikki, mitä voidaan tehdä, kuuluu "parantamisen" määritelmään.

Tausta

Ada Lovelace korosti vuonna 1843 Charles Babbagen mekaanisessa analyyttisessä koneessa tehokkuuden tärkeyttä painottaen suoritusaikaa :

”Lähes kaikissa laskelmissa on mahdollista tehdä monenlaisia ​​konfiguraatioita prosessin onnistuneeseen loppuunsaattamiseen, ja erilaisten käytäntöjen pitäisi vaikuttaa valintaan laskujen suorittamiseksi. Olennaista on valita konfiguraatio, joka johtaa laskennan suorittamiseen tarvittavan ajan minimoimiseen” [1] .

Varhaiset elektroniset tietokoneet olivat hyvin rajallisia sekä nopeuden että muistin suhteen. Joissakin tapauksissa on havaittu, että on olemassa aika-muisti kompromissi , jossa tehtävän on joko käytettävä suurta määrää muistia suuren nopeuden saavuttamiseksi tai käytettävä hitaampaa algoritmia käyttämällä pientä määrää työmuistia. Tässä tapauksessa käytettiin nopeinta algoritmia, jota varten muistia oli riittävästi.

Nykyaikaiset tietokoneet ovat paljon nopeampia kuin aikaisemmat tietokoneet ja niissä on paljon enemmän muistia (gigatavuja kilotavujen sijaan). Donald Knuth kuitenkin korostaa, että tehokkuus on edelleen tärkeä tekijä:

"Vakiintuneilla tekniikan aloilla 12 prosentin parannus on helposti saavutettavissa, sitä ei ole koskaan pidetty törkeänä, ja uskon, että saman pitäisi olla ohjelmoinnissa" [2]

Yleiskatsaus

Algoritmia pidetään tehokkaana, jos sen kuluttama resurssi (tai resurssin hinta) on jollain hyväksyttävällä tasolla tai sen alapuolella. Karkeasti sanottuna "hyväksyttävä" tarkoittaa tässä "algoritmi toimii kohtuullisen ajan käytettävissä olevassa tietokoneessa". Koska tietokoneiden laskentateho ja käytettävissä oleva muisti ovat lisääntyneet merkittävästi 1950-luvulta lähtien, olemassa oleva "hyväksyttävä taso" ei ollut hyväksyttävä vielä 10 vuotta sitten.

Tietokonevalmistajat julkaisevat säännöllisesti uusia malleja, usein tehokkaampia . Ohjelmiston hinta voi olla melko korkea, joten joissain tapauksissa on helpompaa ja halvempaa saada parempi suorituskyky ostamalla nopeampi tietokone, joka on yhteensopiva nykyisen tietokoneesi kanssa.

On monia tapoja mitata algoritmin käyttämiä resursseja. Kaksi eniten käytettyä mittausta ovat nopeus ja käytetty muisti. Muita mittauksia voivat olla siirtonopeus, tilapäinen levyn käyttö, pitkäaikainen levyn käyttö, virrankulutus, kokonaisomistuskustannukset , vasteaika ulkoisiin signaaleihin ja niin edelleen. Monet näistä mittauksista riippuvat algoritmin syötteiden koosta (eli prosessoitavista määristä). Mittaukset voivat myös riippua tietojen esittämistavasta (esimerkiksi jotkin lajittelualgoritmit eivät toimi hyvin jo lajiteltujen tietojen kanssa tai kun tiedot lajitellaan käänteisessä järjestyksessä).

Käytännössä on muitakin algoritmin tehokkuuteen vaikuttavia tekijöitä, kuten vaadittu tarkkuus ja/tai kestävyys. Kuten alla selitetään, tapa, jolla algoritmi toteutetaan, voi myös vaikuttaa merkittävästi todelliseen suorituskykyyn, vaikka monet toteutusnäkökohdat ovatkin optimointiongelmia.

Teoreettinen analyysi

Algoritmien teoreettisessa analyysissä on yleinen käytäntö arvioida algoritmin monimutkaisuus sen asymptoottisessa käyttäytymisessä, toisin sanoen heijastaa algoritmin monimutkaisuus syötteen koon funktiona , " O " iso merkintä . käytetään . Tämä arvio on yleensä melko tarkka suurelle n :lle , mutta se voi johtaa vääriin johtopäätöksiin pienillä n: n arvoilla (esimerkiksi kuplalajittelu, jota pidetään hitaana, voi olla nopeampi kuin "pikalajittelu", jos vain muutama elementti on tarpeen lajiteltu).

Muutamia esimerkkejä isosta O-kirjaimesta :

Nimitys Nimi Esimerkkejä
pysyvä Sen määrittäminen, onko luku parillinen vai pariton. Käyttämällä vakiokokoista hakutaulukkoa . Käyttämällä sopivaa hash-funktiota elementin valitsemiseen.
logaritminen Elementin etsiminen lajitetusta taulukosta binäärihaun tai tasapainotetun puun avulla, aivan kuten binomikeon operaatiot .
lineaarinen Elementin etsiminen lajittelemattomasta luettelosta tai epätasapainoisesta puusta (pahimmassa tapauksessa). Kahden n - bittisen luvun lisääminen käyttämällä läpivientiä .
kvasilineaarinen , logaritmisesti lineaarinen Nopea Fourier-muunnoslaskenta , kekolajittelu , pikalajittelu ( paras ja keskimääräinen tapaus), yhdistäminen
neliö- Kahden n -numeroisen luvun kertominen yksinkertaisella algoritmilla, kuplalajittelu (huonoin tapaus), kuorilajittelu , pikalajittelu (huonoin tapaus), valintalajittelu , lisäyslajittelu
eksponentiaalinen (Täsmällisen) ratkaisun löytäminen matkustavan myyjän ongelmaan dynaamisen ohjelmoinnin avulla . Sen määrittäminen, ovatko kaksi Boolen lauseketta vastaavia tyhjentävällä haulla

Varmistustestit: Suorituskyvyn mittaaminen

Ohjelmistojen uusissa versioissa tai vertailun tarjoamiseksi kilpaileviin järjestelmiin käytetään joskus vertailuarvoja algoritmien suhteellisen suorituskyvyn vertaamiseen. Jos esimerkiksi uusi lajittelualgoritmi julkaistaan , sitä voidaan verrata edeltäjiin varmistaakseen, että algoritmi on vähintään yhtä tehokas tunnetulle tiedolle kuin muut. Vertailuarvojen avulla käyttäjät voivat vertailla eri valmistajien tuotteita arvioidakseen, mikä tuote vastaa heidän vaatimuksiinsa toiminnaltaan ja suorituskyvyltään parhaiten.

Jotkut benchmarkit tarjoavat tavan vertailla eri kääntäjä- ja tulkkikieliä, kuten Roy Longbottomin PC Benchmark Collection [3] , ja The Computer Language Benchmarks Game vertaa joidenkin ohjelmointikielien tyypillisten tehtävien toteutusten suorituskykyä.

(On tarpeeksi helppoa luoda " kotitekoisia " suorituskykytestejä saadakseen käsityksen eri ohjelmointikielten suhteellisesta suorituskyvystä käyttämällä mukautettuja kriteerejä, kuten Christopher Covell-Shah teki "Nine language Performance roundup" -ohjelmassaan) [ 4]

Käyttöönottoongelmat

Toteutusongelmat voivat myös vaikuttaa todelliseen suorituskykyyn. Tämä sisältää ohjelmointikielen valinnan ja algoritmin todellisen koodauksen, valitun kielen kääntäjän tai käytetyn kääntäjän valinnan ja jopa käytetyn käyttöjärjestelmän. Joissakin tapauksissa tulkkina toteutettu kieli voi olla huomattavasti hitaampi kuin kääntäjänä toteutettu kieli [5] .

On myös muita tekijöitä, jotka voivat vaikuttaa aikaan tai muistin käyttöön ja jotka eivät ole ohjelmoijan hallinnassa. Tämä sisältää tietojen kohdistuksen , tarkkuuden roskien keräämisen , käskytason rinnakkaisuuden ja aliohjelman kutsut .

Joillakin prosessoreilla on kyky suorittaa vektorioperaatioita , mikä mahdollistaa useiden operandien käsittelyn yhdellä operaatiolla. Tällaisten ominaisuuksien käyttäminen ohjelmointi- tai käännöstasolla saattaa olla helppoa tai ei. Sarjalaskentaan suunnitellut algoritmit on ehkä suunniteltava kokonaan uudelleen, jotta ne voivat käyttää rinnakkaislaskentaa .

Toinen ongelma voi syntyä prosessorien yhteensopivuudesta, jossa käskyt voidaan toteuttaa eri tavalla, jolloin joidenkin mallien ohjeet voivat olla suhteellisen hitaampia muissa malleissa. Tämä voi olla ongelma optimoivalle kääntäjälle.

Resurssien käytön mittaaminen

Mittaukset ilmaistaan ​​yleensä syötteen koon n funktiona .

Kaksi tärkeintä mittausta ovat:

Akkukäyttöisissä tietokoneissa (esim. kannettavissa tietokoneissa ) tai erittäin pitkissä/suurissa laskelmissa (esim. supertietokoneissa ) toinen mittaus on kiinnostava:

Joissakin tapauksissa tarvitaan muita, vähemmän yleisiä mittauksia:

Aika

Teoria

Algoritmianalyysissä algoritmin aikamonimutkaisuusanalyysiä käytetään yleensä arvioimaan käyntiaika syötetietojen koon funktiona. Tulos ilmaistaan ​​yleensä "O":na iso . Tämä on hyödyllistä algoritmien vertailussa, etenkin kun käsitellään suuria tietomääriä. Tarkempia arvioita tarvitaan algoritmien vertailuun, kun dataa on vähän (vaikka tämä tilanne ei todennäköisesti aiheuta ongelmia). Algoritmeja, joihin liittyy rinnakkaislaskentaa, voi olla vaikeampi analysoida.

Harjoittele

Algoritmin ajoajan vertailutestejä käytetään. Monet ohjelmointikielet sisältävät ominaisuuksia, jotka heijastavat suorittimen käyttöaikaa. Pitkäkestoisissa algoritmeissa kulunut aika voi myös olla kiinnostava. Yleisessä tapauksessa tuloksista tulisi laskea keskiarvo testisarjasta.

Tällainen testi voi olla erittäin herkkä laitteiston kokoonpanolle ja muiden ohjelmien kyvylle toimia samanaikaisesti moniprosessori- ja moniajoympäristössä .

Tämän tyyppiset testit riippuvat myös merkittävästi ohjelmointikielen valinnasta, kääntäjästä ja sen vaihtoehdoista, joten vertailtavat algoritmit on toteutettava samoissa olosuhteissa.

Muisti

Tämä osio käsittelee algoritmin vaatiman päämuistin (usein RAM) käyttöä. Kuten yllä olevassa ajallisessa analyysissä, algoritmianalyysi käyttää tyypillisesti algoritmin tilan monimutkaisuusanalyysiä arvioidakseen tarvittavan ajonaikaisen muistin tulokoon funktiona. Tulos ilmaistaan ​​yleensä "O":na iso .

Muistin käytössä on neljä näkökohtaa:

  • Algoritmikoodin tallentamiseen tarvittava muisti.
  • Syötetietojen vaatima muistin määrä.
  • Tulosten vaatima muistimäärä (jotkut algoritmit, kuten lajittelut, järjestävät usein tulon uudelleen eivätkä vaadi lisämuistia ulostuloon).
  • Laskentaprosessin tarvitseman muistin määrä laskennan aikana (tämä sisältää nimetyt muuttujat ja pinotilan, joka tarvitaan aliohjelmien kutsumiseen, mikä voi olla merkittävää rekursiota käytettäessä ).

Varhaisissa elektronisissa tietokoneissa ja kotitietokoneissa oli suhteellisen vähän työmuistia. Joten vuonna 1949 EDSAC :n maksimityömuisti oli 1024 17-bittistä sanaa, ja vuonna 1980 Sinclair ZX80 tuotettiin 1024 tavulla työmuistilla.

Nykyaikaisissa tietokoneissa voi olla suhteellisen paljon muistia (ehkä gigatavuja), joten algoritmin käyttämän muistin pakkaaminen tietyksi määräksi muistia kestää vähemmän kuin ennen. Kolmen erilaisen muistiluokan olemassaolo on kuitenkin välttämätöntä:

  • Välimuisti (usein staattinen RAM) - toimii prosessorin nopeuksilla
  • Päämuisti (usein dynaaminen RAM) - hieman hitaampi kuin prosessori
  • Virtuaalimuisti (usein levyllä) - antaa illuusion valtavasta muistista, mutta toimii tuhansia kertoja hitaammin kuin RAM.

Algoritmi, jonka tarvittava muisti mahtuu tietokoneen välimuistiin, toimii paljon nopeammin kuin päämuistiin mahtuva algoritmi, joka puolestaan ​​on paljon nopeampi kuin virtuaalitilaa käyttävä algoritmi. Asiaa mutkistaa se, että joissakin järjestelmissä on jopa kolme välimuistitasoa. Eri järjestelmissä on erilaisia ​​määriä tämäntyyppistä muistia, joten muistin vaikutus algoritmiin voi vaihdella merkittävästi järjestelmistä toiseen.

Sähköisen laskennan alkuaikoina algoritmi ja sen tiedot eivät mahtuneet keskusmuistiin, sitä ei voitu käyttää. Nykyään virtuaalimuistin käyttö tarjoaa valtavasti muistia, mutta suorituskyvyn kustannuksella. Jos algoritmi ja sen tiedot mahtuvat välimuistiin, voidaan saada erittäin suuri nopeus, joten tarvittavan muistin minimoiminen auttaa minimoimaan aikaa. Algoritmi, joka ei mahdu kokonaan välimuistiin, mutta varmistaa linkin paikallisuuden , voi toimia suhteellisen nopeasti.

Esimerkkejä tehokkaista algoritmeista

Kritiikki ohjelmoinnin nykytilasta

Ohjelmat hidastuvat nopeammin kuin tietokoneet.

May sanoo:

Laajalti levinneissä järjestelmissä käskyjen suorittamisen puolittaminen voi kaksinkertaistaa akun käyttöiän, ja iso data mahdollistaa parempien algoritmien: Toimintojen määrän vähentämisellä N x N arvoon N x log(N) on voimakas vaikutus suurella N... N=30 miljardia, nämä muutokset ovat samanlaisia ​​kuin 50 vuoden teknologiset parannukset.

  • Ohjelmoija Adam N. Roserburg kuvaili blogissaan " The vika of the Digital computer " ohjelmoinnin nykytilan olevan lähellä "Ohjelmistotapahtumahorisonttia " Adams kirjassaan Hitchhiker's Guide to the Galaxy ( The Hitchhiker's Guide to the Galaxy ) [8] ). Hän arvioi suorituskyvyn laskun 70 dB eli "99,99999 % siitä, mikä oli mahdollista" verrattuna 1980-luvulle - "kun Arthur C. Clarke vertasi vuoden 2001 tietokoneiden laskentatehoa HAL -tietokoneeseen kirjassa 2001: A Space Odyssey , hän huomautti, että tietokoneet olivat yllättävän pieniä ja tehokkaita, mutta ohjelmista tuli valitettava pettymys."

Kilpailu parhaasta algoritmista

Seuraavat kilpailut kutsuvat sinut osallistumaan parhaiden algoritmien kehittämiseen, joiden laatukriteerit määräävät tuomarit:

Katso myös

  • Algoritmianalyysi
  • Aritmeettinen koodaus  – entropiakoodaus , jossa on muuttuva koodipituus tehokkaaseen tiedon pakkaamiseen
  • Assosiatiivinen taulukko  on tietorakenne, jota voidaan tehostaa käyttämällä PATRICIA-puita tai - taulukoita
  • Benchmarking  - menetelmä vertailevien suoritusaikojen mittaamiseen tietyissä tapauksissa
  • Paras, huonoin ja keskimääräinen tapaus  – Käytännöt suoritusaikojen arvioimiseksi kolmelle skenaariolle
  • Binäärihaku  on yksinkertainen ja tehokas tekniikka lajitellun luettelon etsimiseen.
  • Haarataulukko  - tekniikka käskyjen pituuden, konekoodin koon ja usein muistin
  • Optimoiva kääntäjä  on kääntäjä, joka käyttää erilaisia ​​menetelmiä optimaalisemman koodin tuottamiseen säilyttäen samalla toiminnallisuuden.
  • Matemaattisten operaatioiden laskennallinen monimutkaisuus
  • Laskennallinen monimutkaisuus  on tietojenkäsittelytieteen käsite, joka kuvaa työn määrän riippuvuutta syötetyn tiedon koosta.
  • Tietokoneen laskentateho  - kvantitatiivinen ominaisuus toimintojen suorittamisen nopeudelle tietokoneella
  • Tietojen pakkaus  - vähentää tiedonsiirron määrää ja varattua levytilaa
  • Hakemisto  - tiedot, jotka nopeuttavat tietojen hakua taulukoista
  • Entropiakoodaus  - arvosarjan koodaus, jossa on mahdollisuus yksiselitteiseen palautukseen tiedon määrän (sekvenssin pituuden) vähentämiseksi laskemalla koodatun sekvenssin elementtien esiintymistodennäköisyyksien keskiarvo
  • Roskien kerääminen  - muistin automaattinen vapauttaminen käytön jälkeen
  • Green Information Technologies  - liike "vihreiden" tekniikoiden käyttöönottamiseksi, jotka kuluttavat vähemmän resursseja
  • Huffman Code  - Tehokas tietojen koodausalgoritmi
  • Hallitun koodin suorituskyvyn parantaminen  - Microsoft MSDN -kirjasto
  • Viitepaikka  - välttääksesi välimuistin aiheuttamat viiveet, jotka johtuvat ei-paikallisesta muistin käytöstä
  • Silmukan optimointi
  • Muistin hallinta
  • Optimointi (tietokonetiede)
  • Suorituskykyanalyysi  – tekniikat algoritmin todellisen suorituskyvyn mittaamiseksi reaaliajassa
  • Reaaliaikainen laskenta  - esimerkki aikakriittisistä sovelluksista
  • Dynaaminen analyysi  - estimoi odotettavissa olevasta käyntiajasta ja algoritmin jakamisesta
  • Samanaikainen monisäikeistys
  • Ennaltaehkäisevä suoritus , jossa laskelmat suoritetaan, vaikka ei vielä tiedetä, tarvitaanko niiden tuloksia, tai välitön arviointi toisin kuin laiska arviointi
  • Temporaalinen monisäikeistys
  • Säikeistetty koodi  on yksi tavoista toteuttaa virtuaalikone välivaiheessa ohjelmointikieliä tulkittaessa (yhdessä tavukoodin kanssa)
  • Virtuaalinen menetelmätaulukko  - mekanismi, joka tukee dynaamista vastaavuutta (tai myöhäistä sidontamenetelmää)

Muistiinpanot

  1. ↑ Vihreä, 2013 .
  2. ↑ Knuth, 1974 .
  3. ↑ Vertailuhistoria .
  4. ↑ Yhdeksän kielen suorituskyvyn yhteenveto: Math & File I/O | OSnews
  5. ↑ Liukulukujen vertailuarvo .
  6. ↑ Steele, 1977 .
  7. ↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 14. syyskuuta 2017. Arkistoitu alkuperäisestä 3. maaliskuuta 2016. 
  8. ↑ http://www.the-adam.com/adam/rantrave/computers.htm
  9. ↑ Fagone, Jason . Teen Mathletes Do Battle at Algorithm Olympics , Wired  (29. marraskuuta 2010).

Kirjallisuus

Linkit

 Ohjelmiston laatu
Ominaisuudet
Sisäinen
Ulkoinen
Standardit ja suositukset
  • ISO/IEC 9126
  • Ei-toiminnalliset vaatimukset
  • Järjestelmän laatuominaisuudet
Prosessit ja organisaatiot