IB015 Neimperativní programování
Časová složitost, Typové třídy, Moduly
Jiří Barnat
Libor Škarvada
Sekce
Časová složitost
IB015 Neimperativní programování – 07 str. 2/37
Časová složitost algoritmu
Podstata
Časová složitost funkce popisuje délku výpočtu v nejhorším
případě vzhledem k velikosti vstupních parametrů.
Délka výpočtu v nejhorším případě
Maximální počet redukčních kroků přes všechny možné
výpočty aplikace programu na vstupní parametry stejné
velikosti.
IB015 Neimperativní programování – 07 str. 3/37
Časová složitost algoritmu
Podstata
Časová složitost funkce popisuje délku výpočtu v nejhorším
případě vzhledem k velikosti vstupních parametrů.
Délka výpočtu v nejhorším případě
Maximální počet redukčních kroků přes všechny možné
výpočty aplikace programu na vstupní parametry stejné
velikosti.
Na délce záleží!
IB015 Neimperativní programování – 07 str. 3/37
Funkce pro reverzi seznamu
Reverze seznamu funkce reverse’
reverse’ :: [a] -> [a]
reverse’ [] = []
reverse’ (x:s) = reverse’ s ++ [x]
(++) :: [a] -> [a] -> [a]
[] ++ t = t
(x:s) ++ t = x : (s++t)
Reverze seznamu funkce reverse
reverse :: [a] -> [a]
reverse = rev []
where rev s [] = s
rev s (x:t) = rev (x:s) t
IB015 Neimperativní programování – 07 str. 4/37
Reverze seznamu funkcí reverse’
reverse’ :: [a] -> [a]
reverse’ [] = []
reverse’ (x:s) = reverse’ s ++ [x]
(++) :: [a] -> [a] -> [a]
[] ++ t = t
(x:s) ++ t = x : (s++t)
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1]) ≡ [3,2,1]
IB015 Neimperativní programování – 07 str. 5/37
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 6/37
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 6/37
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1 + 2
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 6/37
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1 + 2 + 3 + ... + n
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 6/37
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1 + 2 + 3 + ... + n
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 6/37
Reverze seznamu funkcí reverse
reverse :: [a] -> [a]
reverse = rev []
where rev s [] = s
rev s (x:t) = rev (x:s) t
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 7/37
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 8/37
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1 + n
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 8/37
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1 + n + 1
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 8/37
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1 + n + 1
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 8/37
Asymptotický růst funkcí
Pozorování
Při určování časové složitosti algoritmů je nepraktické a často
i obtížné určovat tuto složitost přesně.
Funkce vyjadřující délku výpočtu vzhledem k velikosti
parametru klasifikujeme podle asymptotického chování.
Asymptotický růst funkcí
Při zápisu funkční hodnoty v proměnné n rozhoduje
nejrychleji rostoucí člen. U něj navíc zanedbáváme kladnou
multiplikativní konstantu.
Podle toho hovoříme o funkcích lineárních, kvadratických,
exponenciálních apod.
IB015 Neimperativní programování – 07 str. 9/37
Přehled asymptotických funkcí
t(n) růst funkce t
1, 20, 729, 264
konstantní
2 log n + 5, 3 log2 n + log2(log2 n) logaritmický
n, 2n + 1, n +
√
n lineární
n log n, 3n log n + 6n + 9 n log n
n2
, 3n2
+ 4n − 1, n2
+ 10 log n kvadratický
polynomiální
n3
, n3
+ 3n2
kubický
2n
1+
√
5
2
n
exponenciální
3n
IB015 Neimperativní programování – 07 str. 10/37
Asymptotická složitost reverse a reverse‘
reverse‘
Počet redukčních kroků výrazu reverse’ [x1,. . .,xn] na
každém seznamu délky n je
n + 1 + 1 + 2 + 3 + · · · + n =
n2 + 3n + 2
2
Složitost funkce reverse’ je kvadratická vzhledem k délce
obraceného seznamu.
reverse
Počet redukčních kroků výrazu reverse [x1,. . .,xn] na každém
seznamu délky n je
1 + n + 1 = n + 2
Složitost funkce reverse je lineární vzhledem k délce
obraceného seznamu.
IB015 Neimperativní programování – 07 str. 11/37
Časová složitost algoritmu a problému
Časová složitost algoritmu
Posuzuje konkrétní algoritmus.
Nevypovídá a jiných algoritmech pro řešení téhož problému.
Časová složitost problému
Daný problém je možné řešit různými algoritmy.
Složitost problému vypovídá a časové složitosti nejlepšího
možného algoritmu pro řešení problému.
Určovat složitost problému je výrazně obtížnější, než určování
složitosti algoritmu.
Bez znalosti složitosti problému nelze určit, zda daný
algoritmus pro řešení problému je optimální.
IB015 Neimperativní programování – 07 str. 12/37
Počítání mocniny
Definice funkcí
mocnina’ :: Int -> Int -> Int
mocnina’ m 0 = 1
mocnina’ m n = m * mocnina’ m (n-1)
mocnina :: Int -> Int -> Int
mocnina m 0 = 1
mocnina m n = if even n then r else m * r
where r = mocnina (m * m) (n ‘div‘ 2)
Složitost výpočtu vzhledem k exponentu
Složitost funkce mocnina’ je lineární.
Složitost funkce mocnina je logaritmická.
IB015 Neimperativní programování – 07 str. 13/37
Výpočet Fibonacciho číselné řady
Definice funkcí
fib’ :: Integer -> Integer
fib’ 0 = 0
fib’ 1 = 1
fib’ n = fib’ (n-2) + fib’ (n-1)
fib :: Integer -> Integer
fib = f 0 1
where f a _ 0 = a
f a b k = f b (a+b) (k-1)
Složitost vzhledem k argumentu
Složitost funkce fib’ je exponenciální.
Složitost funkce fib je lineární.
IB015 Neimperativní programování – 07 str. 14/37
Nejhorší případ 1/2
Pozor
Časová složitost popisuje délku výpočtu v nejhorším případě
pro danou velikost argumentu.
Příklad
Vyšetřujeme časovou složitost funkce ins vzhledem k jejímu
druhému parametru.
Funkce ins zařazuje prvek do seřazeného seznamu.
ins :: Int -> [Int] -> [Int]
ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t else y : ins x t
IB015 Neimperativní programování – 07 str. 15/37
Nejhorší případ 2/2
Různé délky výpočtu
Počet kroků při volání ins x [x1, ..., xn] je různý.
Nejkratší výpočet má délku 3:
ins 1 [2,4,6,8] 3
[1,2,4,6,8]
Nejdelší výpočet má délku 3n + 1:
ins 9 [2,4,6,8] 3∗4+1
[2,4,6,8,9]
Časová složitost
Časová složitost funkce ins je lineární vzhledem k velikosti
jejího druhého argumentu (tj. vzhledem k délce seznamu).
IB015 Neimperativní programování – 07 str. 16/37
Časová složitost a redukční strategie
Pozorování
Časová složitost závisí nejen na algoritmu (způsobu definování
funkce), ale také na redukční strategii.
Příklad
Uvažme funkcí pro uspořádání prvků v seznamu pomocí
postupného zařazování.
inssort :: Ord a => [a] -> [a]
inssort = foldr ins []
where ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t
else y : ins x t
Princip řazení funkcí inssort
inssort [x1, x2, ..., xn−1, xn]
foldr ins [] [x1, x2, ..., xn−1, xn]
n+1
ins x1 (ins x2 (...(ins xn−1 (ins xn []))...))
IB015 Neimperativní programování – 07 str. 17/37
Příklad závislosti časové složitosti na redukční strategii
Definice funkce
inssort :: Ord a => [a] -> [a]
inssort = foldr ins []
where ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t
else y : ins x t
minim = head . inssort
Striktní vyhodnocování (nejhorší případ – seznam je klesající)
minim [x1, ..., xn]
(head.inssort) [x1,...,xn]
head (inssort [x1,...,xn])
head (foldr ins [] [x1,...,xn])
n+1 head (ins x1 (...(ins xn−2 (ins xn−1 (ins xn[])))...))
3·0+1 head (ins x1 (...(ins xn−2 (ins xn−1 [xn]))...))
3·1+1 head (ins x1 (...(ins xn−2 [xn,xn−1])...) )
3·2+1 head (ins x1 (...[xn,xn−1,xn−2]...) )
...
3·(n−2)+1 head (ins x1 [xn,...,x2] )
3·(n−1)+1 head [xn,...,x1]
xn
IB015 Neimperativní programování – 07 str. 18/37
Příklad závislosti časové složitosti na redukční strategii
Definice funkce
inssort :: Ord a => [a] -> [a]
inssort = foldr ins []
where ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t
else y : ins x t
minim = head . inssort
Líné vyhodnocování (nejhorší případ – nejmenší prvek na konci)
minim [x1,...,xn]
(head.inssort) [x1,...,xn]
head (inssort [x1,...,xn])
head (foldr ins [] [x1,...,xn])
n+1 head (ins x1 (...(ins xn−2 (ins xn−1 (ins xn [])))...) )
head (ins x1 (...(ins xn−2 (ins xn−1 (xn : [])))...) )
3 head (ins x1 (...(ins xn−2 (xn : (ins xn−1 [])))...) )
3 head (ins x1 (...(xn : (ins xn−2 (ins xn−1 [])))...) )
...
3 head (ins x1 (xn :(ins x2 (ins x3 (...(ins xn−1 [])...)))))
3 head ( xn : (ins x1 (ins x2 (... (ins xn−1 [])...))))
xn
IB015 Neimperativní programování – 07 str. 19/37
Příklad závislosti časové složitosti na redukční strategii
Striktní vyhodnocování
Počet redukčních kroků výrazu minim [x1,...,xn] je:
3 + n + 1 +
n−1
k=0
(3k + 1) + 1 =
3n2 + n + 10
2
Při striktním vyhodnocování má funkce kvadratickou časovou
složitost.
Líné vyhodnocování
Počet redukčních kroků výrazu minim [x1,...,xn] je:
3 + n + 1 + 1 + 3.(n − 1) + 1 = 4n + 3
Při líném vyhodnocování má funkce lineární časovou složitost.
IB015 Neimperativní programování – 07 str. 20/37
Vliv redukční strategie na časovou složitost
Pozorování
Není pravda, že časová složitost výpočtu se při líném a
striktním vyhodnocování vždy liší.
Pokud se časová složitost liší, může se lišit víc než o jeden
řádek ve zmiňované tabulce asymptotických růstů funkcí.
Příklady
Konstantní (líně) versus exponenciální (striktně):
f n = const n (fib’ n)
Lineární líně i striktně:
length [a1,...,an]
IB015 Neimperativní programování – 07 str. 21/37
Sekce
Typové třídy
IB015 Neimperativní programování – 07 str. 22/37
Připomenutí klasifikace typů
Monomorfní typy
not :: Bool -> Bool
(&&) :: Bool -> Bool -> Bool
Polymorfní typy
length :: [a] -> Int
flip :: (a -> b -> c) -> b -> a -> c
Kvalifikované typy
(==), (/=) :: Eq a => a -> a -> Bool
sum, product :: Num a => [a] -> a
minimum, maximum :: Ord a => [a] -> a
print :: Show a => a -> IO ()
IB015 Neimperativní programování – 07 str. 23/37
Typové třídy
Význam
Identifikují společné vlastnosti různých typů.
Umožňují definici funkcí polymorfních typů zúžených na typy
požadovaných vlastností.
Programátorský význam
Definice a použití typových tříd umožňují sdílet kód funkcí,
které dělají totéž, avšak pracují s hodnotami různých typů.
Sdílení kódu funkcí, které dělají totéž,
by měl být svatý grál všech programátorů.
IB015 Neimperativní programování – 07 str. 24/37
Příklad typové třídy a jejího využití
Typová třída Eq
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y = not (x == y)
Přidružení typů k typové třídě (deklarace instance)
instance Eq Bool where
False == False = True
True == True = True
_ == _ = False
instance Eq Int where
(==) = primEqInt
instance (Eq a, Eq b) => Eq (a,b) where
(x,y) == (u,v) = x == u && y == v
IB015 Neimperativní programování – 07 str. 25/37
Využití typové třídy jinou typovou třídou
Typová třída Ord využívající typovou třídu Eq
class (Eq a) => Ord a where
(<=), (>=), (<), (>) :: a -> a -> Bool
max, min :: a -> a -> a
x >= y = y <= x
x < y = x <= y && x /= y
x > y = y < x
max x y = if x>= y then x else y
min x y = if x<= y then x else y
Deklarace instance
instance Ord Bool where
False <= _ = True
_ <= True = True
_ <= _ = False
instance (Ord a, Ord b) => Ord (a,b) where
(x,y) <= (u,v) = x < u || (x == u && y <= v)
IB015 Neimperativní programování – 07 str. 26/37
Přenos vlastností typu na složený typ
Pozorování
Instanciací lze přenést vlastnosti typu na složené typy.
Příklad
Rozšíření uspořadatelnosti hodnot typu na uspořadatelnost
seznamů hodnot daného typu.
instance (Ord a) => Ord [a] where
[] <= _ = True
(_:_) <= [] = False
(x:s) <= (y:t) = x < y || (x == y && s <= t)
IB015 Neimperativní programování – 07 str. 27/37
Obecná definice typové třídy a deklarace instance
Definice typové třídy
class (C1 a, . . . , Ck a) => C a





where op1 :: typ1...opn :: typn
default1...defaultm






Deklarace instance
instance (C1 a1, . . . , Ck ak) => C typ
where valdef1...valdefn
IB015 Neimperativní programování – 07 str. 28/37
Přetížení
Přetížení
Má-li třída více než jednu instanci, jsou její funkce přetíženy.
Přetížení operací
Jedna operace je pro několik různých typů operandů
definována obecně různým způsobem.
To, která definice operace se použije při výpočtu, závisí na
typu operandů, se kterými operace pracuje.
Srovnej s parametricky polymorfními operacemi, které jsou
definovány jednotně pro všechny typy operandů.
IB015 Neimperativní programování – 07 str. 29/37
Příklad přetížení operace
Typová třída Num
class (Eq a, Show a) => Num a where
(+), (-), (*) :: a -> a -> a
negate, abs, signum :: a -> a
Přetížení operací při deklaraci instancí
instance Num Int where
(+) = primPlusInt
...
instance Num Integer where
(+) = primPlusInteger
...
instance Num Float where
(+) = primPlusFloat
...
IB015 Neimperativní programování – 07 str. 30/37
Implicitní deklarace instance
Implicitní deklarace instance
V Haskellu lze deklarovat datový typ jako instanci typové třídy
(nebo více typových tříd) též implicitně, pomocí klausule
deriving v definici datového typu.
Při implicitní deklaraci instance se požadované funkce definují
automaticky podle způsobu zápisu hodnot definovaného typu
Funkce (==) se při implicitní deklaraci instance realizuje jako
syntaktická rovnost.
Příklad
data Nat = Zero | Succ Nat
deriving (Eq, Show)
IB015 Neimperativní programování – 07 str. 31/37
Sekce
Moduly a modulární návrh programů
IB015 Neimperativní programování – 07 str. 32/37
Modulární návrh
Motivace
Oddělení nezávislých, znovupoužitelných, logicky ucelených
částí kódu do separátních celků – modulů.
Zapouzdření
Při definici modulu je nutné explicitně vyjmenovat funkce,
které mají být viditelné a použitelné mimo rozsah modulu,
tzv. exportované funkce.
Ostatní funkce a datové typy definované v modulu nejsou
z vnějšku modulu viditelné.
Moduly by měly exportovat jen to, co je nutné.
Modul může exportovat hodnoty, typy a typové konstruktory,
typové a konstruktorové třídy, jména modulů.
IB015 Neimperativní programování – 07 str. 33/37
Definice Modulu v Haskellu
Obecná definice
module Jméno (export1, ..., exportn ) where



import M1 spec1
...
import Mm specm



globální_deklarace
Automatické doplnění definice
Není-li uvedena hlavička, doplní se
module Main (main) where
Nevyskytuje-li se mezi importovanými moduly M1,...Mm
modul Prelude , doplní se
import Prelude
IB015 Neimperativní programování – 07 str. 34/37
Main
Hlavní funkce
Program musí mít definovanou hlavní funkci – funkci main .
Právě jeden modul v programu musí být Main .
Modul Main
Modul Main musí exportovat hodnotu
main :: IO τ
pro nějaký typ τ, (obvykle τ = () ).
IB015 Neimperativní programování – 07 str. 35/37
Příklad modulu – Datový typ Fifo
Datový typ Fifo
Datový kontejner (struktura, která uchovává prvky)
přistupovaný operacemi vlož prvek a vyber prvek.
Prvky jsou z datové struktury odebírány v tom pořadí, ve
kterém byly vkládány.
First-In-First-Out = FIFO
Operace by měly mít konstantní časovou složitost.
Realizace v Haskellu
Definice modulu Fifo
Použití modulu:
import Fifo
IB015 Neimperativní programování – 07 str. 36/37
Příklad Modulu – Datový typ Fifo
module Fifo (FifoTyp, emptyq, headq, enqueue, dequeue) where
data FifoTyp a = Q [a] [a]
emptyq :: FifoTyp a
emptyq = Q [] []
enqueue :: a -> FifoTyp a -> FifoTyp a
enqueue x (Q h t) = Q h (x:t)
headq :: FifoTyp a -> a
headq (Q (x:_) _) = x
headq (Q [] []) = error "headq: prázdná fronta"
headq (Q [] t) = headq (Q (reverse t) [])
dequeue :: FifoTyp a -> FifoTyp a
dequeue (Q (_:h) t) = Q h t
dequeue (Q [] []) = error "dequeue: prázdná fronta"
dequeue (Q [] t) = dequeue (Q (reverse t) [])
IB015 Neimperativní programování – 07 str. 37/37