Loeng 5: Määramata ja määratud itereerimine, while ja for tsüklid/blokid, lausendid: continue, break, funktsioonid input ja enumerate, iteraatortoega andmetüübid

Viimati uuendatud 27.09.2025.

---

Koodinäited

1  Itereerimine Pythonis

Itereerimine hõlmab endas teatud koodiosa (mitmekordset) taaskasutamist. Programmi struktuuri mis seda teostab nimetame iteratsioonitsükkliks. Programmeerimises eristame kahte tüüpi tsükkleid: määramata ja määratud.

1.1  Omistuslause ja koodi mitmekordne taaskasutus

1.1.1  Muutujate ülekirjutamine (reassignment) ja uuendamine (updating)

Sa oled kindlasti tähele pannud, et ühele muutujale saab omistada väärtusi mitu korda. Täpsemalt me saame väärtusi taasomitada või uuesti väärtustada või lihtsaltsamalt öeldes üle kirjutada:

x = 1
print(x)
x = 3  # Viitab uuele objektile.
print(x)

1
3

Samas saame muutujale omistatud objekti uuendada kasutades nt. operaatoreid +=, -= jne.:

x = 1
print(x)
x = x + 2
print(x)
x += 2  # Sama mis x = x + 2.
print(x)

1
3
5

Uuendame muutujat x suurendades täisarvu 1 ühe võrra kaks korda:

x = 1
print(x)
x += 1  # Sama mis x = x + samm.
x += 1
print(x)

1
3

Kasutades morsaoperaatorit := saame ühe rea kokku hoida:

print(x := 1)
x += 1
x += 1
print(x)

1
3

1.1.2  Muutujale teise muutja omistamine

Teatavasti saame ühele muutjale omistada teise, vt. Loeng 2. Matemaatikas on kahe muutuja võrdsus kas tõene või väär ja seda alatiseks. Kui a = b praegu, siis a on alati võrdne b-ga. Pythonis võib omistuslause muuta kaks muutujat võrdseks (tegelikuses viide andmetüübi objektile), kuid nad ei pea selliseks jääma:

a = 2
print('a =', a)
b = a  # Muutujad a ja b on võrdsed.
print('b = a =', b)
a = 4  # Muutujad a ja b ei ole enam võrdsed.
print('a =', a)
print('b =', b)  # Muutuja b väärtus endiselt 2. Vt. allolev märkus.

a = 2
b = a = 2
a = 4
b = 2

Rida 5 muudab muutuja a väärtust, kuid ei muuda muutuja b väärtust, seega nad ei ole enam võrdsed. Muutujate uuendamine (uuesti väärtustamine) on sageli kasulik, kuid seda tuleks kasutada ettevaatlikult. Kui muutujate väärtused muutuvad koodis tihti, võib see muuta koodi raskesti loetavaks ja silumise ehk vigade otsimise keeruliseks.

Märkus: Pane tähele, et see näide käitub erinevalt Loengus 2, Punktis 3.1.2, toodud näitele.

1.2  Määramata iteratsioon: while-tsükkel (indefinite iteration: while-loop)

Määramata tsükklis on iteratsioonide arv esitatud ilmutamata kujul. Me kordame teatud tegevust seni kuni etteantud tingimus on rahuldatud. Joonis 1 kujutab määramata iteratsiooni ehk while-tsükli voodiagrammi. Määratud iteratsiooni tsüklis on iteratsioonide arv ilmutatud kujul teada tsükli käivitamise hetkel.

1.2.1  while-tsükkel

Tsükli blokk defineeritakse lausendiga while. Kodeerija peab tagama selle, et koodis toimuks mingi muutus mida saab tingimuslause abil kinni püüda. Joonisel 1 on kujutatud while-tsükli voodiagramm.

Joonis 1: while-tsükli voodiagramm.

Joonisel 1 kujutatud voodiagrammile vastav olukord. Siin suurendame või vähendame muutuja n väärtust:

n = 0
while n < 3:  # NB! koolon ja taane.
    n += 1    # Sama mis n = n + 1.
    print(n)

1
2
3

n = 3
while n > 0:
    print(n)
    n -= 1  # Sama mis n = n - 1.

3
2
1

Suurendame muutuja i väärtust:

i = 0
lst = [12, 11, 10]
while i != len(lst):
    print(lst[i])
    i += 1

12
11
10

Lõpmatu tsükli automaatset peatamist Python ei teosta. Seega ole ettevaatlik! Rekursiooni puhul eksisteeris rekursiooni maksimaalne limiit mille puhul tõstatati erisus RecursionError. Tsüklitel selline kaitsemehhanism puudub. Praktikas on tsüklid piiratud ainult operatsioonisüsteemi ja raudvara vabade ressurssidega.

while False:  # Kui True siis lõpmatu tsükkel.
    print('Python')

1.2.2  Konstruktsioon while-break ja sisseehitatud funktsioon input

Lausend break murrab protsessi tsüklist välja. Lausend break peatab iteratsiooni protsessi. Tavaliselt esineb see lausend koos tingimuslausega. Joonis 2 kujutab while-break konstruktsiooni voodiagrammi.

Joonis 2: while-tsüklis oleva while-break konstruktsiooni voodiagramm.

Joonisel 2 kujutatud voodiagrammile vastav olukord kui tingimus rahuldub:

n = 5
while n > 0:
    n -= 1
    if n == 2:
        break
    print(n)

print('Oleme tsüklist väljas.')

4
3
Oleme tsüklist väljas.

Kui tingimus ei rahuldu:

n = 5
while n > 0:
    n -= 1
    if False:
        break
    print(n)

print('Oleme tsüklist väljas.')

4
3
2
1
0
Oleme tsüklist väljas.

Uus funktsioon: Sisseehitatud funktsiooni input tutvustus. Loe dokumentatsiooni.
Näide: Pangaautomaadi versioon 1.

raha_masinas = 3
raha_soov = int(input('Kui palju raha tahad?'))  # Sisseehitatud funktsioon input.

i = 1
while i <= raha_soov:
    if i > raha_masinas:
        print('Masinas sai raha otsa. Vabandame.')
        break
    print('1 euro')
    i += 1

print('Head aega.')

1 euro
1 euro
1 euro
Masinas sai raha otsa. Vabandame.
Head aega.

1.2.3  Konstruktsioon while-continue

Lausend continue peatab hetkel teostatavat iteratsiooni ja alustab järgmise iteratsiooni tsükliga. Tavaliselt esineb see lausend koos tingimuslausega. Joonis 3 kujutab while-continue konstruktsiooni voodiagrammi.

Joonis 3: while-tsüklis oleva while-continue konstruktsiooni voodiagramm.

Joonisel 3 kujutatud voodiagrammile vastav olukord kus tingimuslause rahuldatakse:

n = 4
while n > 1:
    n -= 1
    if n == 2:
        continue  # Liigume tsükli ehk uue iteratsiooni algusesse.  
    print(n, 'minutit.')

3 minutit.
1 minutit.

Tingimuslause ei rahuldu:

n = 4
while n > 1:
    n -= 1
    if False:
        continue  # Liigume tsükli ehk uue iteratsiooni algusesse.
    print(n, 'minutit.')

3 minutit.
2 minutit.
1 minutit.

Näide: Täisarvud ühe ja viie vahel mis EI jagu kolmega.

i = 1
while i <= 5:
    if i % 3 == 0:
        i += 1
        continue
    print(i)
    i += 1

1
2
4
5

1.2.4  Konstruktsioon while-continue-break

Lausendeid continue ja break saab kasutada koos. Joonis 4 kujutab konstruktsiooni while-continue-break voodiagrammi.

Joonis 4: while-tsüklis oleva while-continue-break konstruktsiooni voodiagramm.

Näide: Lausendite continue ja break kasutamine ühes while-tsüklis. Alloleva näite üldistatud voodiagramm on kujutatud Joonisel 4.

i = 0
while i < 10:
    i += 1
    if i <= 3:
        continue
    elif i > 6:
        break
    print(i)

4
5
6

1.2.5  Konstruktsioonid while-else ja while-break-else

Python lubab lisada lausendi else while-tsükli lõppu. Tegevus mis kaasneb lausendiga else defineeritud blokis teostatakse juhul kui kõik while-tsükli iteratsioonid on teostatud (tsükkel on ammendunud), st., et lausend break pole tsüklit enneaegselt lõpetanud. Joonised 5 ja 6 kujutavad while-else konstruktsiooni voodiagramme juhul kui tsüklis ei esine lausendit break ja kui see esineb.

Joonis 5: while-tsüklis oleva while-else konstruktsiooni voodiagramm.

Joonisel 5 vastav olukord kui lausend break puudub:

n = 3
while n > 0:  # Lausend break puudub.
    n -= 1
    print(n)
else:
    print('Tsükkel ammendus.')  # Teostub alati.

2
1
0
Tsükkel ammendus.

Sama tulemuse saad kasutades koodi (isegi kui lausend break oleks olemas ja see peataks tsükli):

n = 3
while n > 0:  # Lausend break ja else puuduvad.
    n -= 1
    print(n)
    
print('Tsükkel ammendus.')  # Teostub alati.

2
1
0
Tsükkel ammendus.

Joonis 6: while-tsüklis oleva while-break-else konstruktsiooni voodiagramm.

Lausend break on olemas ja tsükkel peatub enneaegselt:

n = 4
while n > 0:
    n -= 1
    print(n)
    if n == 2:  # Peatub enneaegselt.
        break
else:
    print('Tsükkel lõpetatud.')  # NB! Ei prindi, vt. Joonis 6.

3
2

Lausend break on olemas aga tsükkel EI peatu enneaegselt:

n = 4
while n > 0:
    n -= 1
    print(n)
    if False:  # Ei peatu enneaegselt.
        break
else:
    print('Tsükkel lõpetatud.')  # NB! Prindib, vt. Joonis 6.

3
2
1
0
Tsükkel lõpetatud.

Näide: Leia vahemikus $[1, n]$ kus täisarv $n > 1$ olevate arvude seast esimene viiega jaguv arv. Prindi see arv konsooli. Kui arvude seas puudub viiega jaguv arv prindi sellekohane teade (ainult üks kord). Kasuta ühte while-tsüklit.

Vale lahendus võrdluseks:

mitu_arvu = 3
i = 0
while i < mitu_arvu:
    i += 1
    if i % 5 == 0:
        print(i)
        break
    else:
        print('[Vale] Arvu ei leitud.')  # Vale, prindib mitu korda.   

[Vale] Arvu ei leitud.
[Vale] Arvu ei leitud.
[Vale] Arvu ei leitud.

Õige lahendus:

mitu_arvu = 3
i = 0
while i < mitu_arvu:
    i += 1
    if i % 5 == 0:
        print(i)
        break
else:
    print('[Õige] Arvu ei leitud.')  # Õige, prindib üks kord.

[Õige] Arvu ei leitud.

Näide: Pangaautomaat versioon 2.

raha_masinas = 3
raha_soov = int(input('Kui palju raha tahad?'))

i = 1
while i <= raha_soov:
    if i > raha_masinas:
        print('Masinas sai raha otsa. Vabandame.')
        break
    print('1 euro')
    i += 1
else:
    print('Head aega.')  # Pole mõtet head päeva soovida kui raha ei antud.

1 euro
1 euro
1 euro
Masinas sai raha otsa. Vabandame.

1.2.6  Pesastatud while-tsükkel

while-tsükleid saab üksteise sisse pesastada. Joonis 7 kujutab while-tsüklisse pesastatud while-tsükli voodiagrammi.

Joonis 7: while-tsüklisse pesastatud while-tsükli voodiagramm. Pesastatud tsükkel on tähistatud rohelise kinnise kõveraga.

Joonisel 7 kujutatud voodiagrammile vastav olukord:

i = 0
j = 2
while i < 4:
    i += 1
    while j > 0 and i == 3:
        print('Pesastatud:', j)
        j -= 1
    print(i)

1
2
Pesastatud: 2
Pesastatud: 1
3
4

Näide: Nädal ja nädalapäevade tunnid.

päevad = ['E', 'L', 'P']
päeva_pikkus = 2  # Tundides.

i = 0
while i < len(päevad):
    print(päevad[i])
    tund = 0
    while tund <= päeva_pikkus:
        print(f'kell on {tund}.')
        tund += 1
    i += 1

print('\nUus nädal.')

E
kell on 0.
kell on 1.
kell on 2.
L
kell on 0.
kell on 1.
kell on 2.
P
kell on 0.
kell on 1.
kell on 2.

Uus nädal.

1.3  Määratud iteratsioon: for-tsükkel (definite iteration: for-loop)

Pythoni for-tsükli abil defineerime määratud iteratsiooni kus iteratsioonide arv on itereerimise alguses ilmne. Määratud iteratsiooni for-tsükkel ja sellesse kuuluv koodiblokk defineeritakse kasutades lausendit for.

1.3.1  Iteraatortoega objektid (iterables)

Määratud iteratsiooni tsüklis ehk for-tsüklis itereeritakse üle etteantud iteraatortoega objektide või jadade (üldine nimi inglise keeles on iterables). Joonis 8 kujutab for-tsükli voodiagrammi.

Iteraatortoega andmetüübid ja nende objektid on:

• sõne
• list (järjend, loend)
• korteež
• sõnastik
• hulk
• vahemik - range, range([<start>,] <stop>, [<step>])

Märkus: Lisaks eelmainitule saab itereerida ka üle generaatorite. Generaatoritest ja nende kasutamisest räägime Loengus 7.

Joonis 8: for-tsükli voodiagramm. Kriipjoonega tähistatud tegevused (indeksi i suurendamine ühe võrra) on automatiseeritud.

1.3.2  for-tsükkel ja sisseehitatud funktsioon enumerate

Defineerime for-bloki ja itereerime üle iteraatortoega objektide kasutades operaatorit in. Joonisel 8 kujutatud voodiagrammile vastavad näited:

a = 'Python'

for letter in a:  # NB! operaator in pakib lahti.
    print(letter, end=' ')

P y t h o n 

lst = [6, 5, 4]

for i in lst:
    print(i)

6
5
4

tpl = (6, 5, 4)

for i in tpl:
    print(i)

6
5
4

dictionary = {'foo': 1, 'bar': 2, 'baz': 3}

for k in dictionary:  # Vaikimisi väljastab võtmed.
    print(k)

foo
bar
baz

for k in dictionary:
    print(dictionary[k])

1
2
3

for key, value in dictionary.items():  # Operaator in ja lahtipakkimine.
    print(key, ':', value)

foo : 1
bar : 2
baz : 3

for k in dictionary:
    print(k, ':', dictionary[k])

foo : 1
bar : 2
baz : 3

s = {6, 5, 4}

for i in s:
    print(i)  # Hulk pole järjestatud.

4
5
6

Sisseehitatud vahemikku defineeriva funktsiooni range kasutamise näited:

for i in range(3):  # Genereerib tulemuse iga iteratsiooni alguses.
    print(i)

0
1
2

for i in range(2, 17, 5):  # range([<algus>,] <lõpp>, [<samm>])
    print(i)

2
7
12

Uus funktsioon: Sisseehitatud funktsiooni enumerate tutvustus. Loe dokumentatsiooni.

lst = ['Liisa', 'Juulius', 'Mari']
print(list(enumerate(lst)))

[(0, 'Liisa'), (1, 'Juulius'), (2, 'Mari')]

for i, item in [(0, 'Liisa'), (1, 'Juulius')]:  # Operaator in ja lahtipakkimine.
    print(i, '-->', item)

0 --> Liisa
1 --> Juulius

for i, item in enumerate(lst):
    print(i, '-->', item)

0 --> Liisa
1 --> Juulius
2 --> Mari

Näide: Omista indeksid listis olevatele nimedele. Praktikas tihti esinev probleem.
Pikem lahendus võrdluseks:

sõbrad = ['Mari', 'Mai', 'Olev']

index = 0
for nimi in sõbrad:
    print(index, nimi)
    index += 1

0 Mari
1 Mai
2 Olev

Lühem lahendus mis kasutab for-tsüklit ja funktsiooni enumerate:

for index, nimi in enumerate(sõbrad):
    print(index, nimi)

0 Mari
1 Mai
2 Olev

Näide: Arvu iteratiivne astendamine.

def astenda(arv, aste):
    tulem = 1
    for _ in range(aste):  # Kui tead, et ei kasuta muutujat, nimetame _ või _i.
        tulem *= arv
    return tulem

astenda(2, 3)

8

1.3.3  Konstruktsioon for-break

Sarnaselt while-tsüklile peatab lausend break itereerimisprotsessi täielikult ja murrab protsessi tsüklist välja. Joonis 9 kujutab for-break konstruktsiooni voodiagrammi.

Joonis 9: for-tsüklis oleva for-break konstruktsiooni voodiagramm. Kriipjoonega tähistatud tegevused on automatiseeritud.

Joonisel 9 kujutatud voodiagrammile võrdne olukord, kui lausend break peatab tsükli enneaegselt:

for n in [1, 2, 3]:
    if n == 3:
        break
    print(n)

1
2

Lausend break ei peatab tsüklit enneaegselt:

for n in [1, 2, 3]:
    if False:
        break
    print(n)

1
2
3

Näide: Pangaautomaat versioon 3.

raha_masinas = 3
raha_soov = int(input('Kui palju raha tahad?'))

for raha in range(1, raha_soov + 1):
    if raha > raha_masinas:
        print('Masinas sai raha otsa. Vabandame.')
        break
    print('1 euro')

print('Head aega.')

1 euro
1 euro
1 euro
Masinas sai raha otsa. Vabandame.
Head aega.

1.3.4   Konstruktsioon for-continue

Lausend continue töötab samal viisil nagu while-tsüklis. Lausend continue peatab hetkel teostatavat iteratsiooni ja alustab järgmise iteratsiooni tsükliga. Joonis 10 kujutab for-continue konstruktsiooni voodiagrammi.

Joonis 10: for-tsüklis oleva for-continue konstruktsiooni voodiagramm. Kriipjoonega tähistatud tegevused on automatiseeritud.

Joonisel 10 kujutatud voodiagrammile vastav olukord kus tingimuslause rahuldatakse:

for n in [1, 2, 3]:
    if n == 2:
        continue
    print('Juulius on eksamil põrunud', n, 'korda.')

Juulius on eksamil põrunud 1 korda.
Juulius on eksamil põrunud 3 korda.

Tingimuslause ei rahuldu:

for n in [1, 2, 3]:
    if False:
        continue
    print('Juulius on eksamil põrunud', n, 'korda.')

Juulius on eksamil põrunud 1 korda.
Juulius on eksamil põrunud 2 korda.
Juulius on eksamil põrunud 3 korda.

1.3.5   Konstruktsioon for-continue-break

Sarnaselt while tsüklile saame lausendeid continue ja break kasutada koos. Lausendite continue ja break kasutamine ühes tsüklis:

for i in range(10):
    if i <= 3:
        continue
    elif i > 6:
        break
    print(i)

4
5
6

1.3.6  Konstruktsioon for-else

Lausend else käitumine on sama mis while-tsüklis. Tegevus mis kaasneb lausendiga else teostatakse juhul kui kõik while-tsükli iteratsioonid on teostatud (tsükkel on ammendunud), st., et lausend break pole tsüklit enneaegselt lõpetanud. Joonised 11 ja 12 kujutavad for-else konstruktsiooni voodiagramme juhul kui tsüklis ei esine lausendit break ja kui see esineb.

Joonis 11: for-tsüklis oleva for-else konstruktsiooni voodiagramm. Kriipjoonega tähistatud tegevused on automatiseeritud.

Joonisega 11 võrdne olukord:

for n in [1, 2]:  # Lausend break puudub.
    print(n)
else:
    print('Tsükkel ammendus.')

1
2
Tsükkel ammendus.

Sama tulemuse annab kood:

for n in [1, 2]:  # Lausendid break ja else puuduvad.
    print(n)

print('Tsükkel ammendus.')

1
2
Tsükkel ammendus.

Joonis 12: for-tsüklis oleva for-break-else konstruktsiooni voodiagramm. Kriipjoonega tähistatud tegevused on automatiseeritud.

Joonisega 12 võrdne olukord kus tsükkel lõpetatakse enneaegselt:

for n in [1, 2, 3]:
    print(n)
    if n == 2:
        break  # Lõpetab tsükli enneaegselt.
else:
    print('Tsükkel ammendus? Ei.')

1
2

Kui tsükkel ammendub:

for n in [1, 2, 3]:
    print(n)
    if False:  # Tsükkel ammendub.
        break  
else:
    print('Tsükkel ammendus? Jah.')

1
2
3
Tsükkel ammendus? Jah.

Näide: Leia etteantud loendist esimene viiega jaguv arv, prindi see. Kui loendis puudub viiega jaguv arv prindi sellekohane teade (ainult üks kord) kasutades ühte for-tsüklit.

Vale lahendus võrdluseks:

numbrid = [1, 2, 3]
for number in numbrid:
    if number % 5 == 0:
        print(number)
        break
    else:
        print('[Vale] Arvu ei leitud.')  # Vale, prindib mitu korda.

[Vale] Arvu ei leitud.
[Vale] Arvu ei leitud.
[Vale] Arvu ei leitud.

Õige lahendus:

for number in numbrid:
    if number % 5 == 0:
        print(number)
        break
else:
    print('[Õige] Arvu ei leitud.')

[Õige] Arvu ei leitud.

Näide: Pangaautomaat versioon 4.

raha_masinas = 3
raha_soov = int(input('Kui palju raha tahad?'))

for raha in range(1, raha_soov + 1):
    if raha > raha_masinas:
        print('Masinas sai raha otsa. Vabandame.')
        break
    print('1 euro')
else:
    print('Head aega.')  # Pole ilus mõnitada.

1 euro
1 euro
1 euro
Masinas sai raha otsa. Vabandame.

1.3.7   Pesastatud for-tsükkel

for-tsükleid on võimalik üksteise sisse pesastada. Joonis 13 kujutab for-tsüklisse pesastatud for-tsükli voodiagrammi.

Joonis 13: for-tsüklisse pesastatud for-tsükkel. Kriipjoonega tähistatud tegevused on automatiseeritud. Pesastatud tsükkel on tähistatud rohelise ristkülikuga.

Joonisele 13 võrdne olukord:

for i in range(2):
    for j in range(3):
        print('i =', i,'\tj =', j)

i = 0 	j = 0
i = 0 	j = 1
i = 0 	j = 2
i = 1 	j = 0
i = 1 	j = 1
i = 1 	j = 2

Näide: Pakime lahti maatriksi read ja veerud.

mat = [[1, 2],
       [3, 4],
       [0]
      ]

for rida in mat:  # Prindime read.
    print(rida)
    
for rida in mat:
    for veerg in rida:    
        print(veerg)  # Veergudes ja ridades olevad arvud.

[1, 2]
[3, 4]
[0]
1
2
3
4
0

Näide: Nädal ja nädalapäevade tunnid 2.

päevad = ['E', 'L', 'P']
päeva_pikkus = 2  # Tundides.

for päev in päevad:
    print(päev)
    for tund in range(päeva_pikkus + 1):
        print(f'kell on {tund}.')

print('\nUus nädal.')

E
kell on 0.
kell on 1.
kell on 2.
L
kell on 0.
kell on 1.
kell on 2.
P
kell on 0.
kell on 1.
kell on 2.

Uus nädal.

Näide: Algarvude otsimine.

n_max = 11
for n in range(2, n_max + 1):
    for x in range(2, n):
        if n % x == 0:
            print(f'    {n} = {x} * {n // x}')
            break  # NB! Väljub pesastavasse tsüklisse.
    else:
        print('Arv', n, 'on ALGARV!')

Arv 2 on ALGARV!
Arv 3 on ALGARV!
    4 = 2 * 2
Arv 5 on ALGARV!
    6 = 2 * 3
Arv 7 on ALGARV!
    8 = 2 * 4
    9 = 3 * 3
    10 = 2 * 5
Arv 11 on ALGARV!

1.4  Funktsioonis olev tsükkel ja lausend return

Kui funktsiooni definitsioon sisaldab tsüklit või tsükleid ja funktsioon väljastab tulemusi tsükli seest kasutades lausendit return, siis lausend return peatab iteratsiooni ja väljub def-blokist (samas ka for või while-blokist). Seega selles kontekstis lausend return käitub justkui lausend break.

Näide: Funktsioon breaking_num itereerib 0-st, 10-ni (kaasaarvatult) ja murrab tsüklist välja peale num-dat iteratsiooni tsüklit.

def breaking_num(num):
    for i in range(11):
        if i != num:
            print('x', i)
        else:
            return  # Vaikimisi väljastatakse None.
            
breaking_num(3)

x 0
x 1
x 2

Sama käitumine kasutades lausendit break:

def breaking_num(num):
    for i in range(11):
        if i != num:
            print('x', i)
        else:
            break
    return None
            
breaking_num(3)

x 0
x 1
x 2

Näide: Funktsioon find_index leiab iteratiivselt sõnes esimesena esineva etteantud tähemärgi indeksi. Kui tähemärki ei leita väljastatakse sõne pikkus.

def find_index(word, letter):
    index = 0
    word_len = len(word)
    while index < word_len:
        if word[index] == letter:
            return index
        index = index + 1
    return word_len

print(find_index('Juulius', 'x'))  # Tähemärki ei leita.
print(find_index('Juulius', 'l'))

7
3

Sama käitumine kasutades lausendit break:

def find_index(word, letter):
    index = 0
    word_len = len(word)
    while index < word_len:
        if word[index] == letter:
            break
        index = index + 1
    return index

print(find_index('Juulius', 'x'))  # Tähemärki ei leita.
print(find_index('Juulius', 'l'))

7
3

2  Iteratsiooni ja rekursiooni võrdlus

Kõiki probleeme mida saab lahendada iteratiivselt saab lahendada ka rekursiivselt (vt. eelmise nädala loengu materjale). Rekursioon on teatud probleemide puhul elegantsem ja kompaktsema koodiga.

2.1  Iteratsioon

Ülevaade:

• Kasutab tsükleid for või while tegevuste kordamiseks.
• Seisundit hoitakse muutujates, mida uuendatakse igas iteratsioonis ehk tsüklisammus.
• Töötab konstantse mälumahuga (kui ei manipulaarita jadalaadsete andmetüüpidega nt. listid jt.).
• Üldiselt palju kiirem ja mälusäästlikum kui rekursioon.

2.2  Rekursiooni

Ülevaade:

• Funktsioon kutsub iseennast, et jagada probleem väiksemateks alamprobleemideks.
• Iga rekursiivne kutse loob uue pinuraami või virnaraami (stack frame), suurendades mälukasutust.
• Lihtsam kirjutada probleemide puhul, mis on loomu poolest rekursiivsed (nt. Fibonacci jada jne.).
• Üldiselt palju aeglasem kui iteratsioon.
• Protsess võib ületada Pythoni rekursioonilimiidi (vaikimisi umbes 3000).

2.3  Kiirus

Pythonis on rekursiivne lahend üldiselt palju aeglasem kui iteratiivne.

2.3.1  Rekursiivne algoritm

Demonstreerime seda eelmise nädala praktikumis tutvustatud Fibonacci jada liikmeid leidva rekursiivse funktsiooni abil. Leiame $40$-da jada liikme $F(40) = 102334155$:

%%time 
# Jupyteri maagiline käsk (line magic).

def fibonacci_rec(n):
    if n <= 2:
        return 1
    else:
        return fibonacci_rec(n - 2) + fibonacci_rec(n - 1)

fibonacci_rec(40)

CPU times: user 4.14 s, sys: 20 ms, total: 4.16 s
Wall time: 4.17 s

102334155

Üks rekursiivse skeemi väljakutse võttis umbes $4$ s.

2.3.2  Iteratiivne algoritm

Järgmises koodirakus on kasutatud iteratiivset algoritmi jadaliikme $F(40)$ leidmiseks. Iteratiivne lahend on nii kiire, et peame tegema mitu funktsiooni väljakutset ja keskmestama väljakutsele kulunud ajad. Taustal teostatakse $10 \cdot 100\,000 = 1\,000\,000$ väljakutset:

%%timeit -n 100_000 -r 10  
# Jupyteri maagiline käsk (line magic).

def fibonacci_iter(n):
    if n == 1 or n == 2:
        return 1
    a, b = 1, 1
    for _ in range(3, n + 1):  # Kui tead, et ei kasuta muutujat, nimetame _ või _i.
        a, b = b, a + b
    return b

fibonacci_iter(40)

531 ns ± 8.02 ns per loop (mean ± std. dev. of 10 runs, 100,000 loops each)

Natukene teistsugune iteratiivne algoritm:

%%timeit -n 100_000 -r 10

def fibonacci_iter(n):
    fib, prev = 1, 1
    for _ in range(n - 2):
        fib += prev
        prev = fib - prev
    return fib
    
fibonacci_iter(40)

762 ns ± 6.63 ns per loop (mean ± std. dev. of 10 runs, 100,000 loops each)

Kahe viimase koodiraku põhjal järeldame, et ühe iteratiivse $F(40)$ väljakutse kestus on umbes $500$ ns (konkreetsel arvutil mida õppejõud kasutas.) Seega kuna $4$ s $= 4\,000\,000\,000$ ns siis:

4e9 / 500

8000000.0

Tulemusest saame järeldame, et konkreetse näite puhul on iteratiivne skeem $8$ miljonit korda ($6$ suurusjärku) kiirem.

2.3.3  Sabarekursiivne algoritm

Parem skeem on nn. sabarekursiivne Fibonacci jadaliikmete algoritm. Sabarekursiooni mõistet uuri iseseisvalt: https://en.wikipedia.org/wiki/Recursion_(computer_science)#Tail-recursive_functions

%%timeit -n 100_000 -r 10

def fibonacci_tailrec(n, fib, prev):
    if n == 1:
        return prev
    return fibonacci_tailrec(n - 1, fib + prev, fib)
    
fibonacci_tailrec(40, 1, 1)

1.12 μs ± 21.1 ns per loop (mean ± std. dev. of 10 runs, 100,000 loops each)

Kiirus paranes tunduvalt. Üks väljakutse teostatakse umbes $1$ μs jooksul. Kuna $1$ μs = $1000$ ns siis:

4e9 / 1000

4000000.0

Tulemus on $4$ miljonit korda ($6$ suurusjärku) kiirem kui tavaline rekursioon. Võrreldes iteratsiooniga on saadud tulemus ikkagist $2$ korda (sama suurusjärk) aeglasem.

☻   ☻   ☻