ebSkola

7. tēma / 7.5

7.5 Iebūvēto funkciju efektivitāte

Stundas uzdevums: Tu proti rakstīt kārtošanas un meklēšanas algoritmus no nulles, kas palīdz saprast loģiku. 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. (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) - salīdzini sorted() ar savu bubble_sort · 2. uzdevums (~25 min) - izmēri 'in' sarakstā pret kopu · 3. uzdevums (~20 min) - izvēlies pareizo struktūru un pamato izvēli. Papildu uzdevumu sāc tikai tad, ja pārējie trīs ir gatavi.

Pirms sāc: atver VS Code un izveido failu strukturas.py. Noderēs 7.2 stundas bubble_sort funkcija - nokopē to blakus.

Teorija: Pareizā funkcija un pareizā datu struktūra

  • 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.
  • Datu struktūra ir svarīgāka par funkciju: 7.4 stundā redzēji, ka iebūvētā funkcija ir ātrāka par tavu ciklu, bet abas bija O(n). Šajā stundā mainām pašu datu glabāšanas veidu, un tas maina sarežģītības klasi.
    • x in saraksts - pārbauda elementus pēc kārtas, sarežģītība O(n).
    • x in kopa (set) - aprēķina elementa vietu uzreiz, sarežģītība O(1).
    • Miljonā elementu šī atšķirība ir nevis dažas reizes, bet tūkstošiem reižu.

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 -

Salīdzini sorted() ar savu bubble_sort

Beigās tu skaitļos redzēsi, cik lēna ir pašrakstīta kārtošana.

  1. Nokopē savu bubble_sort funkciju no 7.2 stundas.
  2. Izveido divus vienādus sarakstus ar 3000 elementiem apgrieztā secībā.
  3. Izmēri ar time.time(), cik ilgi strādā bubble_sort.
  4. Izmēri tāpat sorted(dati) laiku.
  5. Izdrukā abus laikus ar :.4f.
  6. Pieraksti, cik reižu ātrāks bija sorted().

Gatavs, kad: abi saraksti sakārtojas vienādi, bet sorted() to izdara daudzkārt ātrāk par tavu ciklu.

2. uzdevums -

Izmēri 'in' sarakstā pret kopu

Beigās tu redzēsi, ka datu struktūras maiņa maina ātrumu vairāk nekā funkcijas maiņa.

  1. Izveido sarakstu dati_saraksts = list(range(200000)).
  2. Izveido kopu dati_kopa = set(dati_saraksts).
  3. Izmēri laiku pārbaudei 199999 in dati_saraksts.
  4. Izmēri laiku pārbaudei 199999 in dati_kopa.
  5. Izdrukā abus laikus ar :.6f.
  6. Izrēķini, cik reižu kopa bija ātrāka.
  7. Pieraksti, kāpēc te vairs nepietiek teikt, ka abas ir O(n).

Gatavs, kad: kopa atbild gandrīz uzreiz, bet saraksts prasa manāmi ilgāk, un attiecība ir vismaz simtos reižu.

3. uzdevums -

Izvēlies pareizo struktūru un pamato izvēli

Beigās tu pratīsi izvēlēties struktūru pēc uzdevuma, nevis pēc ieraduma.

  1. Pieraksti trīs uzdevumus: TOP 5 rezultāti, spēlētāju vārdu pārbaude, spēlētāja profils.
  2. Izvēlies katram struktūru: saraksts, kopa vai vārdnīca.
  3. Pamato katru izvēli ar vienu teikumu.
  4. Pārbaudi kopu ar dublikātiem: pievieno vienu vārdu divreiz un izdrukā kopu.
  5. Pārbaudi, vai kopa saglabā pievienošanas secību.
  6. Izlabo savu izvēli, ja secība vai dublikāti to izjauc.
  7. Pieraksti vienu secinājumu: kāpēc TOP 5 sarakstam kopa neder.

Gatavs, kad: katram no trim uzdevumiem tev ir izvēlēta struktūra un viens teikums, kāpēc tieši tā.

Papildu uzdevums - Pārbaudi arī vārdnīcu

Ja pamatdarbs ir gatavs, izmēri arī atslēgas meklēšanu vārdnīcā.

  1. Izveido vārdnīcu ar 200 000 atslēgām, izmantojot {i: i for i in range(200000)}.
  2. Izmēri laiku pārbaudei 199999 in vardnica.
  3. Salīdzini to ar kopas un saraksta rezultātiem.
  4. Pieraksti, kura no trim struktūrām bija lēnākā.
  5. Pieraksti, ko vārdnīca dod papildus salīdzinājumā ar kopu.

Gatavs, kad: vārdnīcas un kopas laiki ir līdzīgi, bet abi krasi atšķiras no saraksta.

Koda piemērs (saraksts pret kopu - grūtākā daļa)

import time

# Grūtākā doma šajā stundā: ātrumu var uzlabot, NEMAINOT algoritmu,
# bet nomainot datu struktūru, kurā dati glabājas.

n = 200000
dati_saraksts = list(range(n))
dati_kopa = set(dati_saraksts)     # tie paši dati, cita struktūra

mekletais = n - 1                  # sliktākais gadījums: pats pēdējais

sakums = time.time()
atrasts_sarakstā = mekletais in dati_saraksts     # O(n) - iet pēc kārtas
laiks_saraksts = time.time() - sakums

sakums = time.time()
atrasts_kopā = mekletais in dati_kopa             # O(1) - aprēķina vietu uzreiz
laiks_kopa = time.time() - sakums

print(f"Sarakstā: {atrasts_sarakstā}  ({laiks_saraksts:.6f} s)")
print(f"Kopā:     {atrasts_kopā}  ({laiks_kopa:.6f} s)")
print(f"Kopa ir ~{laiks_saraksts / laiks_kopa:.0f}x ātrāka")
Abas pārbaudes atgriež True, bet kopa atbild gandrīz uzreiz, kamēr saraksts pārstaigā visus 200 000 elementus. Uzmanies: kopa neglabā secību un nepieļauj dublikātus, tāpēc tā neder visur - piemēram, TOP 5 sarakstam tā nederēs.