Prijavi problem


Obeleži sve katergorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Mali uvod u efikasnost

Колико је C++ бржи од Пајтона

У такмичарским круговима се често може чути да је C++ бољи избор од Пајтона, јер се C++ програми компајлирају у ефикасан извршиви код, па се зато брже извршавају од еквивалентних Пајтон програма (који се изршавају кроз интерпретер). То све јесте тачно, али колико је стварно C++ програм бржи од Пајтон програма?

На следећој слици је време извршавања два C++ и два Пајтон програма, на сваком језику по једно наивно и једно ефикасно решење претходног задатка. Времена су дата и као бројеви у прозору испод слике.

На такмичењу је коришћено 25 тест примера (првих 25 на слици). Првих десет тестова су мали, а следећих 15 су велики. Програм који би радио дуже од 2 секунде, прекидали смо при овом тестирању (нека извршавања на појединим тестовима су претходно трајала и до 200 секунди). Двадесет шести тест смо додали само овде као најнеповољнији случај (тест садржи низ максималне дужине од 50000 елемената, а при томе су збирови префикса низа сви различити, да би речник постао што већи и тиме евентуално спорији).

_images/SaTakmicenja_01_ZadAkcije.png
Мали тестови (званични):
Пајтон наивно:   0.12 0.12 0.12 0.11 0.11 0.11 0.11 0.12 0.12 0.12
C++ наивно:      0.05 0.02 0.03 0.05 0.03 0.03 0.05 0.05 0.03 0.06
Пајтон ефикасно: 0.11 0.12 0.12 0.11 0.11 0.12 0.11 0.12 0.11 0.11
C++ ефикасно:    0.03 0.03 0.03 0.03 0.03 0.04 0.05 0.05 0.05 0.05

Велики тестови (званични):
Пајтон наивно:   2.03 2.03 2.02 2.05 2.04 2.06 2.05 2.03 2.04 2.03 2.04 2.04 2.03 2.03 2.07 (прекидано)
C++ наивно:      0.91 1.05 1.03 1.17 0.95 0.86 0.94 1.11 1.20 1.02 0.99 0.94 0.86 0.87 1.14
Пајтон ефикасно: 0.17 0.17 0.19 0.19 0.17 0.18 0.16 0.17 0.17 0.17 0.16 0.18 0.17 0.17 0.18
C++ ефикасно:    0.06 0.09 0.08 0.08 0.07 0.08 0.06 0.08 0.08 0.08 0.08 0.06 0.08 0.06 0.08

Најнеповољнији случај (додат само овде):
Пајтон наивно:   2.04 (прекидано)
C++ наивно:      1.43
Пајтон ефикасно: 0.23
C++ ефикасно:    0.09

Видимо да се на малим тестовима сва 4 програма извршавају врло брзо, при томе Пајтон програми (црвене линије) око три до четири пута спорије од C++ програма (плаве линије).

Уз разумну претпоставку да је дозвољено време по тесту пажљиво бирано (у овим условима извршавања то би могло да буде пола секунде), оба наивна решења су преспора да би дала резултат на великим тестовима, а оба ефикасна решења су довољно испод границе дозвољеног времена. При томе је за велике тестове решење на Пајтону било око 2 до 2.5 пута спорије од C++ решења.

На основу представљене теорије о ефикасности алгоритама је јасно да је ефикасно решење на Пајтону на довољно великим тестовима брже него неефикасно C++ решење, а ова слика говори у прилог томе. Један број званичних тестова за овај задатак је био такав (довољно велики) да редослед времена на њима буде (од најбржег ка најспоријем):

_images/SaTakmicenja_02_PajtonIliCPP.png

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

Пајтон или C++

Уместо директног одговора на питање Пајтон или C++, рекли бисмо да је то ствар индивидуалног избора. Сваки језик има своје предности, и можда највише профитирају они који током времена науче оба, или још неки језик. Понекад избор језика треба да зависи од задатка. На пример, ако вас интересује колико је \(50!\), а користите само C++, мораћете мало више да се потрудите од писања простог:

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


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