Zadania do wykładu o procedurach i funkcjach

Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowa

Perl: programowanie - procedury i funkcje

Uwaga. Wszystkie programy należy napisać z obecnymi w kodzie i aktywnymi pragmami use strict; oraz use warnings;. Można powiedzieć, że to dla waszego własnego bezpieczeństwa :) Jeżeli w zadaniu jest mowa o napisaniu funkcji, to oczywiście, najlepiej skrobnąć program, który z niej korzysta.

  1. Napisz prostą funkcję, która dodaje dwie liczby. Liczby powinny zostać przekazane jako argumenty (nie należy modyfikować zmiennych globalnych), a funkcja powinna zwrócić wynik będący ich sumą.
    Oto kod, który jest taką funkcją (zapisaną trochę w stylu C): sub dodaj { my $liczba1 = shift(@_); my $liczba2 = shift(@_); my $wynik = $liczba1 + $liczba2; return($wynik); } Funkcję tę można jednak trochę odchudzić, innymi słowy - możemy napisać ją nieco bardziej oszczędnie, przy zachowaniu tej samej funcjonalności. Po pierwsze, nie trzeba używać nawiasów przy shift - operacja ta pobiera argument funkcji, ale nawiasy nie są wymagane (w perlu w ogóle rzadko kiedy wymagane są nawiasy). Co więcej, można pominąć nawet dokładne pisanie CO mamy shiftować - perl domyśli się, że chodzi o zmienną @_, jeżeli napiszemy po prostu samo shift. Dodatkowo tworzenie zmiennej $wynik tylko po to, aby go od razu zwrócić w instrukcji return jest zwykłą stratą czasu. Można od razu do funkcji return przekazać wyrażenie które obliczy sumę. Zatem: sub dodaj { my $liczba1 = shift; my $liczba2 = shift; return $liczba1 + $liczba2; } Tym razem jest krócej, ale można jeszcze bardziej odchudzić kod. Na przykład, zamiast wykonywać dwie instrukcje shift można nie wykonywać żadnej! Wystarczy wykorzystać przypisanie listowe (w perlu można przypisać do listy zmiennnych inną listę) i napisać: sub dodaj { my($liczba1,$liczba2) = @_; return $liczba1 + $liczba2; } Ten kod nadal nie jest optymalny, ponieważ używamy tutaj dwóch zmiennych, które są tylko po to, aby zapisać w nich wartość a następnie wyliczyć sumę. Użycie tych zmiennych nie jest konieczne, ponieważ już mamy wszystkie dane, które potrzebujemy. Są one w tablicy argumentów funkcji, i wystarczy je tylko wydobyć. Możemy zatem napisać tak: sub dodaj { return shift(@_) + shift(@_); } co nadal działa, a to dlatego, że wpisywanie danych do zmiennych zastąpiliśmy sumowaniem bezpośrednim argumentów shiftowanych bezpośrednio z tablicy argumentów funkcji. Można jednak uniknąć tej operacji shiftowania, gdyż i ona jest nadmiarowa. Wystarczy przypomnieć sobie, że tablica argumentów funkcji to zwykła tablica o nazwie _, czyli @_. Dowolny element tej tablicy możemy pobrać bezpośrednio, przez odwołanie się do niego poprzez indeks. Tutaj potrzebujemy dwóch pierwszych argumentów, czyli indeksami jest 0 oraz 1. Można zatem napisać $_[0] + $_[1] i to także będzie suma dwóch liczb podanych jako argumenty! Oto kod: sub dodaj{ return $_[0] + $_[1]; } To już prawie najkrótsza wersja, ale można jeszcze coś wyciąć, pozostawiając samo sedno. Funkcje perla mają taką właściwość, że można pominąć instrukcję return. Wtedy wartością funkcji będzie ostatnio obliczona wartość, zatem można naszą sumę umieścić po prostu w kontekście pustym, a i tak zostanie ona obliczona i zwrócona jako wynik: sub dodaj { $_[0] + $_[1] } I to jest końcowa, najszybsza, gotowa postać funkcji dodającej dwie liczby. Oczywiście, jeżeli jako argumenty podamy teksty, to wynikiem będzie nie suma tekstów, ale błąd wykonania programu. Ale to jest już jakby trochę inna sprawa: zabezpieczenie się przed wszystkimi możliwymi błędami na tym etapie raczej spowoduje wzrost objętości kodu i spadek czytelności i szybkości działania. Lepiej martwić się o odpowiednie argumenty dla takiej funkcji wcześniej, a nie dopiero podczas sumowania.
  2. Napisz prostą funkcję która dzieli dwie liczby. Parametry do funkcji powinny zostać przekazane przez referencje do zmiennych. Jeżeli dzielenie jest niemożliwe z tego powodu, że dzielnik (co to jest dzielnik?) jest zerem, funkcja powinna zwrócić wartość NaN (co to za wartość?)
    Oto funkcja, która wykona dzielenie dwóch zmiennych przekazanych przez referencje. Zakładamy, że referencje te są referencjami do zmiennych skalarnych (inaczej operacja dzielenia się nie powiedzie). sub podziel { my ($dzielna,$dzielnik) = @_; if($$dzielnik == 0){ return "NaN"; } else{ return $$dzielna / $$dzielnik } } Na uwagę zasługuje tutaj przetwarzanie zmiennych. Zmienne $dzielna oraz $dzielnik to zmienne skalarne, które jednak nie zawierają liczb, tylko referencje do innych zmiennych (tak określono wymagania w zadaniu). Zatem operacja dodawania odbywa się na referencjach, ale nie można w perlu dodawać referencji. Zamiast tego, przeprowadzana jest tuż przed dzieleniem operacja dereferencji, która polega na uzyskaniu dostępu do zmiennej wskazywanej przez referencję (można o tym myśleć podobnie jak o wyłuskaniu zmiennej wskazywanej przez wskaźnik). Dereferencja zmiennej skalarnej, która wskazuje na skalar przeprowadzana jest bardzo prosto, poprzez zapisanie znaku dolara przed samą referencją: zamiast $x należy użyć $$x. Taka technika jest zastosowana w funkcji. Wywołanie tej funkcji także nie jest takie trywialne, ponieważ nie przyjmie ona liczb w swojej liczbowej postaci. Zamiast tego zmienne podane jako argumenty przekazać trzeba przez referencje, a tworzy się przez postawienie odwrotnego ukośnika przed nazwą zmiennej. Oto przykładowe wywołanie: $a = 1; $b = 3; $c = podziel( \$a, \$b );
  3. Napisz funkcję obliczającą sumy wszystkich odpowiadających sobie elementów dwóch zwykłych tablic przekazanych jako referencje. Wynikiem funkcji powinna być lista zsumowanych elementów. Pamiętaj, że długość przekazanych tablic może być niejednakowa! Uodpornij funkcję na różnie dziwne przypadki (np. puste tablice, itp.).
    Zadanie to jest proste do wykonania, jeżeli pamięta się, jak przeprowadza się operacje na tablicach. Oto przykładowy kod, który iteruje po obu tablicach tyle razy, ile wynosi dłuższa z nich, i sumuje w bezpieczny sposób elementy. sub sumujtablice { my $tab1 = shift; # pierwsza tablica dana jako referencja my $tab2 = shift; # druga tablica, rowniez jako referencja my @tabW = (); # tablica wynikowa na sumy elementow for(my $i=0; $i <= (($#$tab1 > $#$tab2) ? $#$tab1 : $#$tab2); $i++){ $tabW[$i] = (defined $tab1->[$i] ? $tab1->[$i] : 0) + (defined $tab2->[$i] ? $tab2->[$i] : 0); } return @tabW; } W tej funkcji w sumie najważniejsze jest to, że pracujemy cały czas z referencjami, zatem nie piszemy po prostu $tab1[$i], ale $tab1->[$i]. Kolejna sprawa związana jest z pętlą for. Pętla ta wykonuje się od 0 do liczby będącej długością dłuższej z tablic. Zostało to zapisane w jednym wyrażeniu, jako porównanie indeksu ostatniego elementu każdej z tablic: ($#$tab1 > $#$tab2) ? $#$tab1 : $#$tab2. Zapis $# w przypadku tablicy oznacza indeks ostatniego jej elementu, zatem tutaj porównujemy ostatnie indeksy i wybieramy większy z nich. Można zamiast takiego wyrażenia napisać po prostu scalar @{$tab1}. Dodatkowa sprawa znowu związana jest z referencjami. W zapisie $#$tab1 odbywa się dereferencja zmiennej $tab1, a pełen zapis ma postać $#{$tab1}. Tutaj jednak można go skrócić do formy beznawiasowej. Wynikiem jest to samo, co otrzymujemy dla zwykłej tablicy (np. @a) po zapisaniu $# (np. $#a).
  4. Napisz funkcję, której deklaracja w języki C-podobnym mogłaby wyglądać np. tak: integer prompt(string). Zadaniem funkcji jest wczytanie liczby ze standardowego wejścia. Jeżeli standardowe wejście nie jest terminalem, nie należy wypisywać komunikatu tylko wczytać dane po cichu. :) Zwracana liczba nie może być zakończona znakiem nowego wiersza.
    Taka funkcja może być bardzo przydatna w przypadku pisania programów prowadzących dialog z użytkownikiem. Aby jednak dialog ten był anulowany w przypadku, gdy wejściem/wyjściem nie jest terminal, należy wykorzystać operator testowania pliku omawiany wcześniej - -t, który sprawdza, czy dany plik jest skojarzony z wyjściem terminala, czyli, czy wysłanie znaku do niego, spowoduje pojawienie się tego znaku na ekranie (upraszczając). Oto definicja funkcji: # funkcja prompt - wczytuje liczbe proszac o nia komunikatem sub prompt { my $string = shift || ''; # napis poprzedzajacy wczytanie liczby my $liczba = ''; if( -t \*STDOUT ){ print $string; # wypisanie prosby jezeli terminal dziala } $liczba = <STDIN>; # wczytanie liczby chomp $liczba; # usuniecie opcjonalnego znaku nowej linii return int $liczba; # zwracamy wylacznie calkowita liczbe }
  5. Aby się nie nudziło - zrób program, który zawiera dwie funkcje obliczające silnię (wiem że to straszliwie oklepana klasyka, aż mnie mdli). Jedna z nich powinna działać rekurencyjnie, druga iteracyjnie. Program powinien być napisany z użyciem pragmy use strict;. Jaka jest największa wartość n, dla którego w perlu można obliczyć wartość n! ?
    Oto rekurencyjna funkcja silnia: use strict; sub rek_silnia { my $n = shift || 1; return ($n > 1) ? rek_silnia($n-1)*$n : 1; } Wersja iteracyjna: use strict; sub silnia { my $n = shift || 1; my $silnia = 1; for(my $i=$n; $i>0; $i--){ $silnia *= $i; } return $silnia; }
  6. Dla osób, które używały już modułu Benchmark - porównaj prędkości wykonania obu funkcji silnia - iteracyjnej i rekurencyjnej. Zastanów się która powinna być szybsza i dlaczego, a następnie sprawdź wyniki.
    Porównanie szybkości dwóch funkcji zapisanych tak jak powyżej daje do myślenia. Oto, obliczenie wartości silni z liczby 20, po uśrednieniu 100000 przebiegów wykazuje, że wersja iteracyjna jest prawie 200% szybsza :) Oto wyniki: Rate rek itr rek 50505/s -- -67% itr 151515/s 200% -- Program, który porównuje szybkości działania obu tych funkcji jest bardzo prosty: #!/usr/bin/perl -w use strict; use Benchmark; sub silnia_rek { my $n = shift || 1; return ($n > 1) ? silnia_rek($n-1)*$n : 1; } sub silnia_ite { my $n = shift; my $s = 1; for(my $i=$n; $i > 0; $i--){ $s *= $i; } return $s; } Benchmark::cmpthese(100000,{ rek => sub{ silnia_rek(20); }, itr => sub{ silnia_ite(20); }, }); Należy mieć na uwadze, że wyniki pomiarów będą się różnić w zależności od maszyny, systemu, wersji perla, itp. czynników. Dlatego metoda nie nadaje się do pomiaru prędkości rzeczywistej działania kodu (są inne sposoby), natomiast sprawdza się przy porównywaniu wzajemnym szybkości działania funkcji.
  7. Innym straszliwie oklepanym zadaniem jest napisanie funkcji obliczającej n-ty element ciągu Fibonacciego. Napisz taką funkcję, a następnie oblicz element dla n=100. Funkcja może być napisana rekurencyjnie lub iteracyjnie. Dla zaawansowanych programistów perla: w przypadku wersji rekurencyjnej wyjaśnij, dlaczego jej wydajność jest niska. Następnie użyj modułu Memoize, aby poprawić wydajność funkcji i sprawdź za pomocą modułu Benchmark o ile jest szybsza.
    Wartość setnej liczby Fibonacciego to 354224848179261915075 i jej obliczenie zajmuje programowi z własnym cachem mniej niż 0.1s (na moim komputerze). Programy które zostały zbadane były trzy. Wersja oryginalna funkcji rekurencyjnej (jej możliwości czasowe wyczerpują cierpliwość zwykłego człowieka przy parametrze w granicach 30), wersja przyspieszana modułem Memoize oraz wersja korzystająca z własnego rozwiązania, które jak widać z pomiarów czasu jest szybkie jak błyskawica: Rate fib_origin fib_memoiz fib_cached fib_origin 557/s -- -100% -100% fib_memoiz 152439/s 27266% -- -86% fib_cached 1075269/s 192933% 605% -- Oto kod funkcji rekurencyjnej bez żadnych modyfikacji, ten, który okazał się najwolniejszy: # fibonacci orginalny (fib_origin) w testach sub fib1 { my $n = shift; return $n if $n < 2; fib1($n-1) + fib1($n-2); } Kod funkcji Fibonacciego który był przyspieszany przez moduł Memoize wyglądał dokładnie tak samo, z tym, że była to funkcja o nazwie fib2, aby możliwe było wykonanie memoize('fib2') bez ingerencji w pierwszą funkcję. W testach ta funkcja ma nazwę fib_memoiz. Kod funkcji korzystającej z własnego stosu obliczonych poprzednich wartości wygląda tak: { # fibonacci z wlasnym cache (fib_cached w testach) my @cache; sub fib3 { my $n = shift; return $cache[$n] if defined $cache[$n]; return $cache[$n] = $n if $n < 2; $cache[$n] = fib3($n-1) + fib3($n-2); } } Jak widać z kodu, wykorzytuje on prostą, trywialną tablicę do przechowywania wyników. Dla wartości jakiegoś $n wynik funkcji jest pamiętany w położeniu $cache[$n]. Jeżeli w tablicy nie ma wyliczonej wartości, jest ona obliczana, a w przeciwnym wypadku zwracana jest wartość wprost z tablicy. Taka technika powoduje KOLOSALNE przyspieszenie działania funkcji (o dobrych kilka rzędów) :) Wszystko dlatego, że wartość funkcji dla dowolnego $n jest liczona naprawdę tylko jeden raz. Działanie modułu Memoize jest podobne, z tym, że stosuje on inną technikę przechwytywania wyników, i na skutek tego są trochę gorsze osiągi. Intefrejs zapewniany przez Memoize jest jednak uniwersalny i za jego pomocą można przyspieszać funkcje przyjmujące wiele różnych parametrów.
  8. Napisz funkcję Ackermanna i oblicz kilka elementów dla niewielkich wartości argumentów. Możesz dodać do funkcji jakieś polecenia wypisujące przebieg obliczeń, aby obserwować co się dzieje wewnątrz programu.
    Jak widać jest to przykład dość prostej, a jednocześnie niezwykle ciekawej funkcji. Dla wartości argumentów (4,2) wartość tej funkcji przewyższa podobno liczbę cząsteczek we wszechświecie podniesioną do dwusetnej potęgi... Podobno, ponieważ na razie nie wiadomo ile jest cząsteczek we wszechświecie :-P. Prosty jest kod, który ją implementuje: sub ack { my $x = shift; my $y = shift; print "$x:$y "; return $y + 1 if $x == 0; return ack($x-1,1) if $y == 0; return ack($x-1,ack($x,$y-1)); } Funkcja zawiera polecenie print, dzięki któremu wyświetlić można wartości pośrednie zmiennych $x oraz $y. Można wtedy zaobserwować ile razy wykonują się wywołania rekurencyjne. Oto kilka przebiegów: ackermann.pl 1 1 1:1 1:0 0:1 0:2 =3 ackermann.pl 2 1 2:1 2:0 1:1 1:0 0:1 0:2 1:3 1:2 1:1 1:0 0:1 0:2 0:3 0:4 =5 ackermann.pl 2 2 2:2 2:1 2:0 1:1 1:0 0:1 0:2 1:3 1:2 1:1 1:0 0:1 0:2 0:3 0:4 1:5 1:4 1:3 1:2 1:1 1:0 0:1 0:2 0:3 0:4 0:5 0:6 =7 Oczywiście tak samo jak w przypadku funkcji Fibonacciego, także i tutaj można zastosować memoizację lub cachowanie wyników pośrednich, aby nie obliczać niepotrzebnie wartości już raz obliczonych. Nie pomoże to jednak poprawić czasu wykonania, gdyż przyspieszenie o kilka rzędów jest niczym wobec ogromu pracy, jaki funkcja wykona na przykład dla parametrów 5,5. Można zająć się czymkolwiek w czasie obliczeń, z gwarancją, że prawdopodobnie prędzej się świat skończy, niż funkcja wyliczy prawidłowy wynik na komputerze :)
  9. Napisz funkcję Debug, która użyta z jakimkolwiek odwołaniem do zmiennej lub stałej, wypisze rekurencyjnie jej zawartość. Do wypisywania danych możesz użyć modułu Data::Dumper. Zadbaj o ewentualne formatowanie wyników.
    Ponieważ wolno użyć modułu Data::Dumper, jedyne, co należy zrobić, to opakować własną funkcją wywołanie metody Dumper. Można to zrobić np. tak: sub Debug { my $ref = shift; use Data::Dumper; # ładujemy lokalnie moduł Data::Dumper - to działa local Data::Dumper::Indent = 1; print Dumper $ref; } ...i to w zasadzie cała funkcja. Ustawienie zmiennej Indent bezpośrednio w pakiecie Data::Dumper jest złą i oficjalnie niepolecaną techniką programowania naruszającą zasadę enkapsulacji, i w zasadzie należałoby ją zastąpić przez wywołanie metody obiektowej, ale wtedy również i użycie całego modułu musiałoby być obiektowe. Szczegóły opisane są w dokumentacji modułu Data::Dumper.
  10. Używając modułu Benchmark sprawdź, czy wywołanie funkcji F (którą trzeba napisać, może ona nic nie robić) za pomocą referencji $f zdefiniowanej tak: $f = \&F;, gdzie wywołanie ma postać $f->(); jest tak samo szybkie, jak wywołanie funkcji bezpośrednie (F();).
    Funkcja F zdefiniowana została tak: sub F { } w kodzie utworzono do niej referencję za pomocą: my $f = \&F; i wykonano porównanie czasów 100_000_000 wykonań funkcji F() oraz $f->() za pomocą modułu Benchmark. Wyniki są w poniższej tabelce. (Zapis 100_000_000 działa w perlu - ze znakami podkreślenia, sprawdź).
  11. * Wykorzystując szablony funkcji, stwórz operator skalarny sqr, który będzie zwracał kwadrat swojego argumentu. Operator ten ustawiony w liście powinien działać tylko na jeden najbliższy sobie argument: (1,2,3,4,sqr 5,6,7,8), co powinno dać listę (1,2,3,4,25,6,7,8). Mówiąc prosto, postaraj się ograniczyć zachłanność perla w spłaszczaniu argumentów do płaskiej listy i przekazywania ich tylu do funkcji, ile wlezie.
    Szablony funkcji to swego rodzaju namiastka typowania zmiennych wprowadzanych do funkcji. Na przykład funkcje push, pop, i inne wymagają podania w parametrach tablicy (zawsze tablicy, nie np. listy). Inne z kolei działają tylko na argumentach, które są skalarmi, jeszcze inne tylko na listach, itp. Aby takie funkcje tworzyć, należy wykorzystać szablony funkcji. Są one podobne do nagłówka funkcji (umieszczanego w plikach *.h w programach C) lub do zapowiedzi wyprzedzającej (forward w Pascalu). W perlu wystarczy zapisać nagłówek funkcji a po nim zamiast definicji umieszczonej w bloku, jak to się zwykle robi, podać sam średnik. Perl będzie się spodziewał zdefiniowania funkcji później. Tak zdefiniowana funkcja może być wykorzystana jako operator, który nie wymaga podawania nawiasów. Oto przykłady, dzięki którym można to zagadnienie lepiej zrozumieć: sub add; Ten powyższy kod to zapowiedź funkcji, a nie jej definicja. Dzięki temu możemy pisać np. $a = add 2,3; i perl będzie wiedział co zrobić z zapisem add. Odpowiada to oczywiście wywołaniu add(2,3). Można określić liczbę argumentów, które taka funkcja będzie pobierała przez podanie pseudotypów zmiennych w nawiasie: sub add($$); Taki zapis informuje perla, że funkcja będzie pobierała dokładnie dwa argumenty skalarne. Umieszczenie takiej funkcji w liście danych spowoduje, że pobierze ona dwa najbliższe argumenty, prawostronnie, a pozostałe zostaną "nietknięte": @a = (1,2,3,4, add 1,2,3,4) Kod ten zachowa się tak, jakbyśmy napisali: @a = (1,2,3,4, 3, 3,4); ponieważ funkcja add zostanie obliczona tylko z dwoma argumentami. Bez specfikacji szablonu funkcji add($$) pobrane do funkcji zostałyby wszystkie liczby znajdujące się na liście po jej prawej stronie. Czy funkcja by je przetworzyła, to już inny problem :)
    W zadaniu chodzi o napisanie funkcji-operatora podnoszącego swój jedyny argument do kwadratu, zatem dobrym szablonem będzie np.: sub sqr($); Cały kod tej funkcji jest bardzo prosty i wygląda tak: sub sqr($){ return $_[0] * $_[0]; } Użycie takiej funkcji może wyglądać tak: $a = sqr $a; print join ',',(1,2,3,sqr 4,5,6); # 1,2,3,16,5,6 itp. Na uwagę zasługuje fakt, że wyrażenie sqr $b - 4*$a*$c NIE zostanie obliczone prawidłowo, dlatego że do funkcji sqr zostanie skierowana wartość całego wyrażenia, które obliczone zostanie wcześniej. Aby wymusić prawidłowe obliczenie np. delty trójmianu kwadratowego, należy mimo wszystko zastosować nawiasy: sqr($b) - 4*$a*$c.
  12. * Używając lokalnego, anonimowego bloku kodu stwórz funkcję, która w prywatnej zmiennej zlicza wszystkie swoje wywołania.
    Rozwiązanie tego zadania wymaga odrobiny pomysłowości, i sprowadza się do wykorzystania techniki programowania zwanej domknięciami. Termin pochodzi z języka LISP, a oznacza stworzenie lokalnego środowiska, które nie istnieje w miejscu wywołania funkcji, ale które jest przez funkcję "magicznie" pamiętane w momencie jej wywołania. Dzięki temu funkcja może mieć dostęp do zmiennych prywatnych, które już nie istnieją, a które były przez nią widziane w chwili definicji. Oto przykład: { # lokalny blok anonimowy - jest tu niezbędny my $count = 0; # lokalna zmienna leksykalna - nie istnieje poza blokiem sub funkcja { # ... jakies operacje $count++; # zliczenie wywołania funkcji } } Kod powyższy działa tak, że funkcję zdefiniowaną w lokalnym bloku widać w programie normalnie (ponieważ funkcja nie może być "lokalna" w takim sensie w jakim lokalna jest zmienna leksykalna). Zmienna $count zadeklarowana w bloku jest widoczna tylko w tym bloku, i nigdzie więcej. Funkcję można jednak wywołać z miejsca w programie, w którym nie widać już zmiennej $count. Okazuje się jednak, że zmienna ta jest widziana przez funkcję! :) No i co za tym idzie, funkcja ma do niej dostęp i może używać jej do pamiętania np. liczby swoich wywołań, jak w tym zadaniu. Tego typu zmienna widoczna tylko dla jednej funkcji jest także odpowiedniem zmiennej statycznej znanej z C, gdzie pewna informacja istnieje pomiędzy wywołaniami funkcji, chociaż jest w tej funkcji dostępna. W taki sposób można pamiętać stan, i wykorzystać ten efekt w programowaniu. Zdesperowani mogą nawet stworzyć pewną pseudo-obiektowość w ten sposób, ponieważ jest tutaj prawdziwa enkapsulacja i izolacja danych.
  13. * Utwórz iterator (za pomocą domknięć), który generuje kolejne liczby parzyste przy każdym swoim wywołaniu. O technice tworzenia domknięć możesz przeczytać w manualu perla (domknięcie to po ang. closure).
    Jest to kolejny przykład techniki stosowanej już w poprzednim zadaniu. Zamiast jednak korzystać z anonimowego bloku, można napisać funkcję, która zwraca funkcję korzystającą z lokalnego otoczenia. W ten sposób właśnie można napisać iterator strumienia liczb parzystych (lub nieparzystych), których ciąg zaczyna się od podanej liczby. Rozwiązanie jest dwuetapowe. Nalezy napisać funkcję, która tworzy lokalną zmienną zawierającą początek ciągu liczb, a potem w tym samym otoczeniu utworzyć funkcję, która inkrementuje tę liczbę i ją zwraca. Oto kod: sub create_iterator { my $start = shift; $start++ if $start % 2; # zapewniamy parzystosc liczby od ktorej zaczynamy return sub{ return $start+=2; } } # w tym momencie należy utworzyć iterator my $iterator = create_iterator(10); # zacznie generowac liczby od 10 print &$iterator; print &$iterator; W kodzie tworzymy zmienną skalarną, $iterator do której wpisujemy wynik działania funkcji create_iterator. Wynik ten jest referencją do kodu, a kod, jaki zwrócony został z create_iterator zawiera funkcję dodającą do lokalnej zmiennej $start wartość 2 i zwracającą wynik. Zmienna $start już nie istnieje w momencie wywoływania iteratora, ale jest magicznie nadal widziana ponieważ pochodzi ze środowiska w którym zdefiniowano iterator. Dzięki temu możliwe jest generowanie liczb w seriach, niezależnie od siebie z kilku różnych iteratorów.
  14. * Generowanie liczb pseudolosowych, realizowane przez rand polega na wykorzystaniu poprzednio wylosowanej liczby do generowania następnej. W przypadku, gdy potrzebne jest zastosowanie dwóch niezależnych generatorów, samo rand nie wystarcza, ponieważ liczby z niej uzyskane są zależne od siebie. Utwórz dwa generatory liczb pseudolosowych, które generują całkowicie niezależne serie liczb (podpowiedź: nie mogą one być oparte na rand). Użyj techniki domknięć.
    Generowanie liczb losowych jest samo w sobie ciekawym problemem. Tutaj napiszemy prosty generator liczb pseudolosowych, to znaczy takich, których sekwencje można przewidzieć, jeżeli wiadomo z jakiego równania pochodzą liczby. Osobie przyglądającej się pewnej sekwencji takich liczb będzie się jednak wydawało, że są to liczby "losowe" bo pozornie nic nie będzie ich łączyło. Aby stworzyć generator liczb losowych, należy posiadać liczbę będącą "zarodkiem", od której rozpocznie się cała sekwencja. Każda kolejna liczba jest wyliczana na podstawie poprzedniej (lub poprzednich). Dlatego losowanie jest powtarzalne (nie mają tej cechy algorytmy generowania ciągów losowych oparte na czasie). Jednak z takiego sposobu generowania liczb wynika problem zależności nowej liczby pseudolosowej od poprzedniej. Dlatego w zadaniu chodzi o zrobienie dwóch niezależnych generatorów liczb losowych. Oto kod, który najlepiej wyjaśni jak powinno wyglądać rozwiązanie: # generator generatora liczb losowych sub generuj_srand { my $seed = shift or time(); # zarodek generatora my $range = shift or 0xFFFF; # zakres liczb generowanych [0,$range) return sub { $seed = ($seed * 21 + 1) % $range; } } Powyższy kod tworzy funkcję generującą liczby pseudolosowe. Funkcja generuj_srand nie wymaga podania parametrów. Wtedy zwracana będzie funkcja, której ciąg losowy zostanie zainicjowany losową wartością opartą o czas systemowy, a zakres generowanych liczb będzie od 0 włącznie do 65535 (wyłącznie). Można jednak podać jeden lub dwa argumenty. Pierwszy z nich jest liczbą inicjującą zarodek liczb pseudolosowych. Drugi to zakres generowanych liczb. Aby wykorzystać tę funkcję do stworzenia generatorów, należy je utworzyć: # tworzenie niezaleznych generatorow liczb losowych my $gen1 = generuj_srand(undef,100); my $gen1 = generuj_srand(); my $gen2 = generuj_srand(1,10); Pierwszy generator ($gen1) będzie zwracał wartości liczbowe z zakresu [0,100), drugi z zakresu [0,65535) a trzeci z zakresu [0,10) (nawias kwadratowy oznacza przedział domknięty, a okrągły przedział otwarty, czyli bez krańcowej wartości). Dodatkowo, tylko trzeci generator będzie zwracał zawsze ten sam ciąg liczb, ponieważ tylko trzeci z nich inicjalizowany jest znaną i stałą wartością (1). Dwa pierwsze generatory będą inicjalizowane na podstawie czasu, i nigdy ciągi liczb otrzymane z nich nie będą takie same w kolejnych uruchomieniach (no dobrze, w kolejnych uruchomieniach następujących co najmniej co sekundę). Oto przykłady 10 liczb uzyskanych w dwóch kolejnych uruchomieniach z tych trzech generatorów: # liczby generowane przez generatory 1, 2 i 3, start pierwszy: gen1: 43 4 85 86 7 48 9 90 91 12 53 gen2: 10948 33304 44035 7246 21097 49828 63364 19945 25636 14077 33478 gen3: 2 3 4 5 6 7 8 9 0 1 2 # liczby generowane przez generatory 1, 2 i 3, start drugi: gen1: 51 72 13 74 55 56 77 18 79 60 61 gen2: 11956 54472 29818 36364 42760 46006 48637 38353 18994 5665 53431 gen3: 2 3 4 5 6 7 8 9 0 1 2 Jak widać na załączonym obrazku, jedynie ostatni generator generuje te same sekwencje liczb, co zostało wyjaśnione wcześniej. Dwa pierwsze generatory wygenerowały różne zestawy liczb ponieważ pomiędzy ich kolejnymi uruchomieniami upłynęło więcej czasu.
    Update: dostałem taką notkę od czytelników:
    Napisał Pan, że nigdy ciągi liczb otrzymane z tych generatorów nie będą takie same w kolejnych uruchomieniach (następujących co najmniej co sekundę). A co jeśli pierwszy generator zostanie wywołany co 100 sekund? Poza tym gdybyśmy chcieli użyć tego generatora generatora do generowania liczb z zakresu od 0 do liczby, która jest dzielnikiem liczby 21, np: my $gen3 = generuj_srand(undef,3); to generator ten będzie zwracał same jedynki. Dlatego lepiej by było zastąpić 21 jakąś liczbą pierwszą ($lp). Dodatkowo możnaby sprawdzać, czy $range % $lp == 0 i jeśli tak, to użyć innej liczby zamiast $lp (np. $lp+1). To zapewni, że wszystkie liczby z porządanego zakresu kiedyś wystąpią w generowanym ciągu. Oczywiście, jest całkowita racja i potwierdzam, że tak jest. Dobra uwaga.
Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowa - Perl - Zadania
[c] Piotr Arłukowicz, materiały z tej strony udostępnione są na licencji GNU.