Computer Programming 2024/25 fall

Võistlusprogrammeerimine

Selles peatükis jagatakse soovitusi, kuidas alustada võistlusprogrammeerimisega ning tutvustatakse Pythoni standardteegis leiduvaid kasulikke vahendeid selle jaoks. Nimetatakse erinevaid programmeerimisvõistlusi ja selleteemalisi materjale. Juhend eeldab, et lugeja on tuttav algoritmide teema ja rekursiooniga.

Populaarsed võistlused

Programmeerimisvõistlusi leidub tänapäeval päris palju. Mitmed veebilehed korraldavad neid regulaarselt ja näiteks järjestikustes voorudes osalemisega on seal võimalik oma skoori tõsta. Võistlustel hinnatakse algoritmide tundmist ja nende väljamõtlemise ning implementeerimise oskust. On pikemaid, mitmepäevaseid võistlusi, aga ka lühikesi, mõnetunniseid võistlusi, kus tuleb kasuks eelnev kogemus, kiire mõtlemine ja klaviatuuril trükkimise kiirus (harjuta trükkimist siin). Enamasti on võistlused individuaalsed, kuid leidub ka selliseid, kus tuleb ülesandeid lahendada meeskonnana. Iga ülesande puhul on kirjeldatud sisendit ja oodatavat väljundit (koos näidetega) ning esitatud lahendus peab punktide saamiseks läbima automaattestid.

Kui oled praeguseks läbinud suurema osa kursusest, võid näiteks järgmistes keskkondades või nende võistlustel juba ülesandeid lahendada küll:

• Eesti Informaatikaolümpiaad - Olümpiaadi eelvooru korraldatakse gümnaasiumi ja põhikooli õpilastele. Iga-aastane lahtine võistlus on kõigile avatud.
• CodeForces - Populaarseim võistluskeskkond.
• AtCoder - Võrreldes keskkonnaga CodeForces on siin lühemad ülesannete kirjeldused ja rohkem matemaatikaga seotud ülesandeid.
• Codechef - Korraldab muuhulgas meeskonnavõistluseid ja pikemaid, mitmepäevaseid võistlusi.
• Sphere Online Judge - On mõeldud rohkem harjutamiseks, võistlused toimuvad harvemini.
• Google's Coding Competitions - Erinevad Google'i korraldatud võistlused. Algajatele on mõeldud võistlus Kick Start.

Ülesande lahenduse leidmine

Võistlustel tuleb kasuks üldine probleemilahendamisoskus ning teadmised arvuteooriast, tõenäosustest, graafidest ja geomeetriast. Tavaliselt on võistlustel eri raskusastmega ülesandeid, nii et osaleda võib julgelt ka ilma varasema kogemuseta. Sellegipoolest on kasulik eelnevalt harjutada ja tutvuda erinevate algoritmide ning ülesandetüüpidega.

Ülesande lahenduse välja mõtlemiseks võib kasutada näiteks kursuse õpikus kirjeldatud George Pólyat juhiseid. Kuna need on mõeldud pigem üldiseks probleemilahendamiseks, siis toome lisaks mõned programmeerimise näpunäited:

• Enne koodi kirjutama asumist mõtle läbi, milline peaks olema algoritm, mis probleemi lahendaks.
• Kui probleem tundub üle jõu käiv, jaga see väiksemateks osadeks kuni oskad iga osa koodina kirja panna.
• Kaalu erinevaid andmestruktuure (järjend, sõne, tabel, puu, graaf, pinu jne.).
• Keerukamate ülesannete puhul on mõistlik lahendus tihti rekursiivne, nii et lahenda piisavalt ülesandeid, mis nõuavad erinevaid rekursioonivorme.
• Kontrolli, kas su lahendus on täpne ja üldine. Vali testimiseks kavalad sisendid, et kontrollida, kas programm töötab ka piirjuhtude korral.

Levinud algoritmide liigid

Algoritmi tüüp	Millal kasutada?	Näide
Ahne	Algoritmi liik, mida kasutatakse probleemide puhul, mille optimaalse lahenduse saab leida nii, et lahenduse igal sammul tehakse lokaalselt optimaalne valik ehk valik, mis on just selle sammu jaoks parim.	Kõik küla majad on vaja ühendada ühte teedesüsteemi nii, et kuluks minimaalselt teematerjali. Kui lisada igal sammul sirge tee kahe lähima maja vahele, nii et tsüklit ei teki, siis saabki lõpuks minimaalse teede puu, mis ühendab majad peateega (Kruskali algoritm).
Jaga ja valitse	Kasutatakse siis, kui ülesande saab jagada eraldiseisvateks alamülesanneteks (enamasti rekursiivselt), kus iga suurema ülesande vastuse saab kokku panna selle otseste alamülesannete vastustest.	Kiirsorteerimine: Järjendis valitakse element, millest ühele poole paigutatakse kõik väiksemad elemendid ning teisele poole suuremad. Seejärel korratakse tegevust rekursiivselt mõlema poole peal.
Dünaamiline planeerimine	Mõistlik kasutada siis, kui ülesande saab jagada alamülesanneteks, millest mõned kattuvad. Iga alamülesande vastus tuleb jätta meelde, et sama alamülesannet ei peaks uuesti osadeks tegema ja lahendama.	Leia, millistel viisidel on võimalik (piiramatu arvu) ühe- ja kahesendiste müntidega mingit rahasummat maksta. Kui kõiki võimalusi otsida, saab iga alamsumma jaoks leitud võimaluste arvu esimesel korral meelde jätta. Leitud arvu saab taaskasutada, kui otsimise käigus on uuesti sama alamsummani jõutakse.
Variantide läbivaatus või jõumeetod	Naiivse "jõumeetodi" puhul vaadatakse läbi kõik vastusevariandid, kuni leitakse sobiv lahendus. Meetodit saab optimeerida, nt. kärpides targalt variantide hulka või uurides neid teatud järjekorras.	Trips-traps-trullis parima käigu valimine arvestades (vastase) järgmisi võimalikke käike.

Lahenduse efektiivsus

Lisaks täpsusele peab programm olema võimalikult kiire ja lõpetama töö teatud aja piires. Mõningate keerulisemate ülesannete puhul tuleb jälgida ka seda, et programm liiga palju mälu ei tarbiks.

Lihtsas rekursiivses Fibonacci arvude leidmise funktsioonis leitakse iga arv kahe eelmise Fibonacci arvu abil. Kui funktsiooni väljakutsete puu joonistada, siis on näha, et see teeb palju korduvaid rekursiivseid väljakutseid.

def fibonacci(n):
    if n == 0 or n == 1:
        # Baasjuht: Kui n on 0 või 1, tagasta vastav väärtus
        return n

    # Muul juhul:
    return fibonacci(n-1) + fibonacci(n-2)

Kui rakendada dünaamilist planeerimist siis tehtud väljakutsete tulemused jäetakse meelde, nii et sinistes tippudes ei pea väärtust uuesti leidma hakkama ehk punasega märgitud väljakutsed saab tegemata jätta:

# Sõnastik leitud Fibonacci arvude hoidmiseks
mälu = {}

def fibonacci_mäluga(n):
    if n == 0 or n == 1:
        # Baasjuht: Kui n on 0 või 1, tagasta vastav väärtus
        return n

    # Muul juhul leia ja/või tagasta mälu[n]
    if n not in mälu:
        mälu[n] = fibonacci_mäluga(n-1) + fibonacci_mäluga(n-2)
    return mälu[n]

Kursused ja võistluprogrammeerimise õpik

Lahendustehnikate, levinud algoritmide ja andmestruktuuride kohta leiab rohkem infot eesti keeles kirjutatud võistlusprogrammeerimise õpikust. See sisaldab muuhulgas kontrollülesanded näidislahendustega ja teste lahenduste kontrollimiseks. Vastavaid teemasid uuritakse ka TÜ kursustel "LTAT.03.005 Algoritmid ja andmestruktuurid" ning "MTAT.03.269 Programmeerimisvõistlused".

Lahenduse optimeerimine

Parim viis programmi ajakulu vähendamiseks on üldiselt võimalikult kiire algoritmi valimine. Kui see on tehtud, võib mõelda optimeerimisele:

• Kasuta vähem kulukaid operatsioone ja käske.
• Hinda ja mõõda vajadusel oma programmi töökiirust (juhised allpool).
• Rekursiivse meetodi iteratiivseks kirjutamine aitab tavaliselt kiirust parandada.
• Uuri Pythoni keelespetsiifilisi nippe (mõned näited).

Ole liigse optimeerimisega ettevaatlik, selle käigus võid programmi ka vigaseks muuta.

Kasulikud Pythoni moodulid

Enamikus keskkondades on võimalik esitada lahendusi, mis on kirjutatud Pythoni, C++, Java või muu keele abil. Enamasti eelistavad edasijõudnud kasutada keelt C++, sest C++ programmid on üldjuhul kõige kiiremad ja on rohkem sisseehitatud raamistikke ning andmestruktuure, mida kasutada. Öeldakse, et kui Python on algajasõbralikum, siis C++ on eksperdisõbralikum. Siin kursusel keskendume teemade tutvustamiseks Pythoni võimalustele. Et elu lihtsamaks teha, on Pythonis võimalik kasutada järgmisi sisseehitatud mooduleid:

• collections - Sisaldab mõningaid mugavaid andmestruktuure.
• itertools - Vahendid kombinatoorika ja keerukamate tsüklite jaoks.
• fractions - Vahendid ujukomaarvude esitamiseks harilike murdudena.
• bisect - Algoritm elementide sisestamiseks järjendisse nii, et see jääks sorteerituks.
• heapq - Algoritmid, mis võimaldavad järjendit kuhjana kasutada.
• time - Kasulik programmi tööaja mõõtmiseks, samuti aja sõneks vormistamiseks.
• timeit - Funktsioonide tööaja mõõtmiseks.
• cProfile - Aitab näha, milliseid väljakutseid mingi funktsioon teeb ja millele enim aega kulub.
• tracemalloc - Programmi mälukasutuse mõõtmiseks.

Ajakulu mõõtmine

Protseduuri ajaline keerukus aitab hinnata, kui kaua mingi protseduur aega võtab sõltuvalt sisendi suurusest. Sisendandmete mahu {$ \large{x} $} puhul väljendatakse seda formaalselt kujul {$ \large{O(x)} $}. Lihtsustatult öeldes on see ligikaudne operatsioonide arv, mida algoritm teeb. Enda algoritmi ajalist keerukust saab hinnata näiteks selle järgi, milliseid operatsioone see kasutab ning kui palju tsüklikorduseid kuskil tehakse. Pythoni andmestruktuuridega tehtavate operatsioonide ajalist keerukust saab järele vaadata siit: https://wiki.python.org/moin/TimeComplexity.

Samuti võib testida, kui kaua programmil mingi koodi täitmiseks aega kulub. Kõige lihtsam on seda teha funktsiooni time() abil:

from time import time

t1 = time()
# Mingid tegevused...
t2 = time()

print("Kulus", t2-t1, "ms.")

Timeit

Järgnev kood kasutab funktsiooni timeit, et testida, kas 10 miljoni elemendiga järjendis on erinevate elementide esinemissagedust kiirem kokku lugeda tsükli või moodulis collections asuva objekti Counter abil. Tasub kasutada võimalikult suuri andmehulki, sest siis on mõõtmine täpsem - niimoodi testivad ajakulu ka võistluste automaattestid. Antud andmemahu korral peaks Counter olema peaaegu 2 korda kiirem kui tsükliga loendamine.

from random import choices
from collections import Counter, defaultdict
from timeit import timeit

# 10 miljonit juhuarvu vahemikust 0...9
a = choices(range(0, 10), k=10**7)

def loendur_Counter():
    d = Counter(a)

def loendur_tsükkel():
    d = defaultdict(int) # vaikimisiväärtus sõnastikus on 0
    for elem in a:
        d[elem] += 1

print("counter:", timeit(loendur_Counter, number=1)) # Jooksutab 'loendur_Counter' ühe korra
print("tsükkel:", timeit(loendur_tsükkel, number=1)) # Jooksutab 'loendur_tsükkel' ühe korra

Fibonacci ajakulu

Samamoodi võib võrrelda ka kahe eelnevalt vaadatud Fibonacci funktsiooni tööaega. Kuna neid funktsioone tuleb kutsuda koos parameetriga (n), siis on funktsioonile timeit antavad käsud mõistlikum vormistada sõnena.

Tegelikult käivitab timeit talle antud käsu eraldiseisvas keskkonnas, nii et nüüd tuleb ka vajalikud muutujad kaasa anda nimede sõnastikuna:

muutujad = {
    "fibonacci": fibonacci,
    "fibonacci_mäluga": fibonacci_mäluga,
    "mälu": {}
}

# Jooksutab sõne kujul antud käsud koos vajalike muutujatega:
t1 = timeit("fibonacci(35)", number=1, globals=muutujad)
t2 = timeit("fibonacci_mäluga(35)", number=1, globals=muutujad)

print("Mäluta:", t1, "mäluga:", t2)

Ilma mäluta funktsioonil võib 35nda Fibonacci arvu leidmiseks kuluda üle 10 sekundi (väljakutsete puu tuleb väga suur!). Mäluga funktsioon peaks olema vähemalt 100000 korda kiirem:

>>> %Run fibonacci_test.py
Mäluta: 11.4891262 mäluga: 2.8799999999051806e-05

Profileerimine

Moodul cProfile aitab detailsemalt (kuigi vahel vähem täpselt!) ajakulu hinnata ja loeb kokku erinevate funktsioonide väljakutsed. Moodulis asuvale käsule run peab andma käivitatava koodi sõne kujul ning see väljastab ekraanile tabeli. Viimases näites polnud eriti palju erinevaid funktsiooni väljakutseid, nii et toome cProfile.run demonstreerimiseks uue näite:

from random import randint
from cProfile import run

def lisa_juhuarv(järjend):
    järjend.append(randint(0,10))

def juhujärjend():
    järjend = []
    for i in range(10**6):
        lisa_juhuarv(järjend)
    return järjend

run("juhujärjend()")

Käivitades peaks tekkima tabel (vajadusel impordi mooduli cProfile asemel moodul profile):

>>> %Run test2.py
         7453709 function calls in 2.343 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    2.343    2.343 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 cpython_backend.py:313(_custom_import)
  1000000    0.511    0.000    0.735    0.000 random.py:237(_randbelow_with_getrandbits)
  1000000    0.552    0.000    1.287    0.000 random.py:290(randrange)
  1000000    0.304    0.000    1.591    0.000 random.py:334(randint)
  1000000    0.440    0.000    2.146    0.000 test2.py:18(lisa_juhuarv)
        1    0.195    0.195    2.341    2.341 test2.py:21(juhujärjend)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.__import__}
        1    0.000    0.000    2.343    2.343 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
  1000000    0.115    0.000    0.115    0.000 {method 'append' of 'list' objects}
  1000000    0.090    0.000    0.090    0.000 {method 'bit_length' of 'int' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
  1453700    0.134    0.000    0.134    0.000 {method 'getrandbits' of '_random.Random' objects}

>>> 

• Veerus ncalls on märgitud funktsiooni väljakutsete arv.
• Veerg tottime ütleb, kui palju aega kulus funktsioonis kõigi väljakutsete peale kokku, välja arvatud aeg, mis kulus funktsioonis asuvate teiste funktsioonide väljakutsumiseks ja täitmiseks.
• Veerus cumtime on juurde arvatud ka aeg, mis kulus funktsiooni alamfunktsioonide täitmiseks.
• Veergudes percall on kirjas, kui palju aega igale väljakutsele keskmiselt kulus.
• Viimases veerus on kirjas vastava mooduli või faili nimi või sisseehitatud funktsiooni või meetodi kirjeldus. Faili nimele järgneb veel koolon ja funktsiooni reanumber koos selle nimega.

Mida võib tulemustest välja lugeda? Praegu ei pea kõigile ridadele tähelepanu pöörama. Näiteks read {built-in method builtins.exec}, <string>:1(<module>) ja {method 'disable' of '_lsprof.Profiler' objects} viitavad lihtsalt sellele, et programm käivitati ja midagi profileeriti. Huvi võiksid pakkuda oma failis kasutatud funktsioonid:

1. Kõigepealt kutsuti funktsioon juhujärjend. On näha, et selle funktsiooni täitmisele kulutatud aeg (cumtime) on suurim. Samas ei ole eriti suur konkreetselt selles funktsioonis veedetud aeg (tottime).
2. Suurem osa ajast selles funktsioonis kulub funktsiooni lisa_juhuarv täitmisele, aga ka seal ei viibita nii pikalt. Täidetakse hoopis meetodit järjend.append ja funktsiooni randint.
3. Meetodit append täidetakse küll 1000000 korda, aga sellele kulub siiski palju vähem aega kui funktsioonile randint, mida täidetakse sama palju kordi.
4. Funktsioon randint on pärit failist random.py (moodul random) ja kutsub omakorda seal funktsiooni randrange jne. Faili random.py edasisi funktsioone vaatama ei pea. Saime teada, et siin programmis kulub enim aega käsu randint(0,10) täitmisele.

Kui on teada, milliseid programmiosi kasutatakse kõige rohkem ning millele enim aega kulub, on võimalik need kohad efektiivsemaks muuta, teisi käske või algoritme kasutada või programmi ümber struktureerida.

Enesekontrolliküsimused

Ülesanne

Tee endale keskkonnas CodeForces kasutaja ja esita sealses Eesti võistlusprogrammeerimise grupis mõne ülesande lahendus. Võistlusprogrammeerimise õpikus on olemas grupiga liitumise juhend.