Beispiele - Test und effizienzorientiertes Refactoring
Übersicht: Beispiele - Test und effizienzorientiertes Refactoring
Beispiele Vortrag „Effizienz in Haskell“ (1)
Die in diesem Kapitel vorgestellten Beispiele sind angelehnt an den Vortrag Effizienz in Haskell von Oliver Lohmann. Die Funktionen reverse1 und reverse2 zeichnen sich durch die folgenden Eigenschaften bezüglich der Laufzeit aus:
zu reverse1:
T(reverse1)(0) = O(1) = T(1)
T(reverse1)(n+1) = T(reverse1)(n) + T(++)(n,1)
d.h. Um eine Liste der Länge n+1 umzudrehen, dreht man eine Liste der Länge n um und konkateniert es mit einer Liste der Länge 1.
zu reverse2:
T(accum)(m,0) = O(1) = T(1)
T(accum)(m,n+1) = O(1) + T(accum)(m,n)
d.h. T(reverse2) = T(n)
01 import QuickCheck
02
03 reverse1 :: [a] -> [a]
04 reverse1 [] = []
05 reverse1 (x:xs) = (reverse1 xs) ++ [x]
06
07 reverse2a = foldl prefix []
08 where prefix xs x = x : xs
09
10 reverse2b :: [a] -> [a]
11 reverse2b xs = accum [] xs
12 accum ws[] = ws
13 accum ws (x:xs) = accum (x:ws) xs
14
15 prop_reverse_1eq2a :: (Eq a) => [a] -> Bool
16 prop_reverse_1eq2a xs = reverse1 xs == reverse2a xs
17
18 prop_reverse_1eq2aInt :: [Integer] -> Bool
19 prop_reverse_1eq2aInt xs = prop_reverse_1eq2a xs
20
21 prop_reverse_1eq2b :: (Eq a) => [a] -> Bool
22 prop_reverse_1eq2b xs = reverse1 xs == reverse2b xs
23
24 prop_reverse_1eq2bInt :: [Integer] -> Bool
25 prop_reverse_1eq2bInt xs = prop_reverse_1eq2b xs
26
|
reverse.hs |
Codebeispiel 17
Die in o.g. Vortrag durchgeführte Modifikation des Programmes reverse zur Verbesserung des Laufzeitverhaltens soll getestet werden. Ist die Funktionalität der beiden Funktionen reverse1 und reverse2 identisch?
Der allgemeine Ansatz ist durch die Eigenschaften prop_reverse_1eq2a und prop_reverse_1eq2b gegeben.
Die Funktionen prop_reverse_1eq2aInt prop_reverse_1eq2bInt mit der Typsignatur ermöglichen die direkte Ausführung.
Beispiele Vortrag „Effizienz in Haskell“ (2)
Auch das zweite Beispiel steht im Kontext von "Test und effizienzorientiertes Refactoring". Das zweite Beispiel aus Vortrag "Effizienz in Haskell" besteht aus dem Funktionen "flatten" und "flatcat". (Dieses Beispiel ist nicht ausführbar, da kein Generator für diesen Datentyp definiert ist.)
01 data Btree a = Leaf a
02 | Fork (Btree a) (Btree a)
03
04 flatten :: Btree a ->[a]
05 flatten (Leaf x) = [x]
06 flatten (Fork xt yt)= flatten xt ++ flatten yt
07
08 flatcat :: Btree a ->[a] -> [a]
09 flatcat (Leaf x) xs = x : xs
10 flatcat (Fork xt yt) xs = flatcat xt (flatcat yt xs)
11
12 prop_flatcatEqflatten :: (Eq a) => Btree a -> Bool
13 prop_flatcatEqflatten x = flatcat_def x [] == flatten x
|
flatcat.hs |
Codebeispiel 18
Die Formulierung des Programmes in Form des Algorithmus flatcat mit Hilfe von Parameter Akkumulation
weist Laufzeitanalyse zum Glätten eines perfekten binären Baums
Induktion:
(flatten)(h)= T(h2h)
d.h. flatten benötigt O(s log s) Schritte auf einem Baum der Größe s.
Induktion:
T(flatcat)(h,n)= T(2h)
d.h. flatcat benötigt lineare Laufzeit im Verhältnis zur Baumgröße.
Die zwei hier gezeigten Beispiele sollen ein mögliches Anwendungsfeld des automatisierenten Testens verdeutlichen: Durch das umformulieren der Programme bzw. der Funktionen wird es notwendig deren Funktionalitäten auf Gleichheit zu überprüfen. D.h. es wird die Modifikation mit der Referenzimplementierung bzw. der Spezifikation verglichen.
Ein alternatives Vorgehen soll in dem folgendem Abschnitt anhand eines weiteren Beispiels vorgestellt werden.
Code generated with AusarbeitungGenerator Version 1.1, weblink