======Proudy, vyrovnávací paměť====== Implicitní definice nekonečného proudu definice proudu, který v sobě používá proud, který sam� denuj� následujíc� prvk� proud� jso� přím� zaveden� pomoc� předchozíc� prvk� proud� be� vytvářen� pomocn� rekurzivn� procedur� (be� limitn� podmínky� nekonečn� prou� (define pow (let next ((last 1)) (cons-stream last (next (� � last ))))) implicitní definice předchozího (define pow2 (cons-stream � (stream-ma� (lambda (x) (� � x)� pow2))� Ukázka implicitních definic proudů proud faktoriálů (define fak-stream (cons-stream � (stream-ma� � fak-strea� (stream-cd� naturals)))� prou� Fibonaccih� číse� (define fib-stream (cons-stream � (cons-stream � (stream-ma � fib-stream (stream-cdr fib-stream))))� Konstruktor nekonečných proud� nekonečný proud� lze vytvářet proceduro� build-strea� analogick� proceduř� build-list� al� nem� limitn� podmínk� (nen� potřeb� předáva� délk� vytvářenéh� streamu� ;� konstrukto� build-strea� (define build-stream (lambda (f) (let pro� ((� 0)� (cons-strea� (� i� (pro� (� � 1)))))� Příklad� (define one� (build-stream (lambda (i) 1))� (define natural� (build-stream (lambda (i) (� � 1)))� Příklady manipulace s nekonečnými proudy ;; vytváření nekonečných proudů z nekonečných proudů ;; aplikací po sobě jdoucích funkcí na každý prvek (define expand-stream (lambda (stream . modifiers) (let next ((pending modifiers)) (if (null? pending) (apply expand-stream (stream-cdr stream) modifiers) (cons-stream ((car pending) (stream-car stream)) (next (cdr pending))))))) ;; příklady použití (expand-stream ones - +) ;=> proud: -1 1 -1 1    (expand-stream ones + -) ;=> proud: 1 -1 1 -1    (expand-stream naturals + -) ;=> proud: 1 -1 2 -2 3    Příklady manipulace s nekonečnými proudy vytvoření proudu celých čísel (define integers (build-stream (lambda (i) (if (= i 0) 0 ((if (even? i) + -) (quotient (+ i 1) 2)))))) nebo použitím streamu přirozených čísel a expand-stream (define integers (cons-stream 0 (expand-stream naturals - +))) v obou případech dostáváme integers ;=> proud: 0 -1 1 -2 2 -3 3 -4 4 -5    Příklad� (nesprávné� manipulac� � nekonečným� proud� Následujíc� m� smys� pouz� poku� j� s� konečný� (defin� stream-append� (lambd� (s� s2� (stream-fold� (lambd� (� y� (cons-strea� � (forc� y))� s� s1))� druh� prou� s� neuplatní� protož� prvn� j� nekonečn� (stream-appen� one� (stream-ma� � ones)� následujíc� bud� cykli� (stream-lengt� ones� počíta� délk� (nekončeného� stream� j� nesmysl� neexistuj� algoritmu� (� nikd� existova� nebude)� kter� b� pr� dan� strea� rozhodl� zda-l� j� konečn� č� nikoli� Prou� racionálníc� číse� můžem� vytvoři� � prou� všec� racionálníc� číse� využijem� faktu� ž� všechn� kladn� racionáln� čísl� jso� zapsán� � následujíc� tabulc� (každ� dokonc� nekonečn� mnoh� krát� � toho� ž� tabulk� můžem� projí� p� položkác� � diagonální� směr� POZNÁMKA� prou� všec� reálnýc� čísel� nelz� vytvoři� (!� Prou� racionálníc� číse� ;� prou� pár� (� � 1� (� � 1� (� � 2� (� � 1� � (defin� pair� (le� nex� ((su� 2� (� 1� (� 1)� (cons-strea� (con� � b� (i� (� � 1� (nex� (� su� 1� su� 1� (nex� su� (� � 1� (� � 1)))))� ;� prou� zlomk� 1/� 2/� 1/� 3/� 2/� 1/� � (defin� fraction� (stream-ma� (lambd� (x� (� (ca� x� (cd� x))� pairs)� kladn� racionáln� čísla� zbýv� odstrani� opakujíc� s� čísl� � fraction� (napříkla� 1/� j� toté� jak� 2/2� � podobně� Proud racionálních čísel ;� prou� kladnýc� racionálníc� číse� ;� stejn� čísl� jso� odstraněn� ltrac� (defin� positive-rational� (le� nex� ((f-strea� fractions)� (cons-strea� (stream-ca� f-stream� (nex� (stream-filte� (lambd� (x� (no� (� � (stream-ca� f-stream)))� f-stream))))� ;� � konečně� prou� všec� racionálníc� číse� ;� � -� � -� � -1/� 1/� -� � -1/� 1/� -� � -3/� 3/� � (defin� rational� (cons-strea� � (expand-strea� positive-rational� � +))� Kdy použít proudy? Kdy použít proudy místo seznamů? 1 2 kdy� potřebujem� řídi� průbě� výpočt� pomoc� da� kdy� nen� dopřed� znám� velikos� dat� kter� chcem� zpracovávat� neb� nen� možn� odhadnout� koli� da� budem� muse� zpracovat� ne� najdem� řešen� (nějakého� problém� Příklad� poku� s� budem� pokouše� nají� v� velké� soubor� sekvenc� nějakýc� znak� odpovídajíc� daném� vzoru� pa� nem� smys� natahova� cel� vstupn� soubo� d� paměti� co� můž� bý� dlouh� operac� (neb� � neprovediteln� operace)� protož� hledan� řetěze� můž� bý� třeb� někd� n� začátk� souboru� Typick� použit� proudů� řízen� vstupně/výstupníc� operac� prác� s� soubor� použív� mnoh� P� (napříkla� C++� m� ukážem� implementac� V/� operac� v� Schem� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pamě� 1� � 2� Vstupně/výstupn� operac� v� Schem� Scheme používá při manipulaci se soubory tzv. porty� port lze chápat jako identifikátor otevřeného souboru pro detaily viz specifikaci R6RS Příklad ukládáni dat do souboru (define � (open-output-file "soubor.txt")� (display "Ahoj svete!� p� (newlin� p� (displa� (ma� � '(� � � 4)� p� (newlin� p� (close-output-por� p� Příklad načítání dat ze souboru (define � (open-input-file "soubor.txt")� (display (read p)� (display (read p)� (display (read p)� (close-input-port p� Jednoduché vstupní proudy ;� vytvo� prou� čtení� výraz� z� vstupníh� port� (define input-port->stream (lambda (reader port� (let iter (� (let ((ele� (reader port))� (if (eof-object� elem� (begin (close-input-port port� '()� (cons-stream elem (iter))))))� ;; vytvoří proud otevřením souboru (define file->stream (lambda (reader file-name) (input-port->stream readr (open-input-file file-name)))) Zvýšení výpočetní efektivity pomocí proudů predikát equal-fringe? je pro dva seznamy pravdivý p. k. oba seznamy mají stejné atomické prvky pokud je projdeme zleva-doprava ;; přímočaré řešení, které je neefektivní (define equal-fringe? (lambda (s1 s2) (define flatten ; pomocná procedura: linearizace seznamu (lambda (l) (cond ((null? l) '()) ((list? (car l)) (append (flatten (car l)) (flatten (cdr l)))) (else (cons (car l) (flatten (cdr l))))))) (equal? (flatten s1) (flatten s2)))) ;; příklad použití: (equal-fringe? '(a (b (c)) () d) '(a b c (d))) ;=> #t equal-fringe? '(a (b (c)) () d) '(a b c (e))) ;=> #f ( Zvýšení výpočetní efektivity pomocí proudu V čem spočívá neefektivita předchozího řešení? 1 2 běhe� výpočt� s� konstruuj� lineárn� seznamy� kter� s� poto� použij� pouz� jednorázov� prediká� s� nechov� přirozeně� Poku� mám� dv� seznam� v� tvar� (� � � (� � pa� j� okamžit� jasné� ž� výslede� pr� n� b� mě� bý� #f� al� předchoz� procedur� j� ob� nejprv� cel� linearizuj� Odstraním� problé� č� 2� vstupn� seznam� budem� linearizova� d� proud� (t� jes� výsledke� linearizac� seznam� bud� prou� atomů� okamžit� budem� mí� � dispozic� nejlevějš� atom� ostatn� prvk� linearizovanéh� seznam� s� budo� hleda� a� kdy� přistoupím� � dalším� prvk� proud� vytvořím� prediká� n� tes� shod� dvo� konečnýc� proud� Zvýšení výpočetní efektivity pomocí proudů Každý příslib je roven pouze sám sobě: (define d (delay 1)) (equal? d d) ;=> #t (equal? (delay 1) (delay 1)) ;=> #f tím pádem: (equal? (stream 'a 'b 'c) (stream 'a 'b 'c)) ;=> #f proto zavádíme predikát shodnosti dvou proudů: (define stream-equal? (lambda (s1 s2) (or (and (null? s1) (null? s2)) (and (equal? (stream-car s1) (stream-car s2)) (stream-equal? (stream-cdr s1) (stream-cdr s2)))))) Zvýšen� výpočetn� efektivit� pomoc� proud� ;� témě� dokonal� verz� equal-fringe� (defin� equal-fringe� (lambd� (s� s2� ;; pomocné definice linearizace seznamu (define flatten (lambda (l) (cons ((null) l� '()� ((list� (car l)� (stream-append� (flatten (car l)) (flatten (cdr l)))) (else (cons-stream (car l� (flatten (cdr l))))))� ;; jsou lineární seznam� totožné� (stream-equal� (flatten s1� (flatten s2)))) Zvýšení výpočetní efektivity pomocí proudů Předchozí řešení má jeden malý problém Příklad, na kterém náš predikát selhává (define a '(a)) (set-cdr! a a) (define b '((b))) (set-cdr! b b) (equal-fringe? a b) ;=> 1 (cyklí) Odstranění problému (rozmyslete si proč): místo procedury stream-append2 vytvoříme makro (define-macro stream-append2 (lambda (s1 s2) `(let proc ((s ,s1)) (if (stream-null? s) ,s2 (cons-stream (stream-car s) (proc (stream-cdr s))))))) nový pohled: makro = procedura s líně vyhodnocenými argumenty Vyhodnocovací proces � vyrovnávací pamět� Modelov� progra� (define fib (lambda (n� (if (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2)))))) Výhody a nevýhody předchozího kódu/ výhoda� j� čist� napsan� (vznik� přepise� denic� b� čísla� nevýhoda� j� neefektivn� docház� k� zbytečném� opakován� výpočt� Otázka� Ja� zachova� čitelnos� kódu� al� zvýši� efektivit� výpočetníh� procesu� Vyhodnocovaci proces � vyrovnávac� pamět� ;; iterativni verze procedury ;; představuje zrychlení na úkor čitelnosti kódu (define fib (lambda (n) (let iter ((� 1� (� 1� (� n)� (if (<� � 1� � (ite� � (� � b� (� � 1)))))� Lepší řešení� zachováme původní kód procedury proceduru zabalíme do další procedury (memoize)� která bude mít svou vnitřní vyrovnávací paměť do ktere bude ukládat výsledky aplikací výchoz� procedur� odstraníme tak problém opakovaného provádění stejných výpočtů Vytvoříme proceduru empty-assoc � assoc� pr� správ� pamět� ;� prázdn� pamě� (defin� empty-asso� (lambd� (� (con� (con� #� #f� '()))� ;� destruktivn� zařa� nov� záznam/modiku� existujíc� (defin� assoc� (lambd� (asso� ke� val� (le� ite� ((a� assoc)� (con� ((null� as� (set-cdr� asso� (con� (con� ke� val� (cd� assoc)))� ((equal� (caa� as� key� (set-cdr� (ca� as� val)� (els� (ite� (cd� as))))))� Příklad zařazení nových záznamů: (define a (empty-assoc)) a ;=> ((#f . #f)) (assoc! a 'ahoj 10) a ;=> ((#f . #f) (ahoj . 10)) (assoc! a 'blah 20) a ;=> ((#f . #f) (blah . 20) (ahoj . 10)) (assoc! a 'ahoj 30) a ;=> ((#f . #f) (blah . 20) (ahoj . 30)) Vyhledávání lze provést pomocí klasického assoc (assoc 'blah a) ;=> (blah . 20) (assoc #f a) ;=> (#f . #f) Poznámka: pár (#f . #f) je vždy přítomen kvůli mutaci (KI, UP Olomouc) PP 2, Lekce 7 Proudy, vyrovnávací pamě´ 22 / 28 Vyhodnocovac� proce� � vyrovnávac� pamět� procedur� memoiz� vytvoř� obálk� na� dano� proceduro� (proved� memoizac� dan� procedury� každ� memoizovan� procedur� m� vlastn� pamě� pr� úschov� výsledk� př� volán� memoizovan� procedur� � ji� dřív� použitým� argument� j� výsledn� hodnot� vyhledán� � pamět� (defin� memoiz� (lambd� (f� (le� ((memor� (empty-assoc))� (lambd� called-with-arg� (le� ((foun� (asso� called-with-arg� memory))� (i� foun� (cd� found� (le� ((resul� (appl� � called-with-args))� (assoc� memor� called-with-arg� result� result))))))� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pamě� 2� � 2� ;� Fibonaccih� čísl� urychlen� pomoc� memoiz� (defin� fi� (memoiz� (lambd� (n� (i� (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2))))))� POZOR� následujíc� b� nefungovalo� (defin� fi� (lambd� (n� � původn� pomal� fi� (defin� fast-fi� (memoiz� fib)� (fast-fi� 32� bud� v� skutečnost� pomal� v� fast-fi� s� rekurzivn� vol� původn� procedur� be� cach� př� (fast-fi� 32� j� zapamatová� pouz� výslede� pr� 3� neved� k� kýženém� zrychlen� výpočt� Procedury s keší se chovají jinak než běžné procedury v případě použití vedlejšího efektu (let ((cntr 0)) (define modify (lambda (x) (set! cntr (+ 1 cntr)))) (modify #f) (modify #f) cntr) ;=> 2 (let ((cntr 0)) (define modify (memoize (lambda (x) (set! cntr (+ 1 cntr))))) (modify #f) (modify #f) cntr) ;=> 1 ;; vylepšen� verze� př� přeplněn� pamět� s� pamě� vysyp� (defin� make-memoiz� (lambd� limi� (lambd� (f� (le� ((memor� (empty-assoc)� (memory-siz� 0)� (lambd� called-with-arg� (le� ((foun� (asso� called-with-arg� memory))� (i� foun� (cd� found� (le� ((resul� (appl� � called-with-args))� (i� (an� (no� (null� limit)� (� memory-siz� (ca� limit))� (begi� (set� memory-siz� 0� (set� memor� (empty-assoc)))� (assoc� memor� called-with-arg� result� (set� memory-siz� (� memory-siz� 1)� result)))))))� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pamě� 2� � 2� ;� urychlen� fi� � pamět� � pět� buňkác� (defin� fi� ((make-memoiz� 5� (lambd� (n� (i� (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2))))))� Srovnán� počt� aktivac� vnitřn� procedur� př� dan� velikost� pamět� běhe� výpočt� (fi� 32� velikos� pamět� 5� 2� 1� 1� � � � poče� aktivac� 3� 24� 27� 170� 698� 7518� 28712� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pamě� 2� � 2� Makr� pr� vytvářen� procedu� � keš� ;� globáln� konstant� udávajíc� velikos� pamět� (defin� *max-memory� 1000� ;� makr� kapp� (define-macr� kapp� (lambd� (arg� � body� `((make-memoiz� *max-memory*� (lambd� ,arg� ,@body)))� ;� příkla� použití� (defin� fi� (kapp� (n� (i� (<� � 2� � (� (fi� (� � 1)� (fi� (� � 2)))))� (KI� U� Olomouc� P� 2� Lekc� � Proudy� vyrovnávac� pamě� 2� � 2�