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

Tavs šīs stundas izaicinājums: Tu esi iemācījies "izgudrot riteni" — rakstīt meklēšanas un kārtošanas algoritmus no nulles. Tas ir svarīgi izpratnei. Bet šodien Tu uzzināsi, kāpēc profesionāļi ikdienā izmanto Python iebūvētās funkcijas un kā tās pārspēj mūsu rakstīto kodu ātruma sacīkstēs.

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

Vides sagatavošana (Windows)

1. Atver PowerShell.
2. Ieej algoritmu mapē: cd Tema7_Algoritmi
3. 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 masīvā ar vienas rindas komandām.

1. Failā iebuvetas_funkcijas.py izveido sarakstu ienaidnieku_hp ar 10 dažādām skaitliskām vērtībām.
2. Izmanto funkciju min(), lai atrastu mazāko vērtību, un saglabā to mainīgajā vajakais.
3. Izmanto funkciju max(), lai atrastu lielāko vērtību, un saglabā to mainīgajā stiprakais.
4. 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")

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).

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

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")

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

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

1. Iekopē savu bubble_sort(saraksts) funkciju no 2. stundas faila. (Izņem no tās `print` komandu, lai nepiesārņotu ekrānu).
2. 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.
3. Nomēri, cik ilgu laiku prasa izsaukt bubble_sort(dati_burbulim).
4. 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)
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")