TI/Funkcje, struktury danych, moduły

Funkcje

Definicja

Dlaczego funkcja nazywa się właśnie tak, a nie np. procedura? Tak jak w matematyce, w programowaniu funkcja to "przyporządkowanie", które otrzymawszy jakieś argumenty coś zwraca. Dlatego też w niektórych językach programowania jest rozróżnienie na funkcje i procedury — funkcje to takie twory które "wywołane" zwracają jakąś wartość, natomiast procedury po prostu coś robią i nie dostajemy żadnego wyniku. W pythonie nie ma procedur. Zatem czy:

def hello1():
    print "hello world"

Jest funkcją? A może należałoby napisać tak:

def hello2():
    return "hello world"

Oba twory są funkcjami, w pythonie nawet jeśli nie napiszemy explicite return, nasza funkcja coś zwraca — instrukcja return bez podanej wartości jest równoważna instrukcji return None.

Ciekawostka

Jak już wiecie, Python jest silnie zorientowany obiektowo, co oznacza, że wszystko jest obiektem, włącznie z liczbami, napisami i funkcjami. W szczególności funkcje, jak inne obiekty, mogą mieć atrybuty.

def log(msg):
   log.file.write(msg)

log.file = open('/tmp/log')

Zadanie

Porównaj powyższe funkcje:

x1 = hello1()
x2 = hello2() 
print x1, x2

Dostęp do zmiennych

Obiekty w Pythonie dzielą się na niezmienne (liczby, napisy, krotki) i takie, które można zmieniać (listy, słowniki,... i inne struktury danych).

• Zastanów się, jakie będą wyniki wywołania następujacych instrukcji. Pamiętaj o tym, że argumentem przekazywanym funkcji jest obiekt. W zadaniach może okazać się, że kod jest błędny i musisz go poprawić.

1. Zmienne lokalne i globalne

   x = 6
   def fun(x):
       x += 1
       return x
   
   print fun(x)
   print x
   

   x = 6
   def fun(x):
       global x
       x += 1
       return x
   print fun(x)
   print x
   

   x = 6
   def fun(x):
       x += 1
       return x
   x = 7
   print fun(x)
   print x
   

   x = 6
   def fun(x):
       global x
       x += 1
       return x
   x = 7
   print fun(x)
   print x
   

   x = 6
   def fun(x):
       def fun1():
           global x
           x += 1
           return x
       x = 0
       return x
   x = 7
   print fun(x)
   print x
   

   # zmienne lokalne i globalne
   def modify0(anum):
       global x
       x = anum
       y = anum
       return (x,y)
   
   x = y = 5
   print modify0(3)
   print x, y
   

   Wniosek: global x powoduje, ze x jest tą samą zmienną co zmienna x zdefiniowana poza funkcją — zmiana x wewnątrz funkcji jest widoczna też na zewnątrz. W pozostałych przypadkach, nawet jeśli zmienne mają takie same nazwy jak jakies zmienne zdefioniowane na zewnątrz funkcji, zmiany nie są widoczne na zmiennych na zewnątrz. Jak to działa? Każda funkcja ma własny "konktekst wykonania", i jesli zmienna nie jest poprzedzona słówkiem global, to do kontekstu wykonania funkcji nie jest przekazywana zmienna z kontekstu wykonania programu, tylko jest tworzona nowa zmienna.

2. def fun0():
       y = 5
       global x
       def fun1():
           global y
           y = 0
           return y
       fun1()
       print y    
       x += y
       return x
       
   y = 7
   x = 10
   
   fun0()
   print x
   print y
   

   Słówko global wiąże zmienną ze zmienną zdefiniowaną bezpośrednio w module, a nie ze zmienną z "nadfunkcji".

3. # liczby jako argument
   
   def modify5(anum):
       anum += 1
   
   def modify6(anum):
       anum = 0
   
   x = 10
   
   modify5(x)
   print x
   modify6(x)
   print x
   

   Przekazywaliśmy wszystko przez wartość, więc zmienne są lokalne, zmiany nie są widoczne na zewnątrz.

4. # napisy jako argument
   
   def modify7(astring):
       astring.append("a")
   
   s = "test"
   
   modify7(s)
   print s
   

   Na napisie w ogóle nie można takiej operacji wykonać.

5. # listy jako argumenty
   
   def modify1(alist):
       alist.append(5)
   
   def modify2(alist):
       alist[0] += 3
   
   def modify3(alist):
       alist = []
   
   def modify4(alist):
       alist = [2*x for x in alist]
   
   lista = [1,2,3,4]
   
   modify1(lista)
   print lista
   modify2(lista)
   print lista
   modify3(lista)
   print lista
   modify4(lista)
   print lista
   

   def const_lst(item,lst=[]):
       lst.append(item)
       return lst
   
   L1 = const_lst(1)
   L2 = const_lst(11)
   
   print L1,L2
   

   Tutaj ponownie przekazywaliśmy wszystko przez wartość. Więc jak to jest, że czasem wynik jest widoczny na zewnątrz, a czasem nie? Czym jest tak na prawdę wartość, którą przekazujemy w przypadku list?

• Wytłumacz otrzymane wyniki, korzystając z pojęcia obiektu niezmienniczego i takiego, który można zmieniać.

Zmienne kontra Niezmienne dla zainteresowanych

Żeby lepiej zrozumieć jak działa obiekt niezmienny, a jak zmienny przyjrzyjmy się przykładowi jak klasę która jest "zmienna" przerobić na "niezmienną":

class Immutable(object):
     """An immutable class with a single attribute 'value'."""
     def __setattr__(self, *args):
         raise TypeError("can't modify immutable instance")
     __delattr__ = __setattr__
     def __init__(self, value):
         # we can no longer use self.value = value to store the instance data
         # so we must explicitly call the superclass
         super(Immutable, self).__setattr__('value', value)

Przekazywanie argumentów

Odgadnij jaki będzie wynik następnujących instrukcji:

1. def func(arg1, arg2=5):
       def inner_func(arg3 = arg2):
           return arg1, arg3
       arg1 = arg2 = 15
       return inner_func
   
   f = func(1,2)
   print f()
   f2 = func(0)
   print f2()
   

2. def nostar(a): print a
   
   def onestar(*a): print a
   
   def twostar(**a): print a
   
   nostar(1)
   nostar(1,2,3)
   
   onestar(1,2,3)
   
   twostar(a=1,b=2,c=3)
   
   twostar(1,2,3)
   
   def somearguments(a,b,c,d): print a,b,c,d
   
   somearguments(1)
   somearguments(1,2,3,4)
   x = (1,2,3,4)
   somearguments(x)
   somearguments(*x)
   somearguments(**x)
   x = {'a':1, 'b':2, 'c':3, 'd':4}
   somearguments(x)
   somearguments(*x)
   somearguments(**x)
   

Wyrażenie lambda

Wyrażenie lambda pojawiło się już w zeszłym roku.

Wyrażenie lambda umożliwia zapisanie jednolinijkowej funkcji bezpośrednio w kodzie programu bez potrzeby definiowania jej.

Standardowo definiując funkcję zwiększającą swój argument o 1, napisalibyśmy:

def zwieksz(x):
   return x+1

i wywołalibyśmy ją w programie:

print zwieksz(4)

Używając wyrażenia lambda, można zapisać to inaczej:

zwieksz = lambda x: x + 1
print zwieksz(4)

Możliwa jest też taka forma użycia:

g = (lambda x: x + 1)(4)
print g

Program też wypisuje wtedy na ekran 5.

Wygodnym zastosowaniem konstrukcji lambda jest funkcja map — map(funkcja, lista) zwraca listę z wynikami wykonania funkcji funkcja na elementach listy lista. Można zatem napisać tak:

res = map(lambda x: 3*x, [1,2,3,4])

dostajemy res = [3, 6, 9, 12] Albo tak:

res = map(lambda x,y: x+y, [1,2,3,4], [5,6,7,8] )

Wyrazenie dodaje nam dwie listy element po elemencie: res = [6, 8, 10, 12].

Moduły

Zadanie domowe

Zapisz wszystkie programy rysujące figury na ekranie do oddzielnych funkcji i zrób z nich moduł. Dodaj do niego funkcję rysującą trójkąt o boku [math]N[/math] i wysokości [math]\frac{N-1}{2}[/math] znaków. Załóż, że pary znaków [] są kwadratowe. Skorzystaj ze wskazówki podanej na poprzednich zajęciach.

........[]........

......[][][]......

....[][][][][]....

..[][][][][][][]..

[][][][][][][][][]

1 2 3 4 5 6 7 8 N

Zadanie domowe

Zbierz wszystkie swoje funkcje pisane na zajęcia z Analizy Sygnałów i złóż w jeden moduł. Opatrz je docstringami. Autor najlepszego modułu (najbardziej kompletnego, z funkcjami z najlepszymi modułami) dostanie dodatkową piatkę (liczącą się do oceny końcowej), a jego moduł zostanie oficjalną ściągawką używaną na zajęciach z Analizy Sygnałów.

Struktury danych

Sekwencje

Lista

Napisz polecenie, które:

• doda element x na koniec listy l,
• połączy listy l1 i l2,
• na pozycje i listy l wstawi element x (tzn pomiędzy element i a i+w włoży nowy element),
• usunie z listy l pierwsze wystąpienie elementu x,
• usunie z listy l piąty element,
• poda indeks pierwszego wystąpienia elementu x na liscie l,
• zwróci liczbę wystąpień elementu x na liście l,
• posortuje listę l,
• utworzy odwrotność listy l1,
• mając daną listę l1 liczb naturalnych utworzy listę l2, taką że l2[i] = l1[i] + i,
• mając daną listę l1 liczb naturalnych utworzy listę l2, taką że l2[i] = l1[i] + 1 jeśli l1[i] jest parzyste, oraz l2[i] = l1[i] w przeciwnym przypadku.

Wstęp do struktur danych: stos

Idea stosu.

Mówiąc abstrakcyjnie, czysto teoretycznie, stos jest to taki "obiekt", "zbiór", "struktura danych", która posiada:

• bufor z danymi,
• operacje:
  • push() — dodaje element na "wierzchołek" stosu,
  • pop() — zdejmuje element, który został ostatnio dodany z wierzchołka stosu.

Zupełnie tak, jak na rysunku Figure 1.

Taka jest niezależna od konkretnego języka programowania definicja stosu. W różnych językach programowania taka struktura może być różnie zaimplementowana.

W pythonie listy bardzo dobrze służą jako stos, udostępniając następujące operacje:

• append() implementuje operację push() (tzn. ma takie działanie jak nasz teoretyczny push() w stosie),
• pop() działa dokładnie jak nasz "teoretyczny" pop().

Ćwiczenia

• wypisze elementy od 3 do 20 listy l,
• utwórz listę 100 zer.

Zadanie (właściwości obiektów, które nie są niezmienne)

Jaki będzie wynik następujących instrukcji i dlaczego:

a = ['1', '2', '3', '4', '5']
b = c = a
a.pop()
print a, b, c

a = ['1', '2', '3', '4', '5']
b = c = a
a.pop()
a = ['aaa', 'bbb', 'ccc']
print a, b, c

Kolejka

Schemat kolejki.

Kolejka jest to taka struktura danych, która posiada bufor na dane oraz udostępnia operacje:

• pop(): wyjmuje element, który jako pierwszy pojawił się w kolejce (analogicznie do kolejki w sklepie — ten kto przyszedł pierwszy jest jako pierwszy obsługiwany),
• push(): dokłada element na koniec kolejki.

Pythonowy obiekt deque znajdujący się w module collections dobrze implementuje kolejkę (będący w istocie kolejka dwukierunkową):

• operacja append() spełnia funkcję abstrakcyjnego push(),
• operacja popleft() spełnia funkcję abstrakcyjnego pop().

Stos vs Kolejka: zastosowania

• Omów czym się różnią operacje pop() i push() w kolejce oraz stosie.

Problemy

Wskazówka

W poniższych zadaniach warto jest skorzystać z funkcji loadtxt z modułu numpy.

Splot i korelacja

Numeryczny (przepisany na możliwości komputerów) zapis operacji matematycznej, jaką jest splot, przedstawia się wzorem:

[math] f(k) = \sum _{n=k}^{N} f(n) g(n-k) [/math]

dla [math]k = 0, \cdots , N[/math].

Przykład splotu dwóch szeregów czasowych zapisanych w wektorach o długości N.

Zadanie 1

Plik:Splot dane f.txt (http://brain.fuw.edu.pl/edu/Plik:Splot_dane_f.txt) i Plik:Splot dane g.txt (http://brain.fuw.edu.pl/edu/Plik:Splot_dane_g.txt) zawierają pewne szeregi czasowe [math]f[/math] i [math]g[/math] o długości [math]N=1000[/math]. Napisz funkcję liczącą ich splot, zakładając, że oba wektory są tej samej długości.

Zadanie 2

Napisz funkcję liczącą splot, korzystając z rachunku macierzowego. Porównaj szybkość obu funkcji korzystając z funkcji time() z modułu time:

start = time.time()
wywoływane operacje
trwalo = time.time() - start

W przypadku numerycznego obliczania splotu zwykle zakładamy, że "wystające części wektorów" wypełniamy zerami. Możemy też zastosować tzw. cykliczne warunki brzegowe i brakujące fragmenty wektorów wypełnić występującymi już wartościami tychże wektorów (zakładając, że cały wektor jest okresową sekwencją, która się powtarza).

Zadanie 3

Napisz wersję funkcji liczącej splot, w której "wystające części wektorów" wypełniasz wartościami wektora (początkowymi jeżeli doklejasz je na końcu, końcowymi jeżeli doklejasz je na początku).

Funkcja korelacji mówi o tym, jak dwa sygnały/szeregi czasowe/funkcje są do siebie podobne. W praktyce oblicza się ją, jako splot obu szeregów, pomniejszonych o ich średnią, podzielony przez średnie odchylenie standardowe każdego z nich:

[math] \mathrm{corr}\left(x(t),y(t),\tau\right) = \frac{\int (x(t)-\mu_x)( y(t-\tau)-\mu_y) dt } {\sqrt{ \int (x(t)-\mu_x)^2 dt \int (y(t)-\mu_y)^2 dt [/math]

Co w postaci dyskretnej przyjmuje postać:

[math] \frac{\sum_i (x_i-\mu_x)(y_{i-k}-\mu_y)} {\sqrt{\sum_j (x_j-\mu_x)^2 \sum_k (y_k-\mu_y)^2 [/math]

Zadanie 4

Korzystając z funkcji obliczającej średnią i wariancję (np. z modułu numpy) i funkcji obliczającej splot, napisz funkcję zwracającą wektor zawierający korelację dwóch wektorów. Zastanów się, jakiej długości będzie ten wektor. Stwórz moduł obliczający korelację i splot.

Odrzucanie out-lierów

Out-liery.

W pracy doświadczalnika bardzo często zdarza się sytuacja, gdy pewna część wyników pomiaru znajduje się poza "rozsądnym" przedziałem i trzeba je odrzucić. Zwykle ten rozsądny przedział określany jest jako:

[math] [\mu - 3\sigma ; \mu + 3\sigma ]. [/math]

gdzie

[math] \begin{matrix} N = \text{liczba\ liczb}\\ \mu = \sum _i x_i / N\\ \sigma ^2 = \sum _i (x_i - \mu )^2 / (N - 1) \end{matrix}. [/math]

Zadanie

Plik:Dystrybucja.txt (http://brain.fuw.edu.pl/edu/Plik:Dystrybucja.txt) zawiera wyniki pomiarów pewnej wielkości.

Wypisz te, które leżą poza przedziałem

[math] [\mu - 3\sigma ; \mu + 3\sigma ]. [/math]

Gdyby te liczby pochodziły z rozkładu normalnego, to oczekiwalibyśmy, że 99.7% z nich mieści się w przedziale [math]\pm 3\sigma [/math]. Czy wobec tego te dane mogą pochodzić z rozkładu normalnego?

Powierzchnia wielokąta

Wielokąt i jego wierzchołki.

Pole powierzni wielokąta prostego (w którym krawędzie nie przecinają się) przedstawia się wzorem:

[math] S = \sum _{i=0}^{N-1} \left| \vec{x}_i \times \vec{x}_{(i + 1) \mathrm {mod} N} \right| / 2 [/math]

gdzie [math]\times[/math] oznacza iloczyn wektorowy

[math]\left| \vec{a} \times \vec{b} \right| = a_x b_y - a_y b_x [/math]

Zadanie

Plik:Wielokacik.txt (http://brain.fuw.edu.pl/edu/Plik:Wielokacik.txt) zawiera wierzchołki pewnego wielokąta zapisane jako

[math]x_0[/math] [math]y_0[/math]

[math]x_1[/math] [math]y_1[/math]

[math]x_2[/math] [math]y_2[/math]

[math]x_3[/math] [math]y_3[/math]

…

[math]x_{N-1}[/math] [math]y_{N-1}[/math]

Oblicz powierzchnię [math]S[/math] tego wielokąta.