Перформансе извршавања алгоритма или кад и шта оптимизовати

+def get_missing_numbers_in_starters_list(sorted_registrations_list, start_number_counter, list_length):
+    missing_numbers_list = list()
+    # iterate through registrations and memorize all missing starter numbers
+    for index in range(list_length):
+        # here we know we have a gap in the starting list
+        if sorted_registrations_list[index].number > start_number_counter:
+            # iterate through all the missing starter numbers in the gap and add them to the list
+            for number in range(start_number_counter, sorted_registrations_list[index].number):
+                missing_numbers_list.append(number)
+            # we set the starting number counter to the next value after current registration's number
+            start_number_counter = sorted_registrations_list[index].number + 1
+            # skip the increase counter instructions with this
+            continue
+
+        start_number_counter += 1
+
+    return missing_numbers_list

Ако причамо о перформансама онда вреди споменути две ствари:

• алгоритамску комплексност (О-нотација је конвенција)
• цену извршвања различитих ствари

Зависно од тога каква је природа решења и над каквом структуром података се програм извршава, оба аспекта могу да буду веома битна. У стварности је ретко потребно направити савршено решење. Шта више, савршено решење је обично прескупо за направити а реално ти ни не треба. Дакле, готово увек треба димензионирати систем и планирати скалабилност према вероватноћи да ли ће ти нешто требати или не.

У нашем случају, ми можемо да пођемо од тога да је тренутно највећи догађај који је икада био на порталу имао мање од 2000 пријава. Максимум пријава који се десио у Србији је био на Београдском маратону и ако се не варам било је реда величине 10к пријављених такмичара. У свету број пријава иде и до 100к, али то је за нас све научна фантастика. Дакле, ми можемо да рачунамо на то да наши алгоритми треба да раде до догађаја реда величине 10к - максимум.

Друга ствар је, колико брзо алгоритам треба да се извршава. То највише зависи од тога ко ти је корисник и колико често се извршава, односно на каквом хардверу. У нашем случају, ово је функционалност која би била понуђена само у организаторској контролној табли и то вероватно прилично ексклузивно за Хронометар и можда још премијум кориснике. То значи да алгоритам не мора да може да се изврши за мање од 1 секунде, што би био захтев да је страница отворена за јавност. Овако је све што траје до 30ак секунди прихватљиво. Сад кад имамо контекст, можемо и да формализујемо захтев према перформансама:

• до 30 секунди за око 10к пријава

Тек сад можемо да се осврнемо на две тачке које сам горе споменуо.

Алгоритамска комплексност је:

• константна уколико је мање више независна од количине података → О(1) - овде обично нема никакве петље у извршавању алгоритма
• линеарна уколико линеарно расте у односу на количину података → О(n) - обично има једна петља у којој се само једном пролази кроз податке
• квадратна уколико време извршавања квадратно расте у односу на количину података → O(n^2) - ово обично значи да је једна петља угњеждена у другу
• … ово сад може да се даље распреда и о овоме постоји довољно литературе. Једино што још вреди споменути је и O(log(n)) што је комплексност бинарне претраге и то је боље од линеарне комплексности.

 У нашем случају доле ми тренутно имамо приблично линеарну комплексност O(n) зато што за сваку пријаву sorted_registrations_list[index] се извршава само још једна петља која попуњава рупе у стартним бројевима, што значи да уколико имамо стартне бројеве од 1 од 1000000 максималан број итерација ће бити 1000000 без обзира колико су стартни бројеви фрагментовани.

Цена извршавања ће овде бити одлучујућа. Мени је много помогло следеће да стекнем неки ментални модел: https://gist.github.com/jboner/2841832 ово је већ све застарело, али је и даље релевантно по питању реда величине цене извршавања какве команде. Оно што је за вас релевантно је да можете са сигурношћу да рачунате да је (скоро) све што се извршава у меморији много брже од нечега што приступа диску - било да је то SSD или HDD, а да је то такође брже него приступ нечему преко мреже (ово је данас дискутабилно, али хајде да оставимо овако зарад даље дискусије). Оно што је овде прилично очигледно је, да је све већ у меморији. Дакле, пријаве су већ прочитане из базе и сав посао који интерпретер треба да уради је да на процесору “истамбура неке бројеве” (ово баш улива поверење како звучи ) и то је то. То значи да је заиста свеједно да ли ћемо смањити укупан број итерација или не, док год у петљи приступамо само RAM меморији.

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

С друге стране, ако би ово доле решио са yield number како сам ја доле предложио, имали би мање кода, листа се не би градила цела у меморији, већ би се све извршавало у лету и креирали би се нови бројеви само онолико пута колико итерација онај који позива тражи. Дакле, основна разлика између овог решења и мог предлога је у томе, што би се у мом предлогу логика извршавала lazy. Никако није неопходно, али је корисно за знати како то функционише. Посебно је важно добро разумети концепт, јер такође може да прави велике проблеме уколико се не користи како треба.