Henrik Lončar

Za reševanje te domače naloge uporabljajte numpy. Vsaka funkcija naj bi imela samo eno vrstico z return-om, ki vrne ustrezno filtrirano, indeksirano, prešteto ali karkoli že tabelo. Samo pri naj_dogajanje bo morda praktično, če boste dodali še eno vrstico.

Da ste rešili, kot je mišljeno, boste prepoznali po tem, da ne bo v programu nobenih zank, generatorjev, izpeljanih seznamov. Da ne zapletam testov, ti tega ne bodo preverjali in če bo kdo rešil kako drugače, bo tudi ta rešitev sprejeta kot pravilna. Vseeno pa zelo priporočam, da se potrudite: gre za uvodne naloge iz numpyja in dobro je, da to obvladate, preden pridejo na vrsto zahtevnejše.


Nalogi sta priloženi dve datoteki.

Za nalogo nepomembne opombe. ker sem podatke nabral avtomatsko vsebujejo napake - kadar, na primer, osebo pokličejo po priimku, je težko avtomatsko razbrati, za koga gre. Če bom te podatke uporabljal tudi v prihodnih nalogah, jih bom morda izboljševal.

Nekatere osebe so zapisane z imeni, druge s priimki, saj je bralcem včasih bolj znano eno, včasih drugo (najbrž nihče ne ve, komu je bilo ime Gerrick...). Osebe, ki so predstavljene z imeni in ne priimki, so:

["Harry", "Hermione", "Ron", "Ginny", "Fred", "George", "Arthur", "Molly", "Bill", "Fleur",
 "Cedric", "Cho", "Dean", "Dudley", "Draco", "Charlie", "Katie", "Kendra", "Kingsley",
 "Luna", "Neville", "Oliver", "Sirius", "Xenophilius", "James", "Lily", "Petunia", "Vernon",
 "Lucius", "Louis", "Isla", "Roxanne", "Burke", "Cygnus", "Beadle", "Sirius", "Phineas",
 "Alecto", "Scorpius", "Gwenog", "Beatrix",  "Lucius", "Ariana", "Narcissa", "Angelina",
 "Ignotus", "Percy"]

Priprava podatkov

Napiši program (ne funkcije!), ki preberi datoteki in pripravi numpyjeve tabele poglavja, osebe in omembe. Tabele vsebujejo podatke iz stolpcev datoteke "occurences.txt", pri čemer sta poglavje in omembe pretvorjene v int. Od poglavje odštejte 1, da bo imelo prvo poglavje številko 0.

Poleg tega preberi vsebino datoteke "chapters.txt" v tabelo naslovi.

Testi bodo preverjali, ali obstajajo spremenljivke s temi imeni in vsebujejo (del tega), kar morajo.

import numpy as np

naslovi = np.genfromtxt("chapters.txt", delimiter="XXX", dtype=str)
podatki = np.genfromtxt("mentions.txt", delimiter=",", dtype=str)

poglavja, osebe, omembe = podatki.T
poglavja = poglavja.astype(int) - 1
omembe = omembe.astype(int)

Obvezna naloga

Napiši naslednje funkcije:

Rešitev

Prvi dve funkciji sta očitno podobni. Obe zahtevata, da se spomnimo, kako dobiti indeks največjega elementa argmax. Tako dobimo indeks z največjim številom omemb, potem pa poiščemo pripadajoče ime osebe oziroma pripadajoče ime poglavja. Ime poglavja dobimo tako, da najprej izvemo njegov indeks, nato pa gremo s tem indeksom pogledati v seznam naslovov poglavij.

def naj_oseba():
    return osebe[np.argmax(omembe)]
def naj_dogajanje():
    i = np.argmax(omembe)
    return naslovi[poglavja[i]], osebe[i]
def prva_omemba(oseba):
    return naslovi[np.min(poglavja[osebe == oseba])]

Preostale štiri funkcije zahtevajo masko, s katero dobimo vse elemente, ki se nanašajo na podano osebo, osebe == oseba. Ker vsako osebo v vsakem poglavju štejemo le enkrat, nam bo np.sum(osebe == oseba) povedal število poglavij s to osebo, poglavje[osebe == oseba] indekse teh poglavij, iz indeksov pa dobimo njihove naslove, če gremo pogledat v naslovi. Četrta funkcija v omembe pogleda vse števce omemb te osebe in jih z np.sum sešteje.

def koliko_poglavij(oseba):
    return np.sum(osebe == oseba)
def v_poglavjih_st(oseba):
    return poglavja[osebe == oseba]
def v_poglavjih(oseba):
    return naslovi[poglavja[osebe == oseba]]
def vseh_omemb(oseba):
    return np.sum(omembe[osebe == oseba])

Dodatna naloga

Rešitev

Ta je bolj zafrknjena. Ni kar tako, za hec, dodatna.

Če mora funkcija vrniti masko poglavij, bo potrebno pripraviti tabelo s toliko elementi, kolikor je poglavij. Vsi elementi bodo False. Kot smo se naučili v obvezni nalogi, s poglavja[osebe == oseba] izvemo indekse poglavij, v katerih se pojavlja podana oseba. Te elemente maske postavimo na True. Pa jo imamo, masko.

def maska_poglavij(oseba):
    a = np.zeros(np.max(poglavja) + 1, dtype=bool)
    a[poglavja[osebe == oseba]] = True
    return a

Podobnost je potem preprosta. Sestavimo obe maski. Z & sestavimo masko, ki vsebuje True na mestih, na katerih sta obe maski enaki True; to so poglavja, v katerih se pojavljata obe osebi. Z | dobimo masko, ki ima True-je tam, kjer je True vsaj ena od mask. To so poglavja, kjer se pojavi vsaj ena od oseb. Preštejemo True-je v obeh sestavljenih maskah in ju delimo.

def podobnost(oseba1, oseba2):
    maska1 = maska_poglavij(oseba1)
    maska2 = maska_poglavij(oseba2)
    return np.sum(maska1 & maska2) / np.sum(maska1 | maska2)

Nekateri študenti so odkrili, da gre tudi brez mask - z numpy-jevimi funkcijami np.intersect1d in np.union1d. Če imamo

poglavja_crabbe = v_poglavjih_st("Crabbe")
poglavja_ron = v_poglavjih_st("Ron")

lahko z np.intersect1d in np.union1d dobimo številke poglavjih, v katerih se omenjata oba oz. vsaj eden.

np.intersect1d(poglavja_crabbe, poglavja_ron)
array([ 6,  8, 10, 11, 14, 17, 20, 23, 29])
np.union1d(poglavja_crabbe, poglavja_ron)
array([ 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
       20, 21, 23, 24, 25, 26, 27, 28, 29])

Deliti je potrebno velikosti teh dveh tabel.

def podobnost(oseba1, oseba2):
    poglavja1 = v_poglavjih_st(oseba1)
    poglavja2 = v_poglavjih_st(oseba2)
    return len(np.intersect1d(poglavja1, poglavja2)) / len(np.union1d(poglavja1, poglavja2))

V Pythonu bodo izkušeni programerji za isto (dovolj kratko) reč tipično napisali praktično enake funkcije. V problemih, ki jih rešujemo z numpy-jem ni tako. Malo zaradi njihove narave, malo zato, ker je numpy ogromen. Pri sestavljanju te naloge sploh nisem pomislil na rešitev s tema funkcijama, pa tudi za funkciji sem komaj vedel (= tako kot za besedo v tujem jeziku, katere pomen poznaš, nikoli pa ti ne bi priplavala v zavest, da bi jo sam uporabil).

Sam bi vseeno uporabil rešitev z maskami. Tidve funckciji zahtevata urejanje elementov tabele; čeprav to storita interno, se urejanju poskušam izogibati, ker je časovno zahtevnejše od sestavljanja mask. Po drugi strani pa maske vzamejo več pomnilnika. Vsaka različica ima svoje prednosti.