7. tēma: Algoritmi. 4. stunda: Iebūvēto funkciju efektivitāte.

Tavs šīs stundas izaicinājums: Tu proti rakstīt kārtošanas un meklēšanas algoritmus no nulles, kas ir būtiski loģikas izpratnei. Taču profesionālā izstrādē prioritāte ir koda efektivitāte un izpildes ātrums. Šajā stundā pētīsim, kāpēc Python iebūvētās funkcijas ātrdarbībā pārspēj mūsu pašu rakstīto kodu un kāpēc tās ir nozares standarts.

SR 2.4.19. (Skolēns izmanto gatavus algoritmus tipveida uzdevumu risināšanai)
SR 2.4.16. (Skolēns novērtē algoritmu sarežģītību un efektivitāti)

Teorija: Kāpēc iebūvētās funkcijas ir ātrākas?

Zem pārsega slēpjas "C" valoda: Python iebūvētās funkcijas nav rakstītas pašā Python valodā. Tās ir ieprogrammētas "C" valodā, kas atrodas tuvāk datora aparatūrai (dzelžiem). Tāpēc tās darbojas ievērojami ātrāk.
min() un max() funkcijas:
- Dators tik un tā iziet cauri visam sarakstam, tātad sarežģītība joprojām ir O(n) (lineāra).
- Atšķirība ir tajā, ka šis cikls izpildās "C" valodas līmenī, nevis caur Python interpretatoru, iegūstot ievērojamu ātruma pārsvaru.
sorted() un Timsort:
- Python neizmanto lēno burbuļkārtošanu (O(n²)).
- Kārtošanai tiek izmantots hibrīdalgoritms Timsort, kura sarežģītība ir O(n log n). Tas spēj sakārtot miljoniem elementu sekundes daļā.
Zelta likums: Vienmēr izmanto iebūvētās funkcijas datu meklēšanai un kārtošanai, ja vien nav nepieciešama ļoti specifiska spēles loģika, ko standartfunkcijas neatbalsta.

Vides sagatavošana (Windows)

Atver PowerShell.
Ieej algoritmu mapē: cd Tema7_Algoritmi
Izveido jaunu failu un atver to kodu redaktorā: ni iebuvetas_funkcijas.py; code iebuvetas_funkcijas.py

Praktiskie uzdevumi

1. Līmenis (Vienkāršs): "Lielākais ienaidnieks"

Atradīsim vājāko un spēcīgāko ienaidnieku datu masīvā, izmantojot vienas rindas iebūvētās komandas.

Failā iebuvetas_funkcijas.py izveido sarakstu ienaidnieku_hp ar 10 dažādām skaitliskām vērtībām.
Izmanto funkciju min(), lai atrastu mazāko vērtību, un saglabā to mainīgajā vajakais.
Izmanto funkciju max(), lai atrastu lielāko vērtību, un saglabā to mainīgajā stiprakais.
Izdrukā abus rezultātus.

ienaidnieku_hp = [45, 12, 89, 3, 99, 21, 50, 77, 8, 34]

vajakais = min(ienaidnieku_hp)
stiprakais = max(ienaidnieku_hp)

print(f"Vājākais ienaidnieks: {vajakais} HP")
print(f"Spēcīgākais ienaidnieks: {stiprakais} HP")

Vājākais ienaidnieks: 3 HP
Spēcīgākais ienaidnieks: 99 HP

2. Līmenis (Viduvējs): "Ātruma sacīkstes (O(n) pret O(n))"

Pārbaudīsim praksē apgalvojumu, ka iebūvētais "C" kods ir ātrāks par tīru Python kodu, pat ja abiem ir lineāra sarežģītība O(n).

Faila sākumā importē bibliotēku time.
Izveido sarakstu lieli_dati = list(range(5000000)) (5 miljoni skaitļu).
Uzraksti savu for ciklu, kas atrod lielāko skaitli sarakstā, un nomēri tā izpildes laiku.
Nomēri izpildes laiku Python iebūvētajai funkcijai max(lieli_dati).
Izdrukā un salīdzini abus rezultātus.

import time

lieli_dati = list(range(5000000))

# 1. Mūsu pašu rakstītais O(n) cikls
sakums_savs = time.time()
lielakais_savs = lieli_dati[0]
for skaitlis in lieli_dati:
    if skaitlis > lielakais_savs:
        lielakais_savs = skaitlis
laiks_savs = time.time() - sakums_savs

# 2. Python iebūvētā O(n) funkcija
sakums_ieb = time.time()
lielakais_ieb = max(lieli_dati)
laiks_ieb = time.time() - sakums_ieb

print(f"Paša rakstīts cikls aizņēma: {laiks_savs:.5f}s")
print(f"Iebūvētā max() funkcija aizņēma: {laiks_ieb:.5f}s")

Paša rakstīts cikls aizņēma: 0.18520s
Iebūvētā max() funkcija aizņēma: 0.04110s

3. Līmenis (Padziļināts): "Timsort pret Burbuli"

Ja pie O(n) atšķirība ir mērāma sekundes simtdaļās, kas notiks, ja salīdzināsim mūsu O(n²) Bubble Sort ar Python iebūvēto O(n log n) Timsort algoritmu?

Iekopē savu bubble_sort(saraksts) funkciju no iepriekšējām stundām (izņem no tās `print` komandu, lai nepiesārņotu ekrānu).
Izveido apgrieztā secībā sakārtotu sarakstu ar 5000 elementiem (tas ir sliktākais scenārijs kārtošanai): dati_burbulim = list(range(5000, 0, -1)) un tādu pašu sarakstu dati_timsort.
Nomēri, cik ilgu laiku prasa izsaukt bubble_sort(dati_burbulim).
Nomēri, cik ilgu laiku prasa izsaukt sorted(dati_timsort).

def bubble_sort(saraksts):
    elementu_skaits = len(saraksts)
    for j in range(elementu_skaits):
        for i in range(elementu_skaits - 1):
            if saraksts[i] > saraksts[i + 1]:
                saraksts[i], saraksts[i + 1] = saraksts[i + 1], saraksts[i]
    return saraksts

# Sagatavojam datus (5000 elementi apgrieztā secībā)
dati_burbulim = list(range(5000, 0, -1))
dati_timsort = list(range(5000, 0, -1))

# Mērām Burbuli O(n^2)
sakums = time.time()
bubble_sort(dati_burbulim)
laiks_burbulis = time.time() - sakums

# Mērām Python iebūvēto sorted() O(n log n)
sakums = time.time()
sorted(dati_timsort)
laiks_timsort = time.time() - sakums

print(f"Bubble Sort (5000 el.) laiks: {laiks_burbulis:.5f}s")
print(f"Timsort (sorted) laiks: {laiks_timsort:.5f}s")

Bubble Sort (5000 el.) laiks: 1.25010s
Timsort (sorted) laiks: 0.00015s