Tupling


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

Übersicht: Tupling


Idee

Das Konzept des Tuplings steht eng in Verbindung mit dem Konzept der Parameter Akkumulation. Anstatt eines zusätzlichen Parameters wird ein zusätzliches Ergebnis eingeführt. Wir nutzen das zusätzliche Ergebnis, um Berechnungen miteinander in Verbindung zu bringen und vorangegangene Ergebnisse zur Berechnung nachfolgender zu nutzen.

statt:
 01   fib	:: Integer -> Integer


wird diese Definition von fib genutzt:
 01  fib	:: Integer -> (Integer, Integer)


[ nach oben ]

Beispiel: fib

Wie in der Idee des Tuplings schon angesprochen, werden wir uns jetzt mit den Fibonacci-Zahlen befassen. Die erste, schon bekannte, Definition der Fibonacci-Zahlen ist:

 01  fib		:: Integer -> Integer
 02  fib 0		= 0
 03  fib 1		= 1
 04  fib (n+2)		= fib n + fib(n+1)


Laufzeitanaylse für fib.

T(fib)(0)		= O(1)
T(fib)(1)		= O(1)
T(fib)(n+2)		= T(fib)(n) + T(fib)(n+1) + O(1)

Die Laufzeitanalyse liefert als Ergebnis wieder die Definition der Fibonacci-Zahlen. Aus Induktion folgt, dass T(fib)(n) = Θ(fib n) ist. Die benötigte Zeit ist also proportional zur Größe des Ergebnisses. Mit der Definition des Goldenen Schnittes (Φ) und etwas Mathematik kann eine rein arithmetische Berechnung der Fibonacci-Zahlen erfolgen, die ohne Rekursion zu einem Ergebnis führt.

Zur Abschätzung der Laufzeit können Konstanten wieder eliminiert werden und wir erhalten fib n = Θ(Φn). Eine exponentiell steigende Laufzeit.

Definieren wir nun eine zweite, weitaus effizientere Lösung des Problems. Es fällt sofort auf, dass wir nur noch eine lineare Laufzeit benötigen.
 01  fibtwo 0		= (0,1)
 02  fibtwo (n+1)	= (b,a+b)
 03  			where (a,b) = fibtwo n
Die Laufzeit beträgt Θ(n).

Durch einen einfachen zusätzlichen Ergebniswert haben wir eine Laufzeitsteigerung von exponentiell zu linear erzielt!


[ nach oben ]

Beispiel: average

In diesem Beispiel werden wir nur einen moderaten Laufzeitgewinn erzielen. Vielmehr wird schon ein wichtiges Thema des letzten Kapitels angesprochen, die Speichplatzkomplexität von Listen. Stellen wir uns vor, wir müssen den Durchschnittswert einer Float-Liste ermitteln. Dazu benötigen wir die Summe aller Elemente und die Länge der Liste.
 01  average		:: [Float] -> Float
 02  average xs		= (sum xs) / (length xs)


Die obige Definition stellt das einfachste Verfahren vor. Wir berechnen Summe und Länge der Liste sequentiell und berechnen dann das Ergebnis. Dazu sind zwei Traversierungen der Liste nötig. Mit der Tupling-Technik können wir die Anzahl der Traversierungen auf eine reduzieren. Definieren wir eine Funktion sumlen die Summe und Länge einer Liste in einem Ergebnistupel zurückgibt.
 01  sumlen xs		= (sum xs, length xs)


Unsere neue average Funktion, average', ist dementsprechend umzuformen.
 01  average'		= uncurry (/) . sumlen


Mit einer direkten Rekursion erhalten wir für sumlen eine effiziente Definition.
 01  sumlen [x]		= (x,1)
 02  sumlen (x:y:xs)	= (x+z, n+1)
 03  			where (z,n) = sumlen (y:xs)


Beide Definitionen von average benötigen Θ(n) Schritte um eine Liste der Länge n zu bearbeiten. Die Zeit, die bei einer einmaligen Traversierung gespart wird, kann sogar durch die Berechnung von Ergebnistupeln wieder egalisiert werden. Warum definiert man also eine Funktion die ihre Argumente nur einmal traversiert?
Die Antwort lautet: Speicherplatzeffizienz. Stellen wir uns eine Auswertung der Liste [1..1000] vor.
average [1..1000]

Die Liste xs kommt auf der rechten Seite der average Funktionsdefinition zwei Mal vor. D.h. nach der Auswertung des ersten xs-Ausdrucks bleibt eine Ergebnisliste zurück. Gleiches passiert bei einer zweiten Traversierung. So entstehen bei großen (Listen-)Argumenten schnell Speicherplatzprobleme, die mit der zweiten Definition von average (average') vermieden werden. Umfangreich wird diese Problematik im nachfoldendem Kapitel behandelt.


[ nach oben ]


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