Speicherplatz kontrollieren

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ...

Übersicht: Speicherplatz kontrollieren

Problemdarstellung

Stellen wir uns folgende Reduktion des Terms sum [1..1000] (mit sum = foldl (+) 0), vor. 
 01  -- Reduktion durch outermost reduction
 02  	sum [1..1000]
 03  = foldl (+) 0 [1..1000]
 04  = foldl (+) (0+1) [2..1000]
 05  = foldl (+) ((0+1)+2) [3..1000]
 06  :
 07  :
 08  = foldl (+) (...((0+1)+2)+ ... +1000) []
 09  = (...((0+1)+2)+ ... + 1000)
 10  = 500500


Es fällt sofort auf, dass durch die outermost reduction der auszuwertende Ausdruck proportional zur Listengröße n steigt. Wenn wir also eine geregelte Mischung zwischen inner- und outermost reduction vollziehen könnten, würde die Größe des Ausdrucks konstant bleiben und nicht proportional zu n wachsen. 
 01  -- Reduktion mit outer- & innermost reduction
 02  	sum [1..1000]
 03  =	foldl (+) 0 [1..1000]
 04  =	foldl (+) (0+1) [2..1000]
 05  =	foldl (+) 1 [2..1000]
 06  =	foldl (+) (1+2) [3..1000]
 07  =	foldl (+) 3 [3.1000]
 08  :
 09  :
 10  =	foldl (+) 500500 []
 11  =	500500


Die Speicherplatzkomplexität dieses Vorgangs ist von Θ(n) auf &Theta(1) reduziert. Wir benötigen also eine Funktion die uns erlaubt die Auswertungsreihenfolge zu beeinflussen.


[ nach oben ]

Die strict-Funktion

Die Reduktionsreihenfolge sei durch eine spezielle Funktion, strict, beeinflussbar. Ein Term der Form strict f e wird reduziert, indem zuerst e zur Kopf-Normal-Form reduziert wird und dann f auf e angewendet wird. Ein Ausdruck e ist in Kopf-Normal-Form, wenn e eine Funktion ist oder e ein Datentypkonstruktor ist, angewandt auf keine oder mehrere Argumente (mehr Information zur Kopf-Normal-Form (head normal form)). Ein Ausdruck in Normalform ist auch in Kopf-Normal-Form, aber nicht umgekehrt. Z.B.: e1 : e2 ist in Kopf-Normal, aber nur in Normalform, wenn sowohl e1 als auch e2 in Normalform sind. In dem Ausdruck strict f e wird e, solange keine weiteren Aufrufe von strict vorliegen, selbst outermost reduziert (im Haskell Standard-Verfahren). Currying beeinflusst strict genauso, wie jede andere Funktion auch. Bei strict (f e1) e2 e3 wirkt strict auf e2 nicht auf e1 oder e3. Die Arbeitsweise von strict kann auch auf diese Weise ausgedrückt werden: 

strict f x = if x = ⊥ then ⊥ else x
.

Kehren wir zu unserem Ursprungsproblem sum zurück. Zuerst muss eine neue Definition der foldl Funktion gefunden werden, die unsere Addition in sum strikt auswerten lässt. 
 01  -- allgemeine Definition einer strikten foldl Funktion
 02  sfoldl (⊗) α		= α
 03  sfoldl (⊗) α (x:xs)	= strict (sfoldl (⊗)) (α (⊗) x) xs


Mit der sfoldl Funktion können wir eine neue Definition der sum Funktion erstellen. Mit sum = sfodl (+) 0 erhalten wir die gewünschte Reduktionsfolge und eine konstante Speicherplatzkomplexität. 
 01  -- sum Reduktion mit sfoldl
 02    sum [1..1000]
 03  = sfoldl (+) 0 [1..1000]
 04  = strict (sfoldl (+)) (0+1) [2..1000] 
 05  = sfoldl (+) 1 [2..1000]
 06  = strict (sfoldl (+)) (1+2) [3..1000]
 07  = sfoldl (+) 3 [3..1000]
 08  :
 09  :
 10  = sfoldl (+) 500500 []
 11  = 500500


[ nach oben ]

Beispiel: sumlen

Erinnern wir uns an das Beispiel aus dem letzten Kapitel - average' mit sumlen. Auch dort können wir mit strict die Speichplatzkomplexität verringern. 
 01  average'		= uncurry (/) . sumlen
 02  sumlen		= foldl f (0,0)
 03  			where f(s,n) x = (s+x,n+1)


Ersetzen wir in sumlen die foldl Funktion durch die sfoldl Funktion. Wir erhalten eine andere Reduktionsfolge. 
 01  -- sumlen Reduktion mit sfoldl
 02    sumlen [1..1000]
 03  = sfoldl f (0,0) [1..1000]
 04  = strict (sfoldl f) (0+1,0+1) [2..1000]
 05  = sfoldl f (0+1,0+1) [2..1000]
 06  = strict (sfoldl f) ((0+1)+2,(0+1)+1) [3..1000] (
 07  = ...


Das Problem ist offensichtlich. Ein Ausdruck der Form ((0+1)+2,(0+1)+1) ist in der Kopf-Normal-Form und wird nicht weiter reduziert. Die Speicherplatzkomplexität beträgt deshalb noch immer Θ(n). Um eine konstante Speichplatznutzung zu erhalten muss die Funktion f ebenfalls strikt ausgewertet werden. 
 01  -- f, strikt definiert
 02  f' (s,n)	= strict (strict tuple(s+x)) (n+1) 
 03  			where tuple a b = (a,b)


Die Reduktionssequenz mit f'. 
 01  -- sumlen Reduktion mit sfoldl und f'
 02    sumlen [1..1000]
 03  = sfoldl f' (0,0) [1..1000]
 04  = strict (sfoldl f') (strict (strict tuple (0+1)) (0+1)) [2..1000]
 05  = strict (sfoldl f') (strict (strict tuple (0+1)) 1) [2..1000]
 06  = strict (sfoldl f') (strict (strict tuple 1) 1) [2..1000]
 07  = strict (sfoldl f') (1,1) [2..1000]
 08  = sfoldl f' (1,1) [2..1000]
 09  = ...


Diese Definition besitzt eine konstante Speicherplatznutzung.

Bisher ist aus Gründen der Übersichtlichkeit und Konsistenz zur Literatur auf eine Darstellung in direkt ausführbaren Code verzichtet worden. In Haskell existiert keine Funktion strict, sondern die Funktion "seq" und der entsprechende infix-Operator "$!". Die Quelldatei enthält die drei verschiedenen Definitionen der sumlen Funktion und die Definition einer strikten foldl.


[ nach oben ]

Anmerkungen zur fold-Funktion

Das Dualitätstheorem zu fold besagt: Wenn ein Operator (⊗) assoziativ ist und e die Identität dieser Operation repräsentiert, gilt: 
foldr (⊗) e xs = foldl (⊗) e xs

Dennoch darf nicht vernachlässigt werden, dass die unterschiedlichen Operationen ⊗ unterschiedliche Zeit- und Raumkomplexitäten aufweisen können. Angenommen, ⊗ ist strikt in der Auswertung beider Argumente und kann in konstanter Zeit O(1) berechnet werden. Beispiele sind (+) oder (x), dann beträgt die Laufzeit- und Speicherplatzkomplexität jeweils O(n) bei der Bearbeitung von Listen der Länge n. Wenn die fold-Funktion korrekt gegen eine sfoldf ersetzt werden kann (für (+), (x) ist dies der Fall) bleibt die Laufzeit bei O(n), die Speichplatzkomplexität sinkt allerdings auf O(1). Eine strikte fold Funktion ist in solchen Fällen also sinnvoller. Falls ⊗ nicht diese Bedingungen erfüllt ist eine Entscheidung nicht einfach. Generell gilt die Daumenregel, wenn ⊗ nicht strikt in beiden Argumenten ist, ist foldr häufig die effizientere Methode. Beispiele für solche Operationen sind die ++-Operation und die and-Funktion (mit and = foldr (∧) True).


[ nach oben ]

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ... [ nach oben ] ...