Алгоритамска ефикасност

У рачунарској науци, алгоритамска ефикасност је свосјтво алгоритма које је повезано са количином рачунарских ресурса које алгоритам користи. Алгоритам мора бити анализиран да би се одредило његово коришћење ресурса. Алгоритамска ефикасност може бити замишљена и као аналогна са инжињерском продуктивношћу током понављаног или континуалног процеса.

За максималну ефикасност желимо да минимизирамо коришћење ресурса. Међутим, различити ресурси (нпр. време, простор) не могу бити поређени директно, тако да то који је од два алгоритма ефикаснији често зависи од тога која мера за ефикасност је најважније, нпр. потреба за великом брзином, минималним коришћењем меморије или нека друга мера.

Обратите пажњу да овај чланак није о оптимизацији, која је дискутована у програмској оптимизацији, оптимизацији компајлера, оптимизацији петље итд. Термин "оптимизација" је сама по себи збуњујућа, јер све то генерално може да се замисли као "побољшање".

Позадина

Важност ефикасности је у прошлости нагласила Ада Лавлејс 1843. применом механичког аналитичког мотора Чарлса Бебиџа:

"У скоро сваком рачунању могућа је велика разноликост уређења наследства процеса, и различита разматрања морају да утичу на селекцију међу њима за сврхе рачунајућег мотора. Један важни објекат је бирање уређења које тежи да смањи минимално време потребно за завршавање рачунице.

Стари електронски рачунари су врло ограничени и од стране брзине операција и количине доступне меморије. У неким случајевима је увиђено да постоји простор-време размена, при чему задатак може бити решен коришћењем брзог алгоритма који заузима прилично пуно меморије, или коришћењем спорог алгоритма који користи врло мало радне меморије. Инжињерска размена је онда била да се користи најбржи алгоритам који би стао у доступну меморију. Модерни рачунари су много бржи од раних рачунара, и имају много већу количину доступне меморије (гигабајте уместо килобајта). Ипак, Доналд Кнут је нагласио да је ефикасност и даље важна за разматрање:

"У утврђеним инжињерским дисциплинама 12% побољшања, лако добијених, никада није сматрано маргиналним и ја верујем да исти начин гледања треба да буде примењен у софтверском инжињерству"

Преглед

Алгоритам се сматра ефикасним ако његова потрошња ресурса (или рачунска вредност) на или испод неког прихватљивог нивоа. Грубо речено, "прихватљивих" значи: радиће разумно много времена на доступном рачунару. Од 1950-их компјутери су доживели драматично повећање доступне рачунарске моћи и доступне меморије, тако тренутни прихватљиви нивои би били неприхватљиви чак и пре 10 година.

Произвођачи компјутера често доносе нове моделе, често са бољим перформансама. Цене софтвера могу бити врло високе, тако да је у неким случајевима најједноставнији и најјефтинији начин да се добиу боље перформансе да се купи бржи рачунар, уз обезбеђење да је компатибилан са постојећим рачунаром.

Постоји много начина мерења колико алгоритам користи ресурса: два најчешћа мерења су брзина и коришћење меморије; друга мерења би могла да укључују брзину преноса, привремено коришћење диска, дугорочно коришћење диска, потрошња енергије, цена поседовања, време реаговања на спољашње стимулације, итд. Многе од ових мерења зависе од величине уноса у алгоритам (нпр. количина података који треба да се процесуирају); могу такође да зависе од начина на који су подаци распоређени (нпр. неки алгоритми за сортирање се лоше показују на подацима који су већ сортирани, или који су сортирани у обрнутом редоследу).

У пракси, постоје други фактори који утичу на ефикасност алгоритма, као што су захтеви за прецизношћу и/или поузданошћу. Доле објашњен, начин на који је алгоритам имплементиран може имати велики ефекат на ефикасност, кроз много аспеката ово је повезано са проблемима оптимизације.

Теоретске анализе

У теоретској анализи алгоритама, нормална пракса је да се процени њихова комплексност у асимптотском смислу, нпр. коришћење нотације велико О да се репрезентује комплексност алгоритма као функције са улазом величине н. Ово је генерално довољно прецизно када је н велико, али може бити спутавајуће за мале вредности н (нпр. бабл сорт може бити бржи од квиксорта када само неколико ствари треба да се сортира).

Неки примери великог О укључују:

Notation	Name	Examples
$O(1)\,$	константно	Проверавање да ли је број прав или прост; коришћењем табеле константне величине; коришћењем одговарајуће хеш функције за тражење.
$O(\log n)\,$	логаритамско	Тражење у сортираном низу са бинарним претраживањем или балансирано претраживачко дрво као и све операције у биномиалној гомили.
$O(n)\,$	линеарно	Тражење у несортираној листи или неправилном дрвету (најгори случај) или у несортираном низу; Сабирање два н-битна цела броја са рипл керијем.
$O(n\log n)\,$	логлинеарно или квазилинеарно	Извођење брзе Фуријеве трансформације;хипсорт, квиксорт (најбољи и просечни случај), или мрџсорт.
$O(n^{2})\,$	квадратно	Множење два н-тоцифрена броја једноставним алгоритмом; бабл сорт (најгори случај или наивна имплементација), шелсорт, квиксорт (најгори случај), селекшн сорт или инсершн сорт.
$O(c^{n}),\;c>1$	експоненцијално	Тражење егзактног решења проблема путујућег трговца коришћењем динамичког програмирања; одређивање да ли су две логичке изјаве еквивалентне коришћењем брут форс претраживања.

Тестирање: мерење перформанси

За нове верзије или да се омогући поређење компетитивних система, тестирање се понекад користи, који асистирају са мерењем алгоритамских релативних перформанси. Ако се на пример произведе нови алгоритам за сортирање може бити упоређен са својим прецима да би се осигурало да је ефикасан као и раније са познатим подацима- узимајући у обзир сва функционална побољшања. Тестирања могу да користе муштерије када упоређују различите производе алтернативних добављача да би проценили који производ ће најбоље да одговара њиховим потребама у смислу функционалности и перформанси. На пример у главном делу светског власништва продуката за сортирање у независним софтверским компанијама као што је Синксорт се такмиче са продуктима које добављају велики добављачи као што је IBM за брзину.

Нека тестирања обезбеђују прилике за произвођење анализе која упоређује релативну брзину различитих састављених и интерпретираних језика на пример и The Computer Language Benchmarks Game упоређује перформансе имплементација типичних програмерских проблема у неколико програмских јзика.

(Чак и стварање "уради сам" тестирања да би се добила макар нека захвалност релативних перформанси различитих програмских језика, коришћењем различитих критеријума специфицираних од стране корисника, је лако да се произведе "окупљање групе девет перформансних језика" од Кристофера Ковела демонстрира на примеру)

Проблеми имплементације

Проблеми импементације могу да имају ефекат на ефикасност, као што је избор програмског језика, или начина на који је алгоритам кодиран, или избор компајлера за одређени језик, или компилација поменутих опција, или чак који се оперативни систем користи. У неким случајевима језик који се имплементира од стране интерпретатора може бити много спорији од језика имплементираног од стране компајлера.

Постоје други фактори који могу да утичу на временске или просторне проблеме, али који могу бити ван контроле програмера; они укључују усклађивање података, грануларност података, скупљаче ђубрета, паралелизам на нивоу инструкција, позиви подрутина.

Неки процесори имају способност векторског процесуирања, које дозвољава да једна инструкција оперише над више операнада; то може и не мора да буде лако програмерима или компајлерима да користе. Алгоритми дизајнирани за секвенцијално процесуирање можда треба да буду потпуно редизајнирани да би се искористило паралелно процесуирање.

Још један проблем који може да настане са компатибилним процесорима је да они могу да имплементирају инструкцију на различите начине, тако да инструкције које су релативно брзе на неким моделима, на другим моделима могу да буду релативно споре; ово може загорчати живот оптимизирајућем компајлеру.

Мере коришћења ресурса

Мере се обично представљају као функције са величином лаза н.

Две најчешће мере су:

• Време: колико је алгоритму потребно да се заврши.
• Простор: колико радне меморије (типично рам) је потребно алгоритму. Ово има два аспекта: количина меморије потребна за код, и количина меморије потребне за податке над којима код оперише.

За компјутере чија је снага снадбдевена батеријом (нпр. лаптопови), или врло дуге/велике калкулације (нпр. суперкомпјутери), друге мере од интереса су:

• Директна потрошња снаге: снага потребна да би се директно оперисало рачунаром.
• Индиректна потрошња снаге: снага потребна за хлађење, осветљење, итд.

У неким случајевима друге мање честе мере могу да буду такође релевантне:

• Величина преноса: проток може да буде ограничавајући фактор. Компресија података може да се искористи да се смањи количина података за слање. Приказивање слике (нпр. лого Гугла) може да резултује слањем десетина хиљада бајтова (48 хиљада у овом случају) у поређењу са слањем шест бајтова за текст"Google".
• Спољашњи простор: простор потребан на диску или на другојм спољашњем уређају; ово може да се користи за привремено складиштење док се алгоритам извршава, или може бити дугорочна меморија потребна за касније референцирање.
• Време одзива: ово је посебно важно за апликацију у реалном времену када комјутерски систем треба брзо да реагује на спољашње догађаје.
• Укупна цена поседовања: посебно ако је компјутер намењен за један посебан алгоритам.

Време

Теорија

Анализирање алгоритма, типично коришћењем анализе временске комплексности да се добије просек времена извршавања као функција за величину унетих података. Резултат је обично представљен нотацијом велико О. Ово је корисно за упоређивање алгоритама, посебно када се велика количина података процесуира. Детаљније процене су потребне за поређење алгоритама када је количина података мала (иако у овој ситуацији време не може да буде неки проблем у сваком случају). Алгоритми који укључују паралелно процесуирање могу да буду тежи за анализирање.

Пракса

Коришћење тестирања да се измери корисност алгоритма. Многи програмски језици имају доступну функцију која даје потрошњу времена процесора. За алгоритме који дуго трају протекло време може бити значајно. Резултати би генерално требало да буду упросечени кроз неколико тестова.

Овај тип тестирања може бити веома осетљив на хардверску конфигурацију и могућности програмера или проблема да се догађају истовремено на мулти процесуираном и мулти програмерској околини.

Ова врста теста такође зависи много од селекције одређеног програмског језика, компајлера, и компајлерских опција, тако алгоритми који се пореде морају бити имплементирани под истим околностима.

Простор

Ова секција се бави коришћењем главне меморије (често РАМ) док се алгоритми дешавају. Као и временска анализа изнад, анализа алгоритама, типично користећи анализу временске комплексности да се процени меморија потребна за функцију за унесене податке. Резултат је често представљен нотацијом велико О.

Постоји чак четири аспекта коришћења меморије који треба да се размотре:

• Количина меморије потребна да сачува код алгоритма.
• Количина меморије потребна за унете податке.
• Количина меморије потребна за унесене податке (неке алгоритме, као што је сортирање, често само премештају подтаке који у унесени и није им потребан простор за излазне податке).
• Количина меморије потребне за радни простор током калкулације (ово укључујеу именоване променљиве и сваки стк простор потребан рутинама које се зову током калкулације; овај стек простор може бити врло важан за алгоритме који користе рекурзивне технике).

Рани електронски рачунари, и рани домаћи рачунари, имају релативно малу количину радне меморије. Нпр. 1949 EDSAC је имао максималну радну меморију од 1024 17-битних речи, док 1980 Sinclair ZX80 је у почетку имао 1024 8-битне бајтове радне меморије.

Тренутни рачунари имају релативно велику количину меморије (могуће Гигабајте), тако да скупљање алгоритма у што мању меморију је много мањи проблем него што је некада био. Али присуство три различите категорије меморије може бити врло важно:

• Кеш меморија (често статичка RAM) - она оперише брзином сличном процесорској.
• Главна физичка меморија (често динамичка RAM) - она оперише нешто спорије од процесорске.
• Виртуелна меморија (често на диску) - она даје илузију велике меморијеt, и оперише хиљадама пута спорије од RAM.

Алгоритам чија меморија треба да стане у кеш меморију ће бити много бржа од алгоритма који стаје у главну меморију, што ће за узврат бити много брже од алгоритма који је у виртуелној меморији, Да даље закомпликујемо проблем, неки системи имају до три нивоа кеш меморије, са варирајућим ефикасним брзинама. Различити системи ће имати различите количине ових различитих типова меморије, тако да ефекат меморије која је потребна алгоритму варира поприлично од једног система до другог.

У раним данима електронског рачунарства, ако алгоритам и његови подаци не стају у главну меморију онда алгоритам не може да се користи. Данас коришћење виртуелне меморије изгледа да доприноси много меморије, али на рачун перформанси. Ако алгоритам и његови подаци стају у кеш меморију, онда се може постићи велика брзина; у овом случају минимизирање простора би такође допринело минимизирању времена. Алгоритам коју не може у потпуности да стане у кеш меморију али који показује локалност референци може поприлично добро да се покаже.

Примери ефикасних алгоритама

• quicksort први познати алгоритам са брзином реда $O(n\log n)\,$.
• heapsort Још један алгоритам брзог сортирања.
• Бинарна претрага - Претраживање сложене табеле.
• Бојер-Мур алгоритам за претрагу ниски - Тражење стринга уз помоћ другог стринга.

Критика тренутног стања програмирања

• David May FRS a, британски рачунарски научник и тренутно професор информатике на Универзитету Бристол и оснивач и CTO XMOS Semiconductor, верује да је један од проблема то што постоји ослањање на Муров закон да би се решиле неефикасности. Он је унапредио 'алтернативни' to Moore's law (May's law) који каже следеће:

  Софтверска ефикасност се преполовљава сваких осамнаест месеци, компензујући Муров закон

  Надовезује се

  У свеприсутним системима, преполовљавање егзекутованих инструкција може да удвостручи живот батерије и велики сетови података доносе велике прилике за бољи софтвер и алгоритме: Смањујући број операција са N x N на N x log(N) има драматичан ефекат када је N велико... за N = 30 милијарди, ова промена је добра као педесет година унапређивања технологије

• Софтверски аутор Adam N. Rosenburg у свом блогу "The failure of the Digital computer", је описао тренутно стање програмирања као приближавању "Хоризонту софтверских догађаја", (алудирајући на фиктивни "shoe event horizon" описан од стране Даглас Адамс у његовој књизи Hitchhiker's Guide to the Galaxy). Он процењује да има 70 dB фактора за губитак продуктивности или "99.99999 процената, његове способности да допринесе", од 1980-их—"Када је Артур Ч. Кларк упоредио реалност рачунања у 2001 на компјутеру HAL у својој књизи Одисеја у свемиру, је истакао како су предивно мали и моћни рачунари постали и како је разочаравајуће компјутерско програмирање постало".
• Conrad Weisert даје примере, неке од њих су објављене у ACM SIGPLAN (Special Interest Group on Programming Languages) Обавештења, децембар 1995 у: "Atrocious Programming Thrives"
• Марк Андерсен, суоснивач Netscape је цитирану "Mavericks at Work". ISBN 978-0-06-077961-0. рекавши "Пет великих програмера могу потпуно да премаше 1.000 осредњих програмера."

Такмичења за најбоље алгоритме

Следећа такмичења позивају на најбољи алгоритам засновано на неким арбитрарним критеријумима одређеним од стране судија:

• Wired magazine

Види још

• Анализа алгоритама - како одредити ресурсе потребне алгоритмима
• Arithmetic coding—форма variable-length entropy encoding за ефикасну компресију података
• Асоцијативни низ—структура података која може бити ефикаснија коришћењем Patricia trees or Judy arrays
• Бинарна претрага—једноставна и ефикасна техника за претраживање сортираних низова
• Бенчмарк—метод за мерење компаративне егзекуције времена у дефинисаним случајевима
• Best, worst and average case—разматрања за одређивање времена егзекуције у три сценарија
• Branch table—техника за редуковање дужине инструкције, величина machine code, (и често такође меморија)
• Comparison of programming paradigms—парадигма специфичне перформансе разматрања
• Optimizacija kompilatora—компајлерска оптимизација
• Computational complexity of mathematical operations
• Теорија комплексности
• Перформансе рачунара—метрика компјутерског хардвера
• Data compression—смањивање промене протока и меморије диска
• Database index—структура података која побољшава брзину операција враћања података на табели база података
• Entropy encoding—кодирање података ефикасно коришћењем фреквенције појављивања стрингова као критеријум за замену
• Garbage collection—аутоматско ослобађање меморије након коришћења
• Green computing—потез да се имплементирају "зеленије" технологије, конзумирајући мање ресурса
• Хафманови кодови—алгоритам за ефикасно кодирање података
• Локалност референци—за избегавање кешираних кашњења проузрокованим не локалним приступима меморији
• Оптимизација петље
• Управљање меморијом
• Оптимизација програма
• Performance analysis—методе за мерење перформансе алгоритма док ради
• Real-time computing—даљи примери временски критичних апликација
• Анализа алгоритама—процењивање очекиваних времена извршавања и алгоритамска скалабилност
• Супернитна обрада
• Simultaneous multithreading
• Спекулативно извршавање or Eager execution
• Threaded code—слично виртуелној табели метода или табели грана
• Virtual method table—табела грана са динамички постављеним показивачимаза диспечовање
• Improving Managed code Performance—Microsoft MSDN Library

Литература

• Gal-Ezer, Judith; Zur, Ela (2004). „The efficiency of algorithms—misconceptions”. Computers & Education. 42 (3): 215—226. doi:10.1016/j.compedu.2003.07.004. 

Спољашње везе

• Animation of the Boyer-Moore algorithm (Java Applet)
• "How algorithms shape our world". A TED (conference) Talk by Kevin Slavin.