Bardziej Zaawansowane Tematy

5. Bardziej zaawansowane tematy

Spis treści

Programowanie rekursywne i dynamiczne

Szybkie obliczanie liczb Fibonacciego

Imperatywne (proceduralne) i funkcyjne programowanie

Zmienne lokalne

Pętle i funkcja iteracji

Block i zmienne globalne.

Przykład: symulacja ruchu Browna

Jedna ścieżka

Wiele ścieżek

Programowanie rekursywne i dynamiczne

Programy rekursywne to programy, które "odwołują się do siebie samych". W Mathematice bardzo łatwo jest programować rekursywnie, choć w przeciwieństwie do języków programistycznych takich jak LISP (z którymi język Mathematiki ma pewne podobieństwa), Mathematica nie jest zoptymalizowana do tego celu i nieuważnie napisane programy rekursywne mogą być bardzo powolne. Jednym ze sposobów przyspieszenia programów rekursywnych jest skorzystanie z metody zwanej "programowaniem dynamicznym", lub, bardziej precyzyjnie, metody "funkcji, które zapamiętują swoje wartości". Jest to bardzo pożyteczna metoda, którą najłatwiej zrozumieć, przyglądając się przykładom jej użycia.

Szybkie obliczanie liczb Fibonacciego

Liczby Fibonacciego są rozwiązaniami następującego równania rekursywnego:

KN5_bardziej_zaawansowane_tematy1[2]_1.gif

Funkcja RSolve rozwiązuje wiele równań tego typu:

KN5_bardziej_zaawansowane_tematy1[2]_2.gif

KN5_bardziej_zaawansowane_tematy1[2]_3.gif

Fibonacci[n] to po prostu zakodowana n-ta liczba Fibonacciego. Aby zobaczyć jej definicję, użyjemy polecenia FunctionExpand:

KN5_bardziej_zaawansowane_tematy1[2]_4.gif

KN5_bardziej_zaawansowane_tematy1[2]_5.gif

Teraz spróbujemy sami zdefiniować liczby Fibonacciego. Zrobimy to na dwa sposoby. Pierwszym będzie "zwyczajna rekursja":

KN5_bardziej_zaawansowane_tematy1[2]_6.gif

KN5_bardziej_zaawansowane_tematy1[2]_7.gif

KN5_bardziej_zaawansowane_tematy1[2]_8.gif

KN5_bardziej_zaawansowane_tematy1[2]_9.gif

Niestety to podejście jest bardzo powolne i już obliczenie  liczby Fibonacciego Fib1[30] zabiera zauważalną ilość czasu. W drugim sposobie wykorzystamy "programowanie dynamiczne". Poniższa definicja na pierwszy rzut oka wygląda dziwnie. Należy zwrócić uwagę na równoczesne użycie “:=” i “=”  :

KN5_bardziej_zaawansowane_tematy1[2]_10.gif

KN5_bardziej_zaawansowane_tematy1[2]_11.gif

KN5_bardziej_zaawansowane_tematy1[2]_12.gif

KN5_bardziej_zaawansowane_tematy1[2]_13.gif

KN5_bardziej_zaawansowane_tematy1[2]_14.gif

Tym razem obliczenie  liczby Fibonacciego F2[30] trwało błyskawicznie (prawie 10 tysięcy razy szybciej niż to było przy wykorzystaniu pierwszego sposobu).

Za pomocą funkcji Trace możemy prześledzić dokładnie, co się dzieje podczas wykonywania tych dwóch definicji-programów. Rożnicę widać wyraźnie:

KN5_bardziej_zaawansowane_tematy1[2]_15.gif

KN5_bardziej_zaawansowane_tematy1[2]_16.gif

Łatwo zauważyć, że Fib1 wielokrotnie powtarza te same obliczenia.

W przypadku Fib2 kolejne obliczenia są zupełnie inne. Najpierw usuńmy jeszcze raz Fib2 i zdefiniujmy funkcję od początku:

KN5_bardziej_zaawansowane_tematy1[2]_17.gif

KN5_bardziej_zaawansowane_tematy1[2]_18.gif

KN5_bardziej_zaawansowane_tematy1[2]_19.gif

Teraz wywołajmy Fib2 jeszcze raz, tym razem dla n=6:

KN5_bardziej_zaawansowane_tematy1[2]_20.gif

KN5_bardziej_zaawansowane_tematy1[2]_21.gif

Widzimy wyraźnie, że Mathematica zapamiętała wartości Fib2[n] dla n5 i nie musiała ich ponownie obliczać.

Możemy także sprawdzić bezpośrednio, co Mathematica wie o funkcjach Fib1 i Fib2:

KN5_bardziej_zaawansowane_tematy1[2]_22.gif

Global`Fib1

Fib1[0]=0
Fib1[1]=1
Fib1[n_]:=Fib1[n-1]+Fib1[n-2]

KN5_bardziej_zaawansowane_tematy1[2]_23.gif

Global`Fib2

Fib2[0]=0
Fib2[1]=1
Fib2[2]=1
Fib2[3]=2
Fib2[4]=3
Fib2[5]=5
Fib2[n_]:=Fib2[n]=Fib2[n-1]+Fib2[n-2]

Oczywiście kosztem dużego zysku w szybkości obliczeń przy użyciu programowania dynamicznego jest nieco większa ilość zużytej pamięci. Pamięć tę możemy odzyskać przez:

KN5_bardziej_zaawansowane_tematy1[2]_24.gif

Imperatywne (proceduralne) i funkcyjne programowanie

Dotychczas rozważaliśmy dwa paradygmaty programowania używane w Mathematice: programowanie oparte na regułach oraz programowanie funkcyjne. Teraz skupimy się na programowaniu proceduralnym, zwanym także imperatywnym. Jest to oczywiście najbardziej powszechny paradygmat programowania, oddający dosyć wiernie sposób działania większości współczesnych komputerów. Typowe dla tego paradygmatu jest przypisywanie wartości zmiennym i używanie pętli w celu zmiany tych wartości. Zaczniemy od przykładu:

KN5_bardziej_zaawansowane_tematy1[2]_25.gif

KN5_bardziej_zaawansowane_tematy1[2]_26.gif

Zauważmy, że nie otrzymaliśmy żadnego wyniku. Tym niemniej x ma oczekiwaną wartość:

KN5_bardziej_zaawansowane_tematy1[2]_27.gif

KN5_bardziej_zaawansowane_tematy1[2]_28.gif

Przyjrzyjmy się reprezentacji wewnętrznej (FullForm) obliczanego wyrażenia:

KN5_bardziej_zaawansowane_tematy1[2]_29.gif

KN5_bardziej_zaawansowane_tematy1[2]_30.gif

Zauważmy, że Mathematica automatycznie daje nam wartość ostatniego wyrażenia w ComposedExpression. Jeśli więc nie chcemy tego wyrażenia otrzymać, używamy jako ostatniego argumentu Null.

W wielu proceduralnych językach wartości zmiennej x są zwracane, jeśli użyjemy funkcji Return[x] lub Print[x]. Ponieważ Mathematica zawsze zwraca wartość obliczanego wyrażenia, Return[x] służy tu do zupełnie innego celu. Jeśli pojawi się ono na końcu pętli (zamiast prostego x), możemy być prawie pewni, że autor nauczył się wcześniej programować w języku Fortran (lub C) i nadal pisze programy w tym języku. Nie jest to najbardziej wydajne i eleganckie podejście do programowania w Mathematice, ale działa! Teraz powtórzymy tę samą sekwencję instrukcji, używając pętli “Do”. Zauważmy, że sama pętla “Do” nic nie zwraca - dlatego na końcu kodu umieściliśmy x:

KN5_bardziej_zaawansowane_tematy1[2]_31.gif

KN5_bardziej_zaawansowane_tematy1[2]_32.gif

KN5_bardziej_zaawansowane_tematy1[2]_33.gif

To samo można zapisać nieco krócej:

KN5_bardziej_zaawansowane_tematy1[2]_34.gif

KN5_bardziej_zaawansowane_tematy1[2]_35.gif

W Mathematice można korzystać także z innych, znanych z popularnych języków programowania, pętli, takich jak “While” czy “For”. Zwykle jednak warto ich unikać - rozwiązania wykorzystujące funkcyjne konstrukcje Nest, Fold, FixedPoint i Accumulate zazwyczaj działają znacznie szybciej. Wynika to oczywiście z natury Mathematiki, nie jest to prawdą o programowaniu w ogólności. Nawet w Mathematice różnica w szybkości programów napisanych proceduralnie i funkcyjnie niweluje się w sytuacjach, w których udaje się użyć tzw. kompilacji.

Zmienne lokalne

Jak zawsze używając zmiennych w naszych programach, powinniśmy być czujni, żeby przypadkowo nie zmieniać tych wartości zmiennych, które chcielibyśmy zachować. Najprostszym sposobem zabezpieczenia się przed taką ewentualnością jest używanie zmiennych lokalnych. Mathematica posiada trzy podstawowe konstrukcje lokalizujące zmienne: Block, Module oraz With. Każda z nich działa inaczej oraz ma swoje silne i słabe strony.

KN5_bardziej_zaawansowane_tematy1[2]_36.gif

KN5_bardziej_zaawansowane_tematy1[2]_37.gif

Najpierw obejrzyjmy prosty przykład lokalizacji zmiennych za pomocą konstrukcji Block. Przypisujemy zmiennej x wartość 3, po czym wewnątrz Block zmieniamy jej wartość na 1. Jak widać, "na zewnątrz" bloku wartość x nie uległa zmianie.

KN5_bardziej_zaawansowane_tematy1[2]_38.gif

KN5_bardziej_zaawansowane_tematy1[2]_39.gif

KN5_bardziej_zaawansowane_tematy1[2]_40.gif

KN5_bardziej_zaawansowane_tematy1[2]_41.gif

Dokładnie tak samo w tego typu sytuacji zachowa się konstrukcja Module:

KN5_bardziej_zaawansowane_tematy1[2]_42.gif

KN5_bardziej_zaawansowane_tematy1[2]_43.gif

KN5_bardziej_zaawansowane_tematy1[2]_44.gif

KN5_bardziej_zaawansowane_tematy1[2]_45.gif

KN5_bardziej_zaawansowane_tematy1[2]_46.gif

KN5_bardziej_zaawansowane_tematy1[2]_47.gif

Jednak Block i Module działają zupełnie inaczej. Kiedy lokalizujemy zmienną, używając Block, jej wartość jest najpierw zapamiętana przed wejściem do bloku, potem tymczasowo odebrana wraz z wszystkimi atrybutami zmiennej, i na koniec, po wyjściu z Block, oryginalna wartość zostaje przywrócona zmiennej. W przypadku Module nazwy zmiennych są zmieniane w jego wnętrzu, tak że nie popadają w konflikt ze zmiennymi zewnętrznymi. W przeciwieństwie do Module i Block, kiedy używamy konstrukcji With, wszystkie zmienne lokalne muszą mieć przypisane wartości początkowe:

KN5_bardziej_zaawansowane_tematy1[2]_48.gif

KN5_bardziej_zaawansowane_tematy1[2]_49.gif

Zauważmy teraz pewną cechę, która odróżnia Module i With od Block. W tych dwóch pierwszych inicjalizacja (przypisanie wartości początkowych) wszystkich zmiennych odbywa się niezależnie:

KN5_bardziej_zaawansowane_tematy1[2]_50.gif

KN5_bardziej_zaawansowane_tematy1[2]_51.gif

KN5_bardziej_zaawansowane_tematy1[2]_52.gif

KN5_bardziej_zaawansowane_tematy1[2]_53.gif

KN5_bardziej_zaawansowane_tematy1[2]_54.gif

KN5_bardziej_zaawansowane_tematy1[2]_55.gif

KN5_bardziej_zaawansowane_tematy1[2]_56.gif

KN5_bardziej_zaawansowane_tematy1[2]_57.gif

Block zachowa się inaczej:

KN5_bardziej_zaawansowane_tematy1[2]_58.gif

KN5_bardziej_zaawansowane_tematy1[2]_59.gif

KN5_bardziej_zaawansowane_tematy1[2]_60.gif

A oto inny ważny przykład ilustrujący różnicę między Block i Module:

KN5_bardziej_zaawansowane_tematy1[2]_61.gif

KN5_bardziej_zaawansowane_tematy1[2]_62.gif

KN5_bardziej_zaawansowane_tematy1[2]_63.gif

KN5_bardziej_zaawansowane_tematy1[2]_64.gif

KN5_bardziej_zaawansowane_tematy1[2]_65.gif

Chociaż zmienna foo była zdefiniowana na zewnątrz struktury Block, jej wartość zmieniła się wewnątrz Block. Module zachowuje się inaczej:

KN5_bardziej_zaawansowane_tematy1[2]_66.gif

KN5_bardziej_zaawansowane_tematy1[2]_67.gif

KN5_bardziej_zaawansowane_tematy1[2]_68.gif

KN5_bardziej_zaawansowane_tematy1[2]_69.gif

Czyli ewaluacja wewnątrz Module zależna jest tylko od oryginalnej definicji zmiennej czy funkcji, co nie jest prawdą w przypadku Blocku.

Pętle i funkcja iteracji

Programy napisane zgodnie z paradygmatem imperatywnym zmieniają wartości przypisane jakiejś zmiennej, po czym aby otrzymać wartość zmiennej, należy ją jawnie ewaluować. Widać to w poniższym przykładzie. Sama pętla “Do” nie da nam żadnego wyniku, choć zmieni wartość x. Aby tę wartość otrzymać, musimy dodać x na końcu instrukcji:

KN5_bardziej_zaawansowane_tematy1[2]_70.gif

KN5_bardziej_zaawansowane_tematy1[2]_71.gif

Teraz zrobimy to samo zgodnie z paradygmatem funkcyjnym. Programując w tym stylu, używamy funkcji, które zwracają swoje wartości zamiast zmieniać wartość jakiejś zmiennej. Zamiast pętli używamy specjalnych funkcji które działają na funkcjach i wykonują pewne ich iteracje. Przykładem takiej funkcji jest Nest:

KN5_bardziej_zaawansowane_tematy1[2]_72.gif

KN5_bardziej_zaawansowane_tematy1[2]_73.gif

KN5_bardziej_zaawansowane_tematy1[2]_74.gif

KN5_bardziej_zaawansowane_tematy1[2]_75.gif

oraz spokrewniona z nią funkcja NestList:

KN5_bardziej_zaawansowane_tematy1[2]_76.gif

KN5_bardziej_zaawansowane_tematy1[2]_77.gif

KN5_bardziej_zaawansowane_tematy1[2]_78.gif

KN5_bardziej_zaawansowane_tematy1[2]_79.gif

Możemy teraz, zamiast używać pętli Do (jak w przykładzie powyżej, w którym 20.000 razy zwiększyliśmy o 1 wartość zmiennej x), uzyskać ten sam wynik, programując funkcyjnie:

KN5_bardziej_zaawansowane_tematy1[2]_80.gif

KN5_bardziej_zaawansowane_tematy1[2]_81.gif

Warta zwrócenia uwagi jest duża różnica w szybkości obu tych metod.

Kolejnym przykładem funkcji wykorzystywanej przy programowaniu funkcyjnym jest FoldList:

KN5_bardziej_zaawansowane_tematy1[2]_82.gif

KN5_bardziej_zaawansowane_tematy1[2]_83.gif

Pierwszy argument FoldList musi być dwuargumentową funkcją. Poniższe przykłady ilustrują działanie FoldList:

KN5_bardziej_zaawansowane_tematy1[2]_84.gif

KN5_bardziej_zaawansowane_tematy1[2]_85.gif

KN5_bardziej_zaawansowane_tematy1[2]_86.gif

KN5_bardziej_zaawansowane_tematy1[2]_87.gif

Zwróćmy uwagę na jeszcze jedną podobną funkcję:

KN5_bardziej_zaawansowane_tematy1[2]_88.gif

KN5_bardziej_zaawansowane_tematy1[2]_89.gif

KN5_bardziej_zaawansowane_tematy1[2]_90.gif

KN5_bardziej_zaawansowane_tematy1[2]_91.gif

Oczywiście ten sam wynik można uzyskać przy pomocy poznanej chwilę wcześniej, bardziej ogólnej funkcji FoldList:

KN5_bardziej_zaawansowane_tematy1[2]_92.gif

KN5_bardziej_zaawansowane_tematy1[2]_93.gif

Warto jednak wiedzieć, że bardziej wyspecjalizowana funkcja Accumulate działa szybciej, zatem lepiej używać jej, jeśli pracujemy na numerycznych argumentach:

KN5_bardziej_zaawansowane_tematy1[2]_94.gif

KN5_bardziej_zaawansowane_tematy1[2]_95.gif

KN5_bardziej_zaawansowane_tematy1[2]_96.gif

KN5_bardziej_zaawansowane_tematy1[2]_97.gif

KN5_bardziej_zaawansowane_tematy1[2]_98.gif

KN5_bardziej_zaawansowane_tematy1[2]_99.gif

KN5_bardziej_zaawansowane_tematy1[2]_100.gif

KN5_bardziej_zaawansowane_tematy1[2]_101.gif

KN5_bardziej_zaawansowane_tematy1[2]_102.gif

Programując w Mathematice, często wykorzystuje się fakt, że wyspecjalizowane funkcje są szybsze od swoich bardziej ogólnych odpowiedników.

Block i zmienne globalne.

Konstrukcji Block używamy najczęściej, gdy chcemy tylko na pewien czas zmienić wartości zmiennych globalnych. Na przykład zmienna globalna $ RecursionLimit ma nast&#281;puj&#261;c&#261; domy&#347;ln&#261; warto&#347;&#263;:  </p></p>
<p><p class="Input">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_103.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_103.gif" width="146" height="18" style="vertical-align:middle" /> </p></p>
<p><p class="Output">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_104.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_104.gif" width="29" height="18" style="vertical-align:middle" /> </p></p>
<p><p class="Text">  Oznacza to, &#380;e p&#281;tla, w kt&oacute;rej d&#322;ugo&#347;&#263; rekursji przekroczy 256 krok&oacute;w, zostanie automatycznie zatrzymana. Oczywi&#347;cie ma to u&#322;atwi&#263; wy&#322;apywanie b&#322;&#281;d&oacute;w programistycznych, kt&oacute;re bez tego ograniczenia prowadzi&#322;yby do niesko&#324;czonych p&#281;tli. Czasem jednak to ogranicznie jest niewygodne. Dla przyk&#322;adu wr&oacute;&#263;my jeszcze raz do dobrze nam znanej definicji: </p></p>
<p><p class="Input">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_105.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_105.gif" width="98" height="18" style="vertical-align:middle" /> </p></p>
<p><p class="Input">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_106.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_106.gif" width="588" height="40" style="vertical-align:middle" /> </p></p>
<p><p class="Text">  Spr&oacute;bujmy: </p></p>
<p><p class="Input">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_107.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_107.gif" width="88" height="18" style="vertical-align:middle" /> </p></p>
<p><p class="Message">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_108.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_108.gif" width="416" height="19" style="vertical-align:middle" /> </p></p>
<p><p class="Message">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_109.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_109.gif" width="416" height="19" style="vertical-align:middle" /> </p></p>
<p><p class="Output">  <img src="/sites/default/files/images/mpk-KN5_bardziej_zaawansowane_tematy1[2]_110.gif" alt="KN5_bardziej_zaawansowane_tematy1[2]_110.gif" width="894" height="40" style="vertical-align:middle" /> </p></p>
<p><p class="Text">  Ograniczenie zmiennej  $RecursionLimit do 256 powoduje, że nasz kod nie chce działać. Moglibyśmy zwiększyć wartość $ RecursionLimit albo wr&#281;cz ustali&#263; j&#261; na <span><em>&infin;</em></span>, tym samym ca&#322;kowicie usuwaj&#261;c to ograniczenie. Jednak post&#281;puj&#261;c w ten spos&oacute;b, nara&#380;amy si&#281; na nieprzyjemne konsekwencje w przysz&#322;o&#347;ci - zmienimy lub usuniemy domy&#347;lne ograniczenie na rozmiar p&#281;tli nie tylko w naszym programie obliczaj&#261;cym liczby Fibonacciego, ale r&oacute;wnie&#380; we wszystkich innych programach. Znacznie bezpieczniej jest zmieni&#263; tymczasowo warto&#347;&#263;  $RecursionLimit, np. używając konstrukcji Block. Zanim jednak to zrobimy, musimy usunąć wszystkie definicje Fib, ponieważ Mathematica zapamiętała “zatrzymane” wartości (wartości zawierające Hold, takie jak ta w ostatnim wyniku powyżej).

KN5_bardziej_zaawansowane_tematy1[2]_111.gif

KN5_bardziej_zaawansowane_tematy1[2]_112.gif

KN5_bardziej_zaawansowane_tematy1[2]_113.gif

KN5_bardziej_zaawansowane_tematy1[2]_114.gif

Zauważmy, że globalna wartość $RecursionLimit pozostała w tym przypadku niezmieniona:

KN5_bardziej_zaawansowane_tematy1[2]_115.gif

KN5_bardziej_zaawansowane_tematy1[2]_116.gif

Przykład: symulacja ruchu Browna

Jako przykład użycia funkcji FoldList, NestList oraz Accumulate podajemy konstrukcję symulacji ruchu Browna (procesu Wienera). W dziewiątej wersji Mathematiki ta konstrukcja stała się znacznie łatwiejsza dzięki nowym wbudowanym funkcjom RandomFunction oraz WienerProcess. Kod, który podajemy poniżej, działa w wersjach 6 i wyżej.

Jedna ścieżka

Ścieżkę ruchu Browna (przebytą w jednostce czasu) przybliżamy przez losowe błądzenie z n krokami, gdzie każdy krok jest liczbą rzeczywistą o rozkładzie normalnym ze średnią 0 i odchyleniem standardowym KN5_bardziej_zaawansowane_tematy1[2]_117.gif. Istnieje szereg sposobów zaprogramowania tego w Mathematice. Podajemy poniżej trzy  z nich.

Accumulate (najszybsza metoda):

KN5_bardziej_zaawansowane_tematy1[2]_118.gif

FoldList (nieco powolniejsza):

KN5_bardziej_zaawansowane_tematy1[2]_119.gif

NestList (najwolniejsza)

KN5_bardziej_zaawansowane_tematy1[2]_120.gif

KN5_bardziej_zaawansowane_tematy1[2]_121.gif

KN5_bardziej_zaawansowane_tematy1[2]_122.gif

Wiele ścieżek

KN5_bardziej_zaawansowane_tematy1[2]_123.gif

KN5_bardziej_zaawansowane_tematy1[2]_124.gif

KN5_bardziej_zaawansowane_tematy1[2]_125.gif

KN5_bardziej_zaawansowane_tematy1[2]_126.gif

KN5_bardziej_zaawansowane_tematy1[2]_127.gif

KN5_bardziej_zaawansowane_tematy1[2]_129.gif