Tekst źródłowy strony 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 &mdash; 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:

<source lang="python">
def hello1():
    print "hello world"
</source>

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

<source lang="python">
def hello2():
    return "hello world"
</source>

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

====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.
<source lang = "python">
def log(msg):
   log.file.write(msg)

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

</source>




====Zadanie====
Porównaj powyższe funkcje:
<source lang="python">
x1 = hello1()
x2 = hello2() 
print x1, x2
</source>

=== 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ć.
<ol>
<li> Zmienne lokalne i globalne
<source lang = "python">
x = 6
def fun(x):
    x += 1
    return x

print fun(x)
print x
</source>

<source lang = "python">
x = 6
def fun(x):
    global x
    x += 1
    return x
print fun(x)
print x
</source>

<source lang = "python">
x = 6
def fun(x):
    x += 1
    return x
x = 7
print fun(x)
print x
</source>

<source lang = "python">
x = 6
def fun(x):
    global x
    x += 1
    return x
x = 7
print fun(x)
print x
</source>

<source lang = "python">
x = 6
def fun(x):
    def fun1():
        global x
        x += 1
        return x
    x = 0
    return x
x = 7
print fun(x)
print x
</source>

<source lang="python">
# 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
</source>

Wniosek: <tt>global x</tt> powoduje, ze <tt>x</tt> jest tą samą zmienną co zmienna <tt>x</tt> zdefiniowana poza funkcją &mdash; zmiana <tt>x</tt> 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. 
<li>
<source lang="python">
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
</source>

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

<li><source lang = "python">
# liczby jako argument

def modify5(anum):
    anum += 1

def modify6(anum):
    anum = 0

x = 10

modify5(x)
print x
modify6(x)
print x
</source>

Przekazywaliśmy wszystko przez wartość, więc zmienne są lokalne, zmiany nie są widoczne na zewnątrz.
<li><source lang = "python">
# napisy jako argument

def modify7(astring):
    astring.append("a")

s = "test"

modify7(s)
print s
</source>

Na napisie w ogóle nie można takiej operacji wykonać.
<li><source lang="python">
# 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
</source>

<source lang="python">
def const_lst(item,lst=[]):
    lst.append(item)
    return lst

L1 = const_lst(1)
L2 = const_lst(11)

print L1,L2
</source>
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?
</ol>
*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ą":
<source lang="python">

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)

</source>

===Przekazywanie argumentów===

Odgadnij jaki będzie wynik następnujących instrukcji:
<ol><li>
<source lang = "python">

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()
</source>
<li><source lang = "python">

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)
</source>
</ol>
<!--===Dokumentacja funkcji &mdash; opisy wpisane w funkcje===
Przypomnij sobie, jak dokumentuje się funkcję (jeśli nie pamiętasz jest to opisane w podręczniku [[TI/Programowanie_z_Pythonem/Funkcje#Opisy_wbudowane_w_funkcje|w podręczniku z zeszłego roku]]). Masz 10 minut na przygotowanie krótkiej prezentacji (max 3 slajdy) o tym, jak należy pisać opisy w funkcji. Pliki o nazwie <tt>imie_nazwisko</tt> (zamiast <tt>imie</tt> wpisz swoje imię, a zamiast <tt>nazwisko</tt> &mdash; swoje nazwisko) i odpowiednim rozszerzeniu prześlij prowadzącemu ćwiczenia.-->

===Wyrażenie lambda===
Wyrażenie <tt>lambda</tt> pojawiło się już w [[TI/Programowanie_z_Pythonem/Wybrane_zagadnienia_numeryczne#Wyra.C5.BCenia_lambda|zeszłym roku]].

Wyrażenie <tt>lambda</tt> 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:
<source lang="python">
def zwieksz(x):
   return x+1
</source>
i wywołalibyśmy ją w programie:
<source lang="python">
print zwieksz(4)
</source>
Używając wyrażenia lambda, można zapisać to inaczej:
<source lang="python">
zwieksz = lambda x: x + 1
print zwieksz(4)
</source>

Możliwa jest też taka forma użycia:
<source lang="python">
g = (lambda x: x + 1)(4)
print g
</source>
Program też wypisuje wtedy na ekran 5.

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

<source lang="python">
res = map(lambda x: 3*x, [1,2,3,4])

</source>
dostajemy res = [3, 6, 9, 12]
Albo tak:
<source lang="python">
res = map(lambda x,y: x+y, [1,2,3,4], [5,6,7,8] )

</source>
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 <tt>[]</tt> są kwadratowe. Skorzystaj ze [[TI/Python_-_powtórzenie/Zajęcia_1#Wskaz.C3.B3wka|wskazówki podanej na poprzednich zajęciach]].

<tt>........[]........</tt>

<tt>......[][][]......</tt>

<tt>....[][][][][]....</tt>

<tt>..[][][][][][][]..</tt>

<tt>[][][][][][][][][]</tt>

<tt> </tt>

<tt>1 2 3 4 5 6 7 8 N</tt>

===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 <tt>x</tt> na koniec listy <tt>l</tt>,
* połączy listy <tt>l1</tt> i <tt>l2</tt>,
* na pozycje <tt>i</tt> listy <tt>l</tt> wstawi element <tt>x</tt> (tzn pomiędzy element i a i+w włoży nowy element),
* usunie z listy <tt>l</tt> pierwsze wystąpienie elementu <tt>x</tt>,
* usunie z listy <tt>l</tt> piąty element,
* poda indeks pierwszego wystąpienia elementu <tt>x</tt> na liscie <tt>l</tt>,
* zwróci liczbę wystąpień elementu <tt>x</tt> na liście <tt>l</tt>,
* posortuje listę <tt>l</tt>,
* utworzy odwrotność listy <tt>l1</tt>,
* mając daną listę <tt>l1</tt> liczb naturalnych utworzy listę <tt>l2</tt>, taką że <tt>l2[i] = l1[i] + i</tt>,
* mając daną listę <tt>l1</tt> liczb naturalnych utworzy listę <tt>l2</tt>, taką że <tt>l2[i] = l1[i] + 1</tt> jeśli <tt>l1[i]</tt> jest parzyste, oraz <tt>l2[i] = l1[i]</tt> w przeciwnym przypadku.
===== Wstęp do struktur danych: stos =====
[[File:Data stack.svg|thumb|<figure id="fig: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:
** <tt>push()</tt> &mdash; dodaje element na "wierzchołek" stosu,
** <tt>pop()</tt> &mdash; zdejmuje element, który został ostatnio dodany z wierzchołka stosu.
Zupełnie tak, jak na rysunku <xr id="fig:stos"/>.

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:
* <tt>append()</tt> implementuje operację <tt>push()</tt> (tzn. ma takie działanie jak nasz teoretyczny <tt>push()</tt> w stosie),
* <tt>pop()</tt> działa dokładnie jak nasz "teoretyczny" <tt>pop()</tt>.

==== Ćwiczenia ====
* wypisze elementy od 3 do 20 listy <tt>l</tt>,
* 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:
*
<source lang="python">
a = ['1', '2', '3', '4', '5']
b = c = a
a.pop()
print a, b, c
</source>
*
<source lang="python">
a = ['1', '2', '3', '4', '5']
b = c = a
a.pop()
a = ['aaa', 'bbb', 'ccc']
print a, b, c
</source>

====Krotka====
====Kolejka====
[[Plik:Data Queue_pol.svg|thumb|Schemat kolejki.]]
Kolejka jest to taka struktura danych, która posiada bufor na dane oraz udostępnia operacje:
* <tt>pop()</tt>: wyjmuje element, który jako pierwszy pojawił się w kolejce (analogicznie do kolejki w sklepie &mdash; ten kto przyszedł pierwszy jest jako pierwszy obsługiwany),
* <tt>push()</tt>: dokłada element na koniec kolejki.
Pythonowy obiekt <tt>deque</tt> znajdujący się w module <tt>collections</tt> dobrze implementuje kolejkę (będący w istocie kolejka dwukierunkową):
* operacja <tt>append()</tt> spełnia funkcję abstrakcyjnego <tt>push()</tt>,
* operacja <tt>popleft()</tt> spełnia funkcję abstrakcyjnego <tt>pop()</tt>.

==== Stos vs Kolejka: zastosowania ====
* Omów czym się różnią operacje pop() i push() w kolejce oraz stosie.

===Słowniki===

==Problemy==
===Wskazówka===
W poniższych zadaniach warto jest skorzystać z funkcji <tt>loadtxt</tt> z modułu <tt>numpy</tt>.
===Splot i korelacja===
Numeryczny (przepisany na możliwości komputerów) zapis operacji matematycznej, jaką jest [[STAT:Twierdzenia_o_splocie_i_o_próbkowaniu_(aliasing)|splot]], przedstawia się wzorem:
::<math>
f(k) = \sum _{n=0}^{k} f(n) g(k-n)
</math>
dla <math>k = 0, \cdots , N</math>.

[[Plik:Array_convolution.svg|thumb|200px|Przykład splotu dwóch szeregów czasowych zapisanych w wektorach o długości <tt>N</tt>.]]
====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 <tt>time()</tt> z modułu <tt>time</tt>:
<source lang = "python">
start = time.time()
wywoływane operacje
trwalo = time.time() - start
</source>


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 <tt>numpy</tt>) 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 <i>out-lierów</i>===
[[Plik:outliers.png|thumb|300px|<i>Out-liery</i>.]]
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
<equation id="uid1">
<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>
</equation>
====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===
[[Plik:Polygon vertex labels.svg|thumb|400px|Wielokąt i jego wierzchołki.]]
Pole powierzni wielokąta prostego (w którym krawędzie nie przecinają się) przedstawia się wzorem:
<equation id="uid2">
<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>
</equation>
====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.