ebSkola

7. tēma / 7.4

7.4 Iebūvēto funkciju ātrums

Stundas uzdevums: Salīdzini paša rakstītus meklēšanas un kārtošanas algoritmus ar Python iebūvētajām funkcijām un noskaidro, 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.

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

70 min plāns: Teorija un paraugs (~10 min) · 1. uzdevums (~15 min) - atrodi min un max ar iebūvētajām funkcijām · 2. uzdevums (~25 min) - salīdzini iebūvēto sum() ar savu ciklu · 3. uzdevums (~20 min) - izmēri abus ar time un izdari secinājumu. Papildu uzdevumu sāc tikai tad, ja pārējie trīs ir gatavi.

Pirms sāc: atver VS Code un izveido failu iebuvetas_funkcijas.py. Šajā stundā salīdzināsi savu kodu ar Python gatavajām funkcijām.

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 Python valodā. Tās ir ieprogrammētas "C" valodā, kas atrodas daudz tuvāk datora dzelžiem. Tāpēc tās darbojas ievērojami ātrāk.
  • min() un max():
    • Dators tik un tā iziet cauri visam sarakstam, tātad sarežģītība ir O(n) (Lineāra).
    • Atšķirība ir tajā, ka šis O(n) cikls izpildās "C" valodas līmenī, nevis Python interpretatorā.
  • sorted() un Timsort:
    • Python neizmanto lēno burbuļkārtošanu (O(n²)).
    • Tas izmanto hibrīd-algoritmu 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 (nestandarta) spēles loģika.

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

Atrodi min un max ar iebūvētajām funkcijām

Beigās viena rinda aizstās veselu ciklu.

  1. Izveido sarakstu ienaidnieku_hp ar 10 dažādām vērtībām.
  2. Ieraksti vajakais = min(ienaidnieku_hp).
  3. Ieraksti stiprakais = max(ienaidnieku_hp).
  4. Izdrukā abas vērtības ar f-string.
  5. Uzraksti pats ciklu, kas atrod mazāko vērtību bez min().
  6. Salīdzini sava cikla rezultātu ar min() rezultātu.

Gatavs, kad: tavs cikls un min() dod vienu un to pašu skaitli.

2. uzdevums -

Salīdzini iebūvēto sum() ar savu ciklu

Beigās tu redzēsi, ka abi dara vienu darbu, bet ne vienādi ātri.

  1. Izveido sarakstu ar 1 000 000 skaitļiem, izmantojot list(range(1000000)).
  2. Uzraksti funkciju, kas saskaita visu ar for ciklu.
  3. Uzraksti otru funkciju, kas izmanto sum(dati).
  4. Izsauc abas un pārliecinies, ka rezultāts ir vienāds.
  5. Pieraksti, cik rindu garas ir abas funkcijas.
  6. Pieraksti, kura ir vieglāk salasāma.

Gatavs, kad: abas funkcijas dod vienādu summu, bet sum() variants ir īsāks.

3. uzdevums -

Izmēri abus ar time un izdari secinājumu

Beigās tev būs skaitļos pierādīts, kura versija ir ātrāka.

  1. Ieraksti import time.
  2. Izmēri sava cikla laiku ar time.time() pirms un pēc.
  3. Izmēri tāpat sum() laiku.
  4. Izdrukā abus laikus ar :.4f formatējumu.
  5. Izrēķini, cik reižu ātrāka bija iebūvētā funkcija.
  6. Palaid mērījumu vēlreiz un pārbaudi, vai attiecība ir līdzīga.
  7. Pieraksti vienu secinājumu: kāpēc abas ir O(n), bet viena tomēr ātrāka.

Gatavs, kad: abi rezultāti ir vienādi, bet sum() ir vairākas reizes ātrāks, un tu vari paskaidrot, kāpēc.

Papildu uzdevums - Pārbaudi arī len() un sorted()

Ja pamatdarbs ir gatavs, izmēri vēl divas iebūvētās funkcijas.

  1. Izmēri len(dati) izpildes laiku.
  2. Uzraksti pats ciklu, kas saskaita elementus, un izmēri to.
  3. Pieraksti, kura sarežģītība ir len() - O(1) vai O(n).
  4. Izmēri sorted(dati) uz 10 000 elementiem.
  5. Pieraksti abus rezultātus blakus.

Gatavs, kad: tu vari pateikt, ka len() ir O(1), bet tavs skaitīšanas cikls - O(n).

Koda piemērs (pašrakstīts cikls pret iebūvēto - grūtākā daļa)

import time

# Grūtākā doma: ABAS versijas ir O(n) - tās izdara vienādi daudz soļu.
# Tomēr iebūvētā ir vairākas reizes ātrāka, jo tās cikls izpildās
# C valodas līmenī, nevis caur Python interpretatoru.

lieli_dati = list(range(5000000))

# 1. Pašrakstīts cikls
sakums = time.time()
lielakais_savs = lieli_dati[0]
for skaitlis in lieli_dati:
    if skaitlis > lielakais_savs:
        lielakais_savs = skaitlis
laiks_savs = time.time() - sakums

# 2. Iebūvētā funkcija
sakums = time.time()
lielakais_ieb = max(lieli_dati)
laiks_ieb = time.time() - sakums

print(f"Pašrakstīts: {lielakais_savs}  ({laiks_savs:.4f} s)")
print(f"Iebūvētais:  {lielakais_ieb}  ({laiks_ieb:.4f} s)")
print(f"Iebūvētā funkcija ir ~{laiks_savs / laiks_ieb:.1f}x ātrāka")
Abas versijas atrod vienu un to pašu skaitli, bet max() ir vairākas reizes ātrāka. Tas ir labs piemērs tam, ka vienāda Big O sarežģītība vēl nenozīmē vienādu izpildes ātrumu.