Algoritmi un // to efektivitāte
Kā dators atrod vienu vārdu starp miljoniem? Apgūsti bināro meklēšanu,
kārtošanas algoritmus un Big O notāciju - rīkus,
kas palīdz prognozēt, vai kods darbosies ātri ar miljoniem ierakstu.
Tēmas saturs - 6 stundas
No lineārās meklēšanas līdz Big O - katru jēdzienu apgūsti ar praktisku kodu.
Meklēšanas pamati
Lineārā pret bināro meklēšanu - kāpēc binārā ir neticami ātra kārtotā masīvā.
Kārtošanas loģika
Bubble sort un selection sort - kā dators sakārto datus un cik daudz darba tas prasa.
Big O un Sarežģītība
Četras sarežģītības klases grafikā - O(1), O(log n), O(n), O(n²) un to praktiskā nozīme.
Iebūvēto funkciju ātrums
Python iebūvētās funkcijas pret rokraksta algoritmiem - mēra ar timeit.
Iebūvēto funkciju efektivitāte
map(), filter() un reduce() - datu apstrādes pipeline funkcionālā stilā.
Noslēguma projekts: Koda lauzējs
Dators ar bināro meklēšanu min skaitli, skaita mēģinājumus un pamana pretrunas.
7. tēmas špikeris - algoritmi un to efektivitāte
Meklēšana, kārtošana, Big O un pareizās datu struktūras izvēle. Katrs bloks atbilst vienai stundai.
7.1 Lineārā un binārā meklēšana
def linear_search(saraksts, mekletais):
for i, elements in enumerate(saraksts):
if elements == mekletais:
return i
return -1 # nav atrasts
def binary_search(saraksts, mekletais): # TIKAI sakārtotā sarakstā!
apaksa, augsa, soli = 0, len(saraksts) - 1, 0
while apaksa <= augsa: # <= , nevis <
soli += 1
vidus = (apaksa + augsa) // 2
if saraksts[vidus] == mekletais:
return vidus, soli
elif saraksts[vidus] < mekletais:
apaksa = vidus + 1 # +1 izslēdz pārbaudīto vidu
else:
augsa = vidus - 1 # -1 izslēdz pārbaudīto vidu
return -1, soli
# 1000 elementi: lineārā līdz 1000 soļiem , binārā ~10 soļiBez +1 un -1 cikls var griezties mūžīgi - tur iestrēgst lielākā daļa.
7.2 Burbuļkārtošana
def bubble_sort(saraksts):
n = len(saraksts)
salidzinajumi = 0
for j in range(n):
mainits = False
for i in range(n - 1 - j): # -j: beigas jau ir sakārtotas
salidzinajumi += 1
if saraksts[i] > saraksts[i + 1]:
# apmaiņa vienā rindā, bez pagaidu mainīgā
saraksts[i], saraksts[i + 1] = saraksts[i + 1], saraksts[i]
mainits = True
if not mainits: # jau sakārtots - beidzam
break
return saraksts, salidzinajumi
# Divi cikli:
# iekšējais - viens gājiens, aizstumj lielāko uz beigām
# ārējais - atkārto gājienu, cik reižu vajag6 elementiem ~15 salīdzinājumi, 10 elementiem ~45. Divkāršojot datus, darbs pieaug četrkārt.
7.3 Big O - kā laiks aug
# O(1) nemainās saraksts[0]
# O(log n) +daži soļi binārā meklēšana
# O(n) 10x viens cikls
# O(n log n) ~13x sorted()
# O(n^2) 100x divi ligzdoti cikli
import time
for n in (100, 1000):
dati = list(range(n))
t0 = time.time()
kopa = sum(dati) # O(n)
t1 = time.time()
t2 = time.time()
for x in dati: # O(n^2)
for y in dati:
pass
t3 = time.time()
print(f"n={n}: O(n)={t1-t0:.5f}s O(n^2)={t3-t2:.5f}s")
# Svarīgs nav sekunžu skaits, bet CIK REIZES laiks pieaug,
# palielinot datus 10x.Big O nemēra sekundēs, jo katrs dators ir citāds. Tas mēra soļu skaita pieaugumu.
7.4 Iebūvētās funkcijas pret pašrakstītu ciklu
dati = list(range(5_000_000))
# Pašrakstīts cikls - O(n)
lielakais = dati[0]
for x in dati:
if x > lielakais:
lielakais = x
# Iebūvētā funkcija - ARĪ O(n), bet vairākas reizes ātrāka
lielakais = max(dati)
# Kāpēc? Iebūvētās funkcijas ir rakstītas C valodā,
# tāpēc to cikls neiet caur Python interpretatoru.
min(dati) max(dati) sum(dati) len(dati) sorted(dati)
# len() ir O(1) - Python garumu glabā atsevišķi, neskaita katru reizi
# sorted() lieto Timsort - O(n log n), nevis O(n^2) kā burbulisVienāds Big O vēl nenozīmē vienādu ātrumu - iebūvētā versija ir gan ātrāka, gan īsāka.
7.5-7.6 Datu struktūras izvēle un binārā stratēģija
import time
n = 200_000
kā_saraksts = list(range(n))
kā_kopa = set(kā_saraksts) # tie paši dati, cita struktūra
199_999 in kā_saraksts # O(n) - iet cauri visiem
199_999 in kā_kopa # O(1) - aprēķina vietu uzreiz, simtiem reižu ātrāk
# Ko kad lietot:
# saraksts (list) kārtība svarīga, drīkst dublikāti -> TOP 5
# kopa (set) tikai pārbaude "vai ir" -> vārdu saraksts
# vārdnīca (dict) atslēga -> vērtība -> profils
# Binārā stratēģija darbībā (7.6 projekts)
apaksa, augsa = 1, 100
minejums = (apaksa + augsa) // 2 # pirmais minējums vienmēr 50
if atbilde == "lielaks": apaksa = minejums + 1
elif atbilde == "mazaks": augsa = minejums - 1
if apaksa > augsa: print("Atbildes ir pretrunīgas!")
# 100 skaitļiem: ne vairāk kā 7 minējumiĀtrumu bieži uzlabo, nomainot datu struktūru, nevis pārrakstot algoritmu.