Glasbena lestvica

Namen naloge je bil pokazati, kako uporabni so slovarji -- v primerjavi s seznami. No, ni čisto uspelo. Ko sem sestavljal nalogo, mi je bilo očitno, da se to rešuje s slovarji (ker bi to v resnici delali tako). Ko sem ob pisanju rešitve poskusil isto sprogramirati še s seznami, pa se zdi, da je celo preprosteje. (V resnici ni, vendar le, če so spiski res veliki.)

Nalogo bomo tule najprej rešili s slovarji, nato pa še s seznami.

---

V domači nalogi bomo šteli, kolikokrat je nekdo poslušal katero pesem.

Testi

testi-glasbena-lestvica.py

Obvezni del

Napiši naslednje funkcije.

• prazen_spisek() vrne prazen spisek. Kaj vrne funkcija, je prepuščeno tebi. Vrne lahko seznam, slovar, niz, None ... ali celo številko, če se ti zdi to pametno. (Namig: ni. ;) Vrni kaj, kar ti bo prišlo prav v naslednjih funkcijah.

• poslusam(spisek, pesem) na podani spisek na nek način (pač odvisen od tega, kaj spisek je) doda pesem s podanim naslovom.

• predvajanj(spisek, pesem) pove, kolikokrat je "lastnik" spiska spisek poslušal podano pesem. Če pesmi še ni poslušal, funkcija seveda vrne 0.

Recimo, da storimo tole.

nov_spisek = prazen_spisek()
poslusam(nov_spisek, "Yesterday")
poslusam(nov_spisek, "Tomorrow")
poslusam(nov_spisek, "Yesterday")
poslusam(nov_spisek, "Yesterday")

Po tem bi klic predvajanj(nov_spisek, "Yesterday") vrnila 3, klic predvajanj(nov_spisek, "Tomorrow") bi vrnila 1 in klic predvajanja(nov_spisek, "Today") bi vrnila 0.

• vseh_pesmi(spisek) vrne število različnih pesmi na spisku.
• vseh_predvajanj(spisek) vrne število vseh predvajanj.
• najbolj_priljubljena(spisek) vrne naslov največkrat predvajane pesmi. Če je spisek prazen, funkcija vrne None.

Po gornjem bi klic vseh_pesmi(nov_spisek) vrnil 2, vseh_predvajanj(nov_spisek) bi vrnil 4 in najbolj_priljubljena(nov_spisek) bi vrnil "Yesterday".

V naslednjih nekaj funkcijah bomo predpostavili, da imamo dva spiska.

• stevilo_skupnih(spisek1, spisek2) vrne število pesmi, ki se pojavijo na obeh spiskih.
• velikost_repertoarja(spisek1, spisek2) vrne število pesmi, ki se pojavijo na enem ali drugem (ali obeh) spiskih.
• podobnost(spisek1, spisek2) vrne podobnost med glasbenima okusoma, tako da delimo število skupnih s številom vseh pesmi (torej: delimo gornji števili). Če sta oba spiska prazna, funkcija vrne 0.

Rešitev s slovarjem

Najprej bomo spisek shranjevali v slovar. Ključi bodo naslovi pesmi, vrednosti pa število poslušanj.

Funkcija prazen_spisek le vrne prazen slovar.

def prazen_spisek():
    return {}

Mnogi ste slovar "najprej naredili, nato vrnili".

def prazen_spisek():
    nov_spisek = {}
    return nov_spisek

Nepotrebno.

Če ste želeli, ste lahko vrnili slovar s privzetimi vrednostmi.

from collections import defaultdict

def prazen_spisek():
    return defaultdict(int)

Ko poslušamo neko pesem, povečamo število poslušanj.

def poslusam(spisek, pesem):
    if pesem not in spisek:
        spisek[pesem] = 1
    else:
        spisek[pesem] += 1

Če uporabljamo deafultdict pa zadošča

def poslusam(spisek, pesem):
    spisek[pesem] += 1

Tule je mnoge begalo, kaj bo funkcija poslusam vračala. Nič. Funkcija poslušam le spremeni slovar in ne vrne ničesar. Nekateri ste v začetku te funkcije sestavili nov slovar. Tudi to ni prav: funkcija mora spreminjati slovar, ki ga dobi kot argument.

Funkcija, ki vrača število predvajanj, bi lahko bila takšna:

def predvajanj(spisek, pesem):
    return spisek[pesem]

Vendar to deluje le, če imamo slovar s privzetimi vrednostmi. Pri ostalih se zalomi, če pesmi še ni na spisku; v tem primeru Python javi napako KeyError. Pri običajnih slovarjih zato uporabimo get.

def predvajanj(spisek, pesem):
    return spisek.get(pesem, 0)

Število vseh pesmi je kar dolžina slovarja.

def vseh_pesmi(spisek):
    return len(spisek)

Število vseh predvajanj pa vsota njegovih vrednosti.

def vseh_predvajanj(spisek):
    return sum(spisek.values())

Če še nismo povedali za funkcijo sum: no, zdaj veste. Če še niste vedeli, ste morali pač sami sprogramirati vsoto. Saj vam ni škodilo. :)

Iskanje najbolj priljubljene pesmi ni nič drugega kot stokrat prežvečeno iskanje največjega elementa po določenem kriteriju. Ne spreglejte, kako nam tule pride prav items().

def najbolj_priljubljena(spisek):
    naj_pesem = None
    naj_poslus = 0
    for pesem, poslus in spisek.items():
        if poslus > naj_poslus:
            naj_poslus, naj_pesem = poslus, pesem
    return naj_pesem

Zdaj pa najpreprostejši funkciji, s katerima ste se najbolj ubijali. To pa zato, ker se kljub toplim priporočilom s predavanj mnogi niste spomnili na množice. Funkciji sprašujeta po velikosti preseka in velikosti unije dveh množic, ki ju pridelamo iz ključev obeh slovarjev.

def stevilo_skupnih(spisek1, spisek2):
    return len(set(spisek1) & set(spisek2))

def velikost_repertoarja(spisek1, spisek2):
    return len(set(spisek1) | set(spisek2))

Podobnost izračunamo kot kvocient tega, kar vrneta gornji funkciji. Le na deljenje z nič popazimo: naloga pravi, naj funkcija vrne 0, kadar spiska nimata nobene skupne pesmi.

def podobnost(spisek1, spisek2):
    s = stevilo_skupnih(spisek1, spisek2)
    r = velikost_repertoarja(spisek1, spisek2)
    if r == 0:
        return 0
    return s / r

Rešitev s seznamom

V drugi različici bo spisek seznam.

Prve funkcije so kvečjemu preprostejše kot prej. Spomniti se moramo le, da bomo število pojavitev pesmi v spisku dobili s count in da dobimo število unikatnih pojavitev tako, da preverimo velikost množice.

def prazen_spisek():
    return []

def poslusam(spisek, pesem):
    spisek.append(pesem)

def predvajanj(spisek, pesem):
    return spisek.count(pesem)

def vseh_pesmi(spisek):
    return len(set(spisek))

def vseh_predvajanj(spisek):
    return len(spisek)

Funkcija najbolj_priljubljena je podobna kot prej, le da moramo stalno preštevati pojavitve pesmi. Da bi vsako pesem preverjali le enkrat, smo zanko napisali takole: for pesem in set(spisek) in ne for pesem in spisek. Delovalo pa bi tudi drugo.

def najbolj_priljubljena(spisek):
    naj_pesem = None
    naj_poslus = 0
    for pesem in set(spisek):  # !!!
        poslus = spisek.count(pesem)
        if poslus > naj_poslus:
            naj_poslus, naj_pesem = poslus, pesem
    return naj_pesem

Ostale tri funkcije so enake kot prej!

Prednost slovarjev?!

Če so spiski dolgi, bo count počasen, ker mora dejansko prek celega spiska. Množice pa število predvajanj vrnejo v trenutku. Zato bi vsak izkušen programer tule refleksno uporabil slovarje.

Tudi ostale metode so hitrejše, če uporabljamo slovarje. Če, recimo, pokličemo set(spisek) bo moral Python čez vse ključe slovarja ali pa čez vse elemente seznama. Ključev slovarja je toliko, kolikor je različnih pesmi, elementov seznama pa toliko, kolikor je vseh predvajanj. Pri takšnile domači nalogi ni bistvene razlike, v resničnem svetu pa bi se to lahko zelo poznalo.

Dodatna naloga

Napiši funkcijo lestvica(spisek, n), ki vrne seznam n največkrat poslušanih pesmi. Pesmi, ki so poslušane enakokrat, naj bodo urejene po abecedi. Če spisek vsebuje manj kot n pesmi, naj bo lestvica pač krajša.

Rešitev

S slovarjem:

def lestvica(spisek, n):
    p = []
    for pesem, poslus in spisek.items():
        p.append((-poslus, pesem))
    p.sort()
    s = []
    for poslus, pesem in p[:n]:
        s.append(pesem)
    return s

In s seznamom:

def lestvica(spisek, n):
    p = []
    for pesem in set(spisek):
        p.append((-spisek.count(pesem), pesem))
    p.sort()
    s = []
    for poslus, pesem in p[:n]:
        s.append(pesem)
    return s

Glavna težava je bila, da je potrebno urediti padajoče po številu predvajanj in naraščajoče po abecedi. Zato sestavimo pare, katerih prvi element je negativno(!) število predvajanj, drugi pa ime. Če to uredimo naraščajoče, bomo dobili ravno pravi vrstni red. Nato vrnemo prvih n pesmi, pa smo.