Kvadratni algoritem v evidenci prisotnosti
Učenec analizira evidenco prisotnosti na šolskih delavnicah. Datoteka vsebuje 25.000 zapisov v obliki »ime;datum;delavnica«. Napisal je program, ki naj bi poiskal podvojene zapise in izračunal odstotek udeležencev z vsaj enim podvojenim zapisom. Jedro programa:
podvojeni = 0
for i in range(len(zapisi)):
for j in range(len(zapisi)):
if i != j and zapisi[i] == zapisi[j]:
podvojeni = podvojeni + 1
odstotek = (podvojeni // len(zapisi)) * 100
print('Podvojenih:', podvojeni, 'Odstotek:', odstotek)
Program se pri 2.500 zapisih izvede v 0,8 s, pri 10.000 zapisih pa v 12 s. Na končni datoteki se izvaja že več kot minuto, rezultat pa je vedno »Odstotek: 0«. Učenec sumi, da je kriv počasen računalnik, in predlaga nakup novega. Mentor zahteva, da najprej utemelji svojo trditev z meritvami in šele nato predlaga spremembe. Učenec podatke bere iz besedilne datoteke, kjer je vsak zapis v svoji vrstici, in jih shrani v seznam nizov; na voljo ima šolski prenosnik z 8 GB RAM.
1. Preveri, ali so meritve skladne s kvadratno časovno zahtevnostjo. Izračunaj pričakovani čas pri 25.000 zapisih in presodi učenčevo razlago, da je kriv počasen računalnik.
Read the worked answer
Preverjanje rasti
Pri kvadratni zahtevnosti velja T(n) = c · n², zato razmerje časov ustreza kvadratu razmerja velikosti vhoda.
- 10.000 / 2.500 = 4 → pričakovano razmerje 4² = 16 → 0,8 s · 16 = 12,8 s. Izmerjenih 12 s se ujema v okviru napake merjenja (predpomnilnik, sistemska obremenitev).
- Če bi bila rast linearna, bi pričakovali 3,2 s – izmerjenih 12 s linearno hipotezo jasno ovrže.
- 25.000 / 10.000 = 2,5 → pričakovano razmerje 6,25 → 12 s · 6,25 = 75 s, kar ustreza opažanju »več kot minuto«.
Sklep o strojni opremi
Meritve kažejo, da čas raste s kvadratom velikosti vhoda, torej je ozko grlo algoritem, ne strojna oprema. Računalnik, ki bi bil 10-krat hitrejši, bi pri 25.000 zapisih potreboval okoli 7,5 s, pri 100.000 zapisih pa okoli dve minuti – težava bi se le odložila. Nakup novega računalnika zato ni utemeljen; utemeljena je sprememba algoritma.
Pomembno je tudi, da meritve niso bile narejene na končni datoteki; sklepanje o 25.000 zapisih je ekstrapolacija modela, ki pa je podprta z dvema neodvisnima meritvama.
2. V jedru programa sta vsaj dva logična hrošča. Poišči ju, pojasni posledice in zapiši popravljeno različico, ki izračuna odstotek zapisov (ne parov), ki imajo vsaj en podvojen zapis.
Read the worked answer
Hrošč 1 – dvojno štetje in napačna enota Zanka šteje pare: za vsak par enakih zapisov se števec poveča dvakrat (enkrat pri (i, j) in enkrat pri (j, i)). Rezultat zato ni število zapisov, ampak dvakratnik števila parov, in lahko doseže n·(n−1). Posledično bi lahko »odstotek« presegel 100 %, kar je nesmisel.
Hrošč 2 – celoštevilsko deljenje
Operator // vrne celi del količnika. Ker je število podvojenih zapisov vedno manjše od števila vseh zapisov, je količnik 0, zato je izpis vedno »Odstotek: 0«, ne glede na podatke. To je videti kot napaka v podatkih, v resnici pa je napaka v izrazu.
Popravljena različica
from collections import Counter
stevci = Counter(zapisi)
z_dvojnikom = sum(1 for z in zapisi if stevci[z] > 1)
odstotek = z_dvojnikom / len(zapisi) * 100
print('Zapisov s podvojitvijo:', z_dvojnikom, 'Odstotek:', round(odstotek, 1))
Zdaj je števec definiran na ravni zapisa (koliko zapisov ima vsaj eno podvojitev), deljenje pa je realno. Če je zapis podvojen trikrat, se šteje enkrat – kar ustreza zastavljenemu vprašanju.
3. Predlagaj algoritem s časovno zahtevnostjo O(n) ali O(n log n) in ga utemelji. Primerjaj ga z obstoječim glede na čas in pomnilnik pri 25.000 zapisih.
Read the worked answer
Predlog s slovarjem (štetjem pojavitev)
stevci = {}
for z in zapisi:
stevci[z] = stevci.get(z, 0) + 1
z_dvojnikom = 0
for z in zapisi:
if stevci[z] > 1:
z_dvojnikom += 1
Vsak zapis obiščemo dvakrat, vsak vnos v slovar in vsako iskanje je v povprečju O(1) → skupaj O(n). Pri 25.000 zapisih to pomeni nekaj deset tisoč operacij namesto približno 625 milijonov primerjav v dvojni zanki.
Pomnilnik: slovar hrani le različne zapise, pri 25.000 zapisih nekaj megabajtov – na prenosniku z 8 GB RAM zanemarljivo. To je pravo razmerje: zamenjamo malo pomnilnika za ogromno časa.
Alternativa z razvrščanjem: zapise razvrstimo in nato v enem prehodu štejemo zaporedne enake – O(n log n) časa, O(1) dodatnega pomnilnika (če razvrščamo na mestu). Počasnejša od slovarja, a brez dodatne porabe pomnilnika.
Omejitve: slovar zahteva, da so zapisi enaki po nizu (pozor na presledke in velike začetnice – smiselno je najprej normalizirati zapis). V najslabšem primeru (slab razprševalnik) je iskanje O(n), a v praksi se to ne zgodi. Če so podatki v relacijski bazi, enak rezultat dobimo s GROUP BY in HAVING COUNT(*) > 1, kar je še bolj ustrezno, ker se delo prenese na strežnik.