Naloge se nanašajo na dekoratorja @lru_cache in @singledispatch, ki sta opisana v dokumentaciji modula functools.

Nalogi

1. Napiši funkcijo za izračun n-tega Fibonacijevega števila v rekurzivni obliki (n-to Fibonacijevo število je enako vsoti n-1-tega in n-2-tega. Prvo in drugo Fibonacijevo število je 0.)

Poskusi izračunati deseto, dvanajsto, štirinajsto ... ... število. Kako narašča čas računanja? Kako velika števila lahko še izračunaš v doglednem času?

2. Dodaj dekorator @lru_cache. Kako hitro se števila računajo zdaj?

Rešitev

Pridelali smo

@lru_cache(100)
def fibo(n):
    if n <= 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

Brez dekoratorja, @lru_cache(100), se začne pošteno obirati med n=30 (tu je še čisto hitra) in 35 (ta ne gre nikamor več). Malo smo razmislili in ugotovili, da je čas izvajanja funkcije kar sorazmeren Fibonacijevemu številu, ki ga mora naračunati. Za tiste, ki že veste, kaj to pomeni: čas narašča eksponentno, približno z $O(1.6^n)$. Računanje vsakega naslednjega člena zahteva 1.6-krat več časa.

Če dodamo @lru_cache se vede presenetljivo imenitno in ne računa bliskovito le prvih 100 ali 200 ali 1000 členov, temveč postane funkcija praktično enako hitra kot računanje "naprej", z zanko. Še več, kot je odkril Metod, zadošča, da si zapomnimo zadnja dva člena, pod pogojem, da obrnemo vsoto - namesto fibo(n - 1) + fibo(n - 2) moramo seštevati fibo(n - 2) + fibo(n - 1).

@lru_cache(2)
def fibo(n):
    if n <= 2:
        return 1
    return fibo(n - 2) + fibo(n - 1)

(Razlog je zanimiv. Najprej izračuna n-2-go število. Ko potem računa n-1, ima n-2-gega ravno še pri roki in mu ga zato ni potrebno računati. Pri računanju n-2-gega se zgodba ponovi. Števila se zato v bistvu izračunajo naprej.)

Nalogi

3. Napiši funkcijo vsota(s), ki vrne vsoto elementov v s. Če je s slučajno slovar, naj vrne vsoto vrednosti v tem slovarju, ne vsoto ključev. Če je s niz, naj ga razcepi (split), pretvori kose v števila in jih sešteje.

4. Če v prejšnji točki še nisi naredil(a) tako: reši jo z uporabo dekoratorja @singledispatch.

Temu, kar dela @singledispatch se učeno reče memoizacija.

Rešitev

Ker namen te vaje ni ponavljanje snovi Programiranja 1, bo funkcija vsota klicala kar funkcijo sum. Dokler ne vemo za dekoratorje, bomo pisali

def vsota(s):
    if isinstance(s, dict):
        return sum(s.values())
    elif isinstance(s, str):
        return sum(int(x) for x in s.split())
    else:
        return sum(s)

("V živo smo sicer naredili tole poučno kvazi-rekurzivno varianto:

def vsota(s):
    if isinstance(s, dict):
        return vsota(s.values())
    elif isinstance(s, str):
        return vsota(int(x) for x in s.split())
    v = 0
    for e in s:
        v += e
    return v

)

Z dekoratorjem @singledispatch spremenimo (prvo) rešitev v

@singledispatch
def vsota(s):
    return sum(s)

@vsota.register(dict)
def _(s):
    return sum(s.values())

@vsota.register(str)
def _(s):
    return sum(int(x) for x in s.split())

Prva funkcija je "osnovna", ostali dve sta specializirani za slovarje in nize. Funkciji se imenujeta _, ker je to ime, ki ga uporabljamo, kadar pač moramo dati neko ime, vendar nam je zanj vseeno.

"V živo" sem namesto imena _ uporabil ime vsota, kar je natančno edino ime, ki ga ne smemo dati tej funkciji. Z njim bi povozili funkcijo vsota in potem zanjo ne bi mogli registrirati izpeljank.

Kar počnemo tu, nekatere najbrž spominja na (function overloading)[https://en.wikipedia.org/wiki/Function_overloading], ki ste ga srečali v kakih drugih jezikih. Medtem ko za "overloading" v teh jezikih poskrbi že prevajalnik, je tule morda bolj pravi termin single dispatch - kar je seveda ravno ime dekoratorja.

Nalogi

5. Napiši dekorator @zaokrozena3, ki poskrbi, da je rezultat dekorirane funkcije zaokrožen na tri decimalke.

6. Napiši dekorator @zaokrozena(n), ki prejme število decimalk kot argument.

Rešitev

Dekorator je funkcija, ki vrača funkcijo. Praviloma bo torej takšne oblike

def ime_dekoratorja(f):
    def dekorirana(*args, *argkw):
        ...
    return dekorirana

V našem primeru imamo

def zaokrozi3(f):
    def zaokrozena(*args, **kwargs):
        return round(f(*args, **kwargs), 3)
    return zaokrozena

Funkcija zaokrozena v bistvu le kliče f - skoraj takšna je:

def zaokrozena(*args, **kwargs):
    return f(*args, **kwargs)

Dobi neke argumente in kliče f z istimi argumenti, ter vrne rezultat f-a. Vse, kar še naredi z njim, je, da rezultat zaokroži na tri decimalke, zato

def zaokrozena(*args, **kwargs):
    return round(f(*args, **kwargs), 3)

Celoten dekorator pa je torej

def zaokrozi3(f):
    def zaokrozena(*args, **kwargs):
        return round(f(*args, **kwargs), 3)
    return zaokrozena

Funkcija f je nekako shranjena v funkciji zaokrozena (rekli smo, da se nahaja v njenem closure-ju, zaprtju).

Zdaj lahko pišemo

@zaokrozena3
def top(kot, v):
    return v ** 2 * sin(2 * radians(kot)) / 9.81

@zaokrozena3
def diagonala(a):
    return a * sqrt(2)

@zaokrozena3
def hipo(a, b):
    return sqrt(a ** 2 + b ** 2)

in vse te funkcije bodo vračale rezultat, zaokrožen na tri decimalke.

Nalogo, ki je zgoraj označena kot štesta, smo reševali zaradi provokacije iz občinstva. :) Recimo, da hočemo zaokrožati na različna števila decimalk

@zaokrozena(3)
def top(kot, v):
    return v ** 2 * sin(2 * radians(kot)) / 9.81

@zaokrozena(1)
def diagonala(a):
    return a * sqrt(2)

@zaokrozena(5)
def hipo(a, b):
    return sqrt(a ** 2 + b ** 2)

Dekorator je, kot smo videli, funkcija, ki vrača funkcijo. zaokrozena3 je bila recimo takšna funkcija, zato smo lahko uporabili zaokrozena3 kot dekorator. Če hočemo pisati @zaokrozena(3), pa mora biti zaokrozena(3) dekorator. Torej je zaokrozena funkcija, ki dobi argument (npr. 3) in vrača dekorator. Funkcija, ki vrača dekorator ... ali, z drugimi besedami, funkcija, ki vrača funkcijo, ki vrača funkcijo. Juhej.

def zaokrozi(n):
    def dekorator(f):
        def zaokrozena(*args, **kwargs):
            return round(f(*args, **kwargs), n)
        return zaokrozena
    return dekorator

Lepota je, da v izrazu round(f(*args, **kwargs), n) dobimo n kot argument funkcije zaokrozi in f kot argument funkcije dekorator.

Trudil se bom, da bi bila tole najbolj zapletena stvar pri tem našem Pythonu 2. O teh rečeh je zabavno razmišljati, ni pa preprosto in tudi ne preveč uporabno. Če boste šli na drugo stopnjo, pa se boste tega naužili pri predmetu Programiranje, kjer boste spoznavali tudi funkcijsko programiranje.

Naloga

Naloge z @dump se nismo lotili. Vseeno ti je nihče ne brani. :)