Funkcije za delo z vektorji

Testi

Testi: testi-funkcije-za-delo-z-vektorji.py

Naloga

V tokratni domači nalogi bomo sprogramirali nekaj reči, ki jih bomo pri predavanjih še večkrat uporabili kot primer. Delali bomo z vektorji, predstavili pa jih bomo predstavili kar s seznami. Kjer torej spoda pišemo "vektor" ... si lahko predstavljate, da smo v resnici hoteli reči kar seznam.

• zero(n) vrne n-dimenzionalni vektor 0 (torej: seznam, ki vsebuje n ničel);
• vector(s) vrne kopijo podanega vektorja s (pazite: ne istega, temveč enakega);
• add(a, b) vrne vsoto vektorjev a in b; vsota vektorjev [1, 2] in [4, 5] je [5, 7];
• iadd(a, b) k vektorju a prišteje vektor b;
• sub(a, b) vrne razliko vektorjev a in b (torej a-b);
• isub(a, b) od vektorja a odšteje vektor b;
• mul(a, k) vrne produkt vektorja a s skalarjem (torej: številom) k; mul([5, 7], 2) mora vrniti [10, 14];
• imul(a, k) pomnoži vektor a s skalarjem k
• inner(a, b) izračuna skalarni produkt vektorjev a in b; inner([2, 5, 3, 1], [2, 1, 1, 4]) vrne 16;
• euclid(a, b) vrne evklidsko razdaljo med a in b;
• median(s) dobi kot argument seznam vektorjev in kot rezultat vrne tistega (istega, ne enakega!), katerega poprečna razdalja do vseh ostalih vektorjev je najmanjša.

Le zadnja funkcija zahteva nekaj razlage: s je seznam vektorjev, torej seznam seznamov. Za vsak vektor izračunajte poprečno razdaljo do vseh drugih (ali, če želite, vseh, vključno z njim samim, saj to ničesar ne spremeni). Funkcija naj vrne tisti (isti, ne samo enak!) vektor, pri katerem je ta razdalja najmanjša.

Razlika med funkcijami, ki se začnejo z i in tistimi, ki se ne (iadd, isub in imul v primerjavi z add, sub in mul) je v tem, da prve spreminjajo vektor, ki so ga dobile kot argument, druge pa pustijo ta vektor pri miru in izračunajo rezultat v nov vektor.

Če vektorja nista enako dolga, naj se funkcije obnašajo tako, kot da bi imel krajši na koncu še toliko ničel, da bi bil enak daljšemu. sub([5, 8], [3, 4, 5]) naj vrne [2, 4, -5].

Naloga je videti zelo dolga, v resnici pa bi zaresen programer vse funkcije naredil v eni vrstici (poleg glave funkcije) brez kakih posebnih grdobij. Z vašim znanjem bodo zahtevale po kake tri vrstice. Tole je torej naloga za sproščanje po kolokviju iz Diskretnih struktur. ;)

Rešitev

Naloga je bila zanimiva, saj je od vas zahtevala dvoje: razumeti, kar ste slišali na zadnjih predavanjih, poleg tega pa ste se morali nekoliko igrati s seznami. Z njimi se poznamo že dva meseca, uporabljate jih na približno vsakih vajah in pri približno vsaki domači nalogi, zato je bilo zanimivo videti, koliko spretnosti ste si nabrali pri delu z njimi.

Ob predavanjih in nalogi imam nekoliko slab priokus: morda ste dobili vtis, da je potrebno pri programiranju - tako v Pythonu kot v drugih jezikih - pogosto razmišljati o istosti in enakosti. Pa ni tako, te stvari običajno tečejo nekako naravno, ne da bi izgubljali čas in misli zanje. Ta predavanja in ta naloga sta te reči le izpostavila na nekaj kritičnih primerih.

zero in vector

O njima ni vredno izgubljati besed.

def zero(n): return [0]*n def vector(f): return f[:]

add

Tisto, kar ste morali vedeti iz zadnjih predavanj, je, da ne smete spremeniti a-ja. Če ga spreminjate, ga morate popraviti nazaj ... vendar ga je lažje skopirati in potem spreminjati kopijo. Kopirati pa je potrebno znati. To pa znamo že od prvih predavanj in tudi na zadnjih smo se spomnili, da s t[:] naredimo kopijo seznama t. Tako pridemo do naslednje funkcije:

def add(a, b): aa = a[:] bb = b[:] if len(a) < len(b): aa += [0]*(len(b)-len(a)) elif len(b) < len(a): bb += [0]*(len(a)-len(b)) v = [] for i in range(len(aa)): v.append(aa[i]+bb[i]) return v

aa in bb sta kopiji originalnih a in b, zato jima smemo brez bojazni dodati toliko ničel, da bosta enako dolga. Nato sestavimo nov prazen seznam in vanj dodamo vsoto njunih elementov.

Takšna rešitev je sicer pravilna, a grda na sto in eni način. Za začetek se lahko znebimo onih nesrečnih ifov, če vemo za lepo lastnost množenja seznamo: če seznam pomnožimo z negativnim številom, dobimo prazen seznam: [0]* -3 ne vrne seznama z "minus tremi ničlami" temveč prazen seznam.

def add(a, b): aa = a[:] + [0]*(len(b)-len(a)) bb = b[:] + [0]*(len(a)-len(b)) v = [] for i in range(len(aa)): v.append(aa[i]+bb[i]) return v

Tako, se že počutim veliko boljše. Če sta seznama enako dolga, je len(a)-len(b) enako 0 in nikomur ne bomo dodali ničesar. Če sta različnih dolžin, bomo krajšemu dodali prazen seznam (se pravi ničesar), drugemu pa toliko ničel, kolikor je treba.

Naslednje, kar žali moj estetski čut, je range(len(aa)); tega se znebim, če se le da. Že na prvih predavanjih smo opazili funkcijo zip, ki združi elemente dveh (ali več) seznamov v pare (ali večterke). Zdaj je pravi trenutek, da jo uporabimo.

def add(a, b): aa = a[:] + [0]*(len(b)-len(a)) bb = b[:] + [0]*(len(a)-len(b)) v = [] for e, f in zip(aa, bb): v.append(e+f) return v

Prav. Zdaj pa bi se rad znebil kopiranja in spreminjanja. Tisto prištevanje ničel ni posebej elegantno. Naredimo lahko tole: zanko spustimo tako daleč, kolikor je dolg daljši od seznamov. Preden rečemo v.append(a[i]+b[i]) pa preverimo, da nismo prišli že čez rob kakega seznama in v tem primeru le prepišemo element daljšega izmed njiju.

def add(a, b): v = [] for i in range(max(len(a), len(b))): if i >= len(a): v.append(b[i]) elif i >= len(b): v.append(a[i]) else: v.append(a[i]+b[i]) return v

Za tole ne bi mogli reči, da je kaj elegantneje od kopiranja. Hecnejša izvedba taistega je takšna.

def add(a, b): v = [] for i in range(max(len(a), len(b))): v.append((i < len(a) and a[i]) + (i < len(b) and b[i])) return v

Za tole morda zaslužim kako točko za domiselnost, a nič za eleganco. Vendar smo na pravi poti. Spomniti se moramo, da lahko zipu podamo seznama različnih dolžin in bo šel toliko daleč, kolikor je dolg krajši. Toliko elementov bomo sešteli, na konec pa pripeli rep daljšega seznama. Uporabimo še trik z rezinami: če ima seznam samo tri elemente in zahtevamo vse od petega naprej, to ne sproži napake, temveč vrne prazen seznam.

def add(a, b): v = [] for e, f in zip(a, b): v.append(e+f) v += a[len(b):] + b[len(a):] return v

V zadnji vrstici pred returnom se lahko zgodi troje. Če sta seznama enako dolga, je a[len(b):] isto kot a[len(a):], torej zahtevamo vse elemente od "enega za zadnjim" in dobili bomo prazen seznam. Dvakrat. K vju torej tedaj ne prištejemo nič (v += [] + []) in prav je tako. Zdaj pa recimo, da je a krajši; naj ima a, recimo, tri elemente, b pa pet. Tedaj zadnja vrstica pomeni v += a[5:] + b[3:]. Seznam a ima samo tri elemente in če hočemo vse od petega naprej, dobimo prazen seznam. Seznam b jih ima pet in če hočemo vse od tretjega, bomo dobili prav tiste, ki štrlijo prek aja. Tretja možnost je, da je krajši b; ta je obratna kot druga in seveda je spet vse prav.

Vse, kar smo našteli doslej, smo se učili na prvih predavanjih. Krajšo rešitev se bomo učili, najbrž, na zadnjih decembrskih predavanjih in je takšna:

def add(a, b): return [e+f for e, f in zip(a, b)] + a[len(b):] + b[len(a):]

iadd

Z iadd je ravno obratno kot z add: tu moramo spreminjati a. Čim kjerkoli napišemo a = nekaj, smo ga polomili. Potrebno je spremeniti seznam, ki ga imenujemo a, ne pa aju prirediti nek nov seznam.

Ubadanje z ničlami je podobno kot pri add, zato ne bomo še enkrat ponavljali pravkar povedanega. Poglejmo le preprosto kolikor toliko elegantne rešitve:

def iadd(a, b): for i in range(min(len(a), len(b))): a[i] += b[i] a += b[len(a):]

V zanki gremo toliko daleč, kolikor je dolg krajši od vektorjev, in seštevamo. Nato k aju dodamo še toliko elementov, kolikor je b daljši - se pravi vse elemente bja od zadnjega elementa aja naprej. Če je b slučajno krajši, pa zadnja vrstica ne bo naredila ničesar.

Ker se hočem vedno znebiti range-lena (že imam svoje razloge za to, vendar o njih še ne morem govoriti), raje uporabim enumerate, ki seznam elementov spremeni v seznam parov indeks-element.

def iadd(a, b): for i, e in enumerate(b[:len(a)]): a[i] += e a += b[len(a):]

Sicer pa smo ljudje lena bitja in funkcijo iadd najraje sprogramiramo tako, da v a zapišemo tisto, kar vrne funkcija add(a, b).

def iadd(a, b): a[:] = add(a, b)

sub in mul

Pustimo; sub gre po istem vzorcu kot add, mul pa je trivialna.

inner

Študentskih rešitev še nisem gledal, a če je kdo tudi v funkciji inner telovadil z ničlami, se bom hahljal. Čemu? No, z velikimi mukamu dodajati ničle samo za to, da boš potem množil z njimi je pač nekoliko hecno, ni?

def inner(a, b): prod = 0 for e, f in zip(a, b): prod += e*f return prod

Če vemo, česar še ne vemo, pa napišemo kar

def inner(a, b): return sum(e*f for e, f in zip(a, b))

euclid

Trivialno, vendar bom vseeno objavil, ker vem, da je večina komplicirala brez potrebe.

from math import sqrt def euclid(a, b): diff = sub(a, b) return sqrt(inner(diff, diff))

Zakaj pa mislite, da ste morali programirati skalarni produkt? ;)

median

Mediana pa je le preprosta vaja iz dvojnih zank in iskanja največjega elementa. Večina programov, ki sem jih videl, je delovala tako, da se je začela z neko izmišljeno, zelo veliko razdaljo, od katere je bila manjša že prva naslednja razdalja. To je sprejemljivo, v praksi pa se temu, če nismo res res res prepričani, da je številka dovolj velika, raje izognemo. Tule je lepša rešitev.

def median(s): med = None for x in s: dist = 0 for y in s: dist += euclid(x, y) if med is None or dist < bestDist: med, bestDist = x, dist return med

Ob pogoju if med is None or dist < bestDist je nemara koga zaskrbelo, da takrat, ko pridemo do njega prvič, bestDist še ni definiran. Nič ne de, nič ne de: takrat je med zagotovo enak None in Python drugega pogoja, tistega, v katerem nastopa bestDist, sploh ne bo gledal. Tole je povsem varno.