Transcript
Kapitel 5: Effizienz und Komplexität
Programmieren in Haskell
1
Analyse von insertionSort
insertionSort :: (Ord a) => [a] -> OrdList a insertionSort [] = [] insertionSort (a:as) = insert a (insertionSort as) insert :: (Ord a) => a -> [a] -> [a] insert a [] = [a] insert a (a’:as) | a <= a’ = a:a’:as | otherwise = a’:insert a as
Programmieren in Haskell
(insert.1) (insert.2) (insert.2.a) (insert.2.b)
2
(insert c) (d:z) ⇒ | c <= d | otherwise ⇒ | True | otherwise
= c:d:z
(insert.2)
= d:insert c z = c:d:z
(<=)
= d:insert c z
⇒ c : d : z
(insert.2.a)
beziehungsweise ⇒ | False | otherwise ⇒ d:insert c z
Programmieren in Haskell
= c:d:z
(<=)
= d:insert c z (insert.2.b)
3
T ime(insert c [])
=
1
T ime(insert c (d:z))
=
3,
T ime(insert c (d:z))
=
3 + T ime(insert c z),
Programmieren in Haskell
falls c 6 d falls c > d
4
T ime(insert c [])
=
1
T ime(insert c (d:z))
=
3,
T ime(insert c (d:z))
=
3 + T ime(insert c z),
falls c 6 d falls c > d
T ime(isort [])
=
1
T ime(isort (a:x))
=
1 + T ime(isort x ⇒ v) + T ime(insert a v)
Programmieren in Haskell
4
t_insertionSort :: (Ord a) => [a] -> (Int,OrdList a) t_insertionSort [] = (1,[]) t_insertionSort (a:as) = (t+u+1,ys) where (t,xs) = t_insertionSort as (u,ys) = t_insert a xs t_insert :: (Ord a) => a -> [a] -> (Int,[a]) t_insert a [] = (1,[a]) t_insert a (a’:as) | a <= a’ = (3,a:a’:as) | otherwise = (t+3,a’:xs) where (t,xs) = t_insert a as
Programmieren in Haskell
5
Untere und obere Schranken
T isort (n) 6 T ime(isort [a1 ,...,an ]) 6 T isort (n)
Programmieren in Haskell
6
Untere und obere Schranken
T isort (n) 6 T ime(isort [a1 ,...,an ]) 6 T isort (n)
Programmieren in Haskell
T isort (n)
=
min{ T ime(isort x) | length x = n }
T isort (n)
=
max{ T ime(isort x) | length x = n }
6
Programmieren in Haskell
T insert (0)
=
1
T insert (n + 1)
=
3
T insert (0)
=
1
T insert (n + 1)
=
3 + T insert (n)
7
Programmieren in Haskell
T insert (0)
=
1
T insert (n + 1)
=
3
T insert (0)
=
1
T insert (n + 1)
=
3 + T insert (n)
T isort (0)
=
1
T isort (n + 1)
=
1 + T insert (n) + T isort (n)
T isort (0)
=
1
T isort (n + 1)
=
1 + T insert (n) + T isort (n)
7
> rsolve({insert(n) = 3 + insert(n-1), insert(0)=1, isort(n) = 1 + insert(n-1) + isort(n-1), isort(0)=1},{insert,isort}); 3 2 1 {insert(n ) = 1 + 3 n, isort(n ) = 1 + n + n } 2 2
Programmieren in Haskell
8
> rsolve({insert(n) = 3 + insert(n-1), insert(0)=1, isort(n) = 1 + insert(n-1) + isort(n-1), isort(0)=1},{insert,isort}); 3 2 1 {insert(n ) = 1 + 3 n, isort(n ) = 1 + n + n } 2 2
Programmieren in Haskell
T insert (0)
=
1
T insert (n + 1)
=
3
T insert (n)
=
3n + 1
T isort (0)
=
1
T isort (n + 1)
=
4n + 1
T isort (n)
=
(3/2)n2 + (1/2)n + 1
8
Asymptotische Zeit- und Platzeffizienz Θ(g)
=
{ f | (∃n0 , c1 , c2 )(∀n > n0 ) c1 g(n) 6 f (n) 6 c2 g(n) }
(1)
Ist f ∈ Θ(g), so heißt g asymptotische Schranke von f .
Programmieren in Haskell
9
Asymptotische Zeit- und Platzeffizienz Θ(g)
=
{ f | (∃n0 , c1 , c2 )(∀n > n0 ) c1 g(n) 6 f (n) 6 c2 g(n) }
(1)
Ist f ∈ Θ(g), so heißt g asymptotische Schranke von f .
Programmieren in Haskell
T insert (n)
∈
Θ(1)
T insert (n)
∈
Θ(n)
T isort (n)
∈
Θ(n)
T isort (n)
∈
Θ(n2 )
9
Programmieren in Haskell
f ∈ Θ(f )
(Reflexivität)
(2)
f ∈ Θ(g) ∧ g ∈ Θ(h) ⇒ f ∈ Θ(h)
(Transitivität)
(3)
f ∈ Θ(g) ⇒ g ∈ Θ(f )
(Symmetrie)
(4)
cf ∈ Θ(f )
(5)
na + nb ∈ Θ(na ) für a > b
(6)
loga n ∈ Θ(logb n)
(7)
10
Untere und obere asymptotische Schranken
Ω(g)
=
{ f | (∃n0 , c)(∀n > n0 ) cg(n) 6 f (n) }
(8)
O(g)
=
{ f | (∃n0 , c)(∀n > n0 ) f (n) 6 cg(n) }
(9)
Ist f ∈ Ω(g), so heißt g untere asymptotische Schranke von f . Für f ∈ O(g) heißt g entsprechend obere asymptotische Schranke von f .
Programmieren in Haskell
11
Effizienz strukturell rekursiver Funktionen
Programmieren in Haskell
T insert (0)
=
0
T insert (n + 1)
=
1 + T insert (n)
T isort (0)
=
0
T isort (n + 1)
=
T insert (n) + T isort (n)
12
Effizienz strukturell rekursiver Funktionen T insert (0)
=
0
T insert (n + 1)
=
1 + T insert (n)
T isort (0)
=
0
T isort (n + 1)
=
T insert (n) + T isort (n)
C(0)
=
c
C(n + 1)
=
f (n + 1) + kC(n)
C(n)
=
n
k c+
n X
kn−i f (i)
(10)
i=1
Programmieren in Haskell
12
T insert (n)
=
n X
1 = n ∈ Θ(n)
i=1
T isort (n)
=
n X i=1
Programmieren in Haskell
i−1=
1 n(n − 1) ∈ Θ(n2 ) 2
13
Platzbedarf von isort
isort [a1 , ..., an−1 , an ]
Programmieren in Haskell
⇒
insert a1 (· · · (insert an−1 (insert an [])) · · ·)
⇒
[aπ(1) , ..., aπ(n−1) , aπ(n) ]
14
Platzbedarf von isort
isort [a1 , ..., an−1 , an ]
Programmieren in Haskell
⇒
insert a1 (· · · (insert an−1 (insert an [])) · · ·)
⇒
[aπ(1) , ..., aπ(n−1) , aπ(n) ]
Space(insert a x)
∈
Θ(length x)
Space(isort x)
∈
Θ(length x)
14
Worst-case Laufzeit von sortTree sortTree :: Tree Integer -> [Integer] sortTree (Leaf a) = [a] sortTree (Br l r) = merge (sortTree l) (sortTree r) merge merge merge merge | |
:: (Ord a) => [] bs (a:as) [] (a:as) (b:bs) a <= b otherwise
Programmieren in Haskell
OrdList a -> OrdList a -> OrdList a = bs = a:as = a:merge as (b:bs) = b:merge (a:as) bs
15
T merge (m, n)
Programmieren in Haskell
=
m+n−1
für m, n > 1
16
T merge (m, n)
für m, n > 1
m+n−1
=
n = Zahl der Blätter (size): T sT (1)
=
0
T sT (n)
=
n − 1 + max{ T sT (i) + T sT (n − i) | 0 < i < n }
n
1
2
3
4
5
6
7
8
9
T sT (n) 0
1
3
6
10
15
21
28
36
T sT (n)
=
n X i=1
i−1=
1 n(n − 1) ∈ Θ(n2 ) 2
Schlechtester Fall: entarteter Baum Programmieren in Haskell
16
n = Tiefe (depth): 0
T sT (0) 0
T sT (n + 1)
0 T sT (n)
=
n X i=1
n−i
2
i
=
0
=
2n+1 − 1 + 2T sT (n)
(2 − 1) =
n X
0
2n − 2n−i = n2n − 2n + 1 ∈ Θ(n2n )
i=1
Schlechtester Fall: ausgeglichener Baum
Programmieren in Haskell
17
T ime(sortTree t)
00
T sT (s, d)
Programmieren in Haskell
6
=
depth t*size t
sd
18
Ende 5.2 und 5.3 fehlen.
Programmieren in Haskell
19
Problemkomplexität Bisher: isort: „worst case“-Laufzeit von Θ(n2 ) mergeSort: „worst case“-Laufzeit von Θ(n log n) Effizienz eines Sortierverfahrens
Programmieren in Haskell
20
Problemkomplexität Bisher: isort: „worst case“-Laufzeit von Θ(n2 ) mergeSort: „worst case“-Laufzeit von Θ(n log n) Effizienz eines Sortierverfahrens Jetzt: Komplexität des Sortierproblems
Programmieren in Haskell
20
Entscheidungsbäume
a1<=a2 / \ [a1,a2] [a2,a1]
a1<=a2
/ \ a1<=a3 a2<=a3 / \ / \ a2<=a3 [a3,a1,a2] a1<=a3 [a3,a2,a1] / \ / \ [a1,a2,a3] [a1,a3,a2] [a2,a1,a3] [a2,a3,a1]
Programmieren in Haskell
21
T imesort (n) > log2 (n!)
Programmieren in Haskell
22
T imesort (n) > log2 (n!) Die Fakultätsfunktion läßt sich mit der Stirlingschen Formel abschätzen: n n √ n! > 2πn . e
Programmieren in Haskell
22
Insgesamt erhalten wir T imesort (n) > log2 = log2
√ √
2πn
n n e
2πn + log2
n n e n n
= log2 (2πn)1/2 + log2
e 1 n = log2 (2πn) + n log2 2 e 1 1 = log2 (2π) + log2 n + n log2 n − n log2 e 2 2 ∈ Θ(n log n)
Programmieren in Haskell
23
Der Weg zu einer guten Problemlösung
1. Man verschafft sich Klarheit über die Komplexität des zu lösenden Problems. 2. Man entwickelt einen Algorithmus, dessen Effizienz in der Klasse der Problemkomplexität liegt. Asymptotisch gesehen, ist dieser bereits „optimal“. 3. Man analysiert die konstanten Faktoren des Algorithmus und sucht diese zu verbessern.
Programmieren in Haskell
24
Optimierung von mergeSort build :: [a] -> Tree a build [] = Nil build [a] = Leaf a build (a:as) = Br (build (take k as))(build (drop k as)) where k = length as ‘div‘ 2
Programmieren in Haskell
25
Optimierung von mergeSort build :: [a] -> Tree a build [] = Nil build [a] = Leaf a build (a:as) = Br (build (take k as))(build (drop k as)) where k = length as ‘div‘ 2
build’’ :: [a] -> Tree a build’’ as = buildn (length as) as where buildn :: Int -> [a] -> Tree a buildn 1 (a:as) = Leaf a buildn n as = Br (buildn k (take k as)) (buildn (n-k) (drop k as)) where k = n ‘div‘ 2
Programmieren in Haskell
25
T build (n) = 5n + 2n log2 n − 4 T build00 (n) = 5n + n log2 n − 4
Programmieren in Haskell
26
build’ :: [a] -> Tree a build’ as = fst (buildSplit (length as) as) buildSplit n as = (Br l r, as’’) where k = n ‘div‘ 2 (l,as’) = buildSplit k as (r,as’’) = buildSplit (n-k) as’
Programmieren in Haskell
27
build’ :: [a] -> Tree a build’ as = fst (buildSplit (length as) as) buildSplit n as = (Br l r, as’’) where k = n ‘div‘ 2 (l,as’) = buildSplit k as (r,as’’) = buildSplit (n-k) as’
Programmieren in Haskell
T buildSplit (n)
=
6 + T buildSplit (bn/2c) + T buildSplit (dn/2e)
T buildSplit (1)
=
1
27
build’ :: [a] -> Tree a build’ as = fst (buildSplit (length as) as) buildSplit n as = (Br l r, as’’) where k = n ‘div‘ 2 (l,as’) = buildSplit k as (r,as’’) = buildSplit (n-k) as’
T buildSplit (n)
=
6 + T buildSplit (bn/2c) + T buildSplit (dn/2e)
T buildSplit (1)
=
1
Für n = 2k : T buildSplit (2k ) = 6(2k+1 − 1) = 12n − 6 ∈ Θ(n) Programmieren in Haskell
27
mergeSort as = sortTree (build as) build [] = Nil build [a] = Leaf a build (a:as) = Br (build (take k as))(build (drop k as)) where k = length as ‘div‘ 2
Programmieren in Haskell
28
mergeSort [] = sortTree(build []) = sortTree Nil mergeSort [a] = sortTree(build [a]) = sortTree (Leaf mergeSort (a:as) = sortTree(build (a:as)) = sortTree(Br (build (take k as)) (build where k = length = merge (sortTree (build (take k as)) sortTree (build (drop k as))) where k = length = merge (mergeSort (take k as) mergeSort (drop k as))) where k = length
Programmieren in Haskell
a)
= [] = [a]
(drop k as))) as ‘div‘ 2
as ‘div‘ 2
as ‘div‘ 2
29
mergeSort’ [] = [] mergeSort’ [a] = [a] mergeSort’ (a:as) = merge (mergeSort (take k as)) (mergeSort (drop k as)) where k = length as ‘div‘ 2
Programmieren in Haskell
30
mtest = mergeSort [1..10000] mtest’ = mergeSort’ [1..10000]
Programmieren in Haskell
31
Top down Baumkonstruktion [8, 3, 5, 3, 6, 1] [8, 3, 5]
[3, 6, 1] [3, 5]
8
3
5
[6, 1] 3
[3, 5] [3, 5, 8]
6
1 [1, 6]
[1, 3, 6] [1, 3, 3, 5, 6, 8]
Programmieren in Haskell
32
Bottom up Baumkonstruktion /\ /t1\ ----
Programmieren in Haskell
/\ /t2\ ----
/\ /t3\ ----
/\ /t4\ ----
/\ /t5\ ----
/\ /t6\ ----
/\ /t7\ ----
33
Bottom up Baumkonstruktion /\ /t1\ ----
/\ /t2\ ----
/\ /t3\ ----
o / /\ /t1\ ----
Programmieren in Haskell
/\ /t4\ ----
/\ /t5\ ----
o \ /\ /t2\ ----
/ /\ /t3\ ----
/\ /t6\ ----
/\ /t7\ ----
o \ /\ /t4\ ----
/ /\ /t5\ ----
\ /\ /t6\ ----
/\ /t7\ ----
33
bubuild :: [a] -> Tree a bubuild = buildTree . map Leaf buildTree buildTree buildTree buildTree
:: [Tree a] -> Tree a [] = Nil [t] = t ts = buildTree (buildLayer ts)
buildLayer buildLayer buildLayer buildLayer
Programmieren in Haskell
:: [Tree a] -> [Tree a] [] = [] [t] = [t] (t1:t2:ts) = Br t1 t2:buildLayer ts
34
Berücksichtigung von Läufen
16 14 13 4 9 10 11 5 1 15 6 2 3 7 8 12 16 14 13 4 | 9 10 11 | 5 1 | 15 6 2 | 3 7 8 12.
Programmieren in Haskell
35
runs runs runs runs
:: [a] -> [] = [a] = (a:b:x) =
[[a]] [[]] [[a]] if a<=b then ascRun b [a] x else descRun b [a] x
ascRun, descRun :: a -> [a] -> [a] -> [[a]] ascRun a as [] = [reverse (a:as)] ascRun a as (b:y) = if a<=b then ascRun b (a:as) y else reverse (a:as):runs (b:y) descRun a as [] = [a:as] descRun a as (b:y) = if a<=b then (a:as):runs (b:y) else descRun b (a:as) y
Programmieren in Haskell
36
Geschmeidiges Merge-Sort
smsort :: Ord a => [a] -> [a] smsort = mergeRuns . build’ . runs mergeRuns :: Ord a => Tree [a] -> [a] mergeRuns (Leaf x) = x mergeRuns (Br l r) = merge (mergeRuns l) (mergeRuns r)
Programmieren in Haskell
37
Nachtrag zu Listen
[1 ..] Liste der positiven Zahlen, [1 .. 99] Liste der positiven Zahlen bis einschließlich 99, [1, 3 ..] Liste der ungeraden, positiven Zahlen, [1, 3 .. 99] Liste der ungeraden, positiven Zahlen bis einschließlich 99.
Programmieren in Haskell
38
Listenbeschreibungen (list comprehensions)
squares :: [Integer] squares = [n*n | n <- [0..99]]
Programmieren in Haskell
39
Listenbeschreibungen (list comprehensions)
squares :: [Integer] squares = [n*n | n <- [0..99]]
map’ f x = [f a | a <- x] squares = map (\n -> n * n) [0..99] a ‘elem‘ x = or [a==b | b <- x]
Programmieren in Haskell
39
divisors :: (Integral a) => a -> [a] divisors n = [d | d <- [1..n], n ‘mod‘ d == 0] primes :: (Integral a) => [a] primes = [n | n <- [2..], divisors n == [1,n]]
Programmieren in Haskell
40
divisors :: (Integral a) => a -> [a] divisors n = [d | d <- [1..n], n ‘mod‘ d == 0] primes :: (Integral a) => [a] primes = [n | n <- [2..], divisors n == [1,n]]
qsort’’ :: (Ord a) => [a] -> [a] qsort’’ [] = [] qsort’’ (a:x) = qsort’’ [b | b <- x, b < a] ++ [a] ++ qsort’’ [ b | b <- x, b >= a]
Programmieren in Haskell
40
[(a,b) | a <- [0,1], b <- [1..3]] ⇒
Programmieren in Haskell
[(0,1),(0,2),(0,3),(1,1),(1,2),(1,3)]
41
Felder (Arrays) squares’ :: Array Int Int squares’ = array (0,99) [(i,i*i) | i <- [0..99]]
squares’!7 ⇒ 7*7 ⇒ 49
Programmieren in Haskell
42
Felder (Arrays) squares’ :: Array Int Int squares’ = array (0,99) [(i,i*i) | i <- [0..99]]
squares’!7 ⇒ 7*7 ⇒ 49
multTable :: Array (Int, Int) Int multTable = array ((0,0),(9,9)) [((i,j),i*j) | i <- [0..9], j <- [0..9]]
Programmieren in Haskell
42
Funktionen auf Indextypen
range inRange array bounds assocs (!)
:: :: :: :: :: ::
Programmieren in Haskell
(Ix (Ix (Ix (Ix (Ix (Ix
a) a) a) a) a) a)
=> => => => => =>
(a,a) (a,a) (a,a) Array Array Array
-> [a] -> a -> Bool -> [(a,b)] -> Array a b a b -> (a,a) a b -> [(a,b)] a b -> a -> b
43
Funktionstabellierung
tabulate :: (Ix a) => (a -> b) -> (a,a) -> Array a b tabulate f bs = array bs [(i, f i) | i <- range bs]
Programmieren in Haskell
44
Funktionstabellierung
tabulate :: (Ix a) => (a -> b) -> (a,a) -> Array a b tabulate f bs = array bs [(i, f i) | i <- range bs]
∀i <- range bs : (tabulate f bs)!i == f i
Programmieren in Haskell
44
Anwendung Tabellierung
badfib 0 = 1 badfib 1 = 1 badfib n = badfib (n-2) + badfib (n-1) fib n = t!n where t = tabulate f (0,n) f 0 = 1 f 1 = 1 f n = t!(n-2) + t!(n-1)
Programmieren in Haskell
45
listArray :: (Ix a) => (a,a) -> [b] -> Array a b listArray bs vs = array bs (zip (range bs) vs)
zip [a1 ,a2 ,...] [b1 ,b2 ,...] = [(a1 ,b1 ),(a2 ,b2 ),...]
Programmieren in Haskell
46
Binäre Suche
binarySearch :: (Ord b, Integral a, Ix a) => Array a b -> b -> Bool binarySearch a e = within (bounds a) where within (l,r) = l <= r && let m = (l + r) ‘div‘ 2 in case compare e (a!m) of LT -> within (l, m-1) EQ -> True GT -> within (m+1, r)
Programmieren in Haskell
47
Anwendung: Ein lineares Sortierverfahren countingSort :: (Ix a) => (a, a) -> [a] -> [a] countingSort bs x = [ a | (a,n) <- assocs t, i <- [1..n]] where t = accumArray (+) 0 bs [(a,1) | a <- x, inRange bs a]
Programmieren in Haskell
48
Anwendung: Ein lineares Sortierverfahren countingSort :: (Ix a) => (a, a) -> [a] -> [a] countingSort bs x = [ a | (a,n) <- assocs t, i <- [1..n]] where t = accumArray (+) 0 bs [(a,1) | a <- x, inRange bs a]
listSort :: (Ix a) => (a, a) -> [[a]] -> [[a]] listSort bs xs | drop 8 xs == [] = insertionSort xs | otherwise = [[] | [] <- xs] ++ [a:x | (a, ys) <- assocs t, x <- listSort bs ys] where t = accumArray (\y b -> b:y) [] bs [(a,x) | (a:x) <- xs]
Programmieren in Haskell
48
Array-Update
(//) :: (Ix a) => Array a b -> [(a, b)] -> Array a b unitMatrix :: (Ix a, Num b) => (a,a) -> Array (a,a) b unitMatrix bs@(l,r) = array bs’ [(ij,0) | ij <- range bs’] // [((i,i),1) | i <- range bs] where bs’ = ((l,l),(r,r))
Programmieren in Haskell
49
Pascalsches Dreieck 0
1
2
3
4
5
6 7
8
0 1
Programmieren in Haskell
1 1
1
2 1
2
1
3 1
3
3
1
4 1
4
6
4
1
5 1
5
10
10
5
1
6 1
6
15
20
15
6
7 1
7
21
35
35
21
7 1
8 1
8
28
56
70
56
28 8
1
1
50
pascalsTriangle :: Int -> Array (Int,Int) Int pascalsTriangle n = a where a = array ((0,0),(n,n)) ( [((i,j),0) | i <- [0..n], j <- [i+1..n]] ++ [((i,0),1) | i <- [0..n]] ++ [((i,i),1) | i <- [1..n]] ++ [((i,j),a!(i-1,j) + a!(i-1,j-1)) | i <- [2..n], j <- [1..i-1]])
Programmieren in Haskell
51
Binomialkoeffizienten
(x + y)n
=
! n X n k n−k x y k
k=0
n k
Programmieren in Haskell
! =
8 <
n! (n−k)!k!
06k6n
:
0
06n
