Memoisierung

Eine weitere globale Verbesserung der Effizienz läßt sich erreichen, wenn man sich über mehrere Aufrufe der Lösungsfunktion hinweg bereits berechnete Werte merkt, und diese später nur noch nachschlägt. Diese Vorgehensweise wird Memoisierung genannt, und wir führen das Prinzip  hier vor, obgleich es sich bei unserem einfachen Beispiel nicht lohnt.

Die Lebensdauer bereits berechneter Werte muß nun über den Aufruf der Funktion hinausgehen, und wir brauchen daher dafür eine globale Datenstruktur, im Hauptprogramm oder besser (wegen des Geheimnisprinzips) in einem eigenen Modul, das die Realisierung verbirgt. 

DEFINITION MODULE FibMod;
(* Modul fuer Fibonacci-Zahlen, robust *)

CONST MaxArg = 24;
(* fuer groessere Argumente laeuft der Zahlbereich ueber *)

PROCEDURE Fib(n: CARDINAL): CARDINAL;
(* liefert die n-te Fibonacci-Zahl, falls 0 < n < MaxArg, 
   sonst den illegalen Funktionswert 0 *)

END FibMod.
Im Implementierungsmodul berechnen wir nun alle jemals benötigten Werte bereits zur Zeit der Initialisierung des Moduls: 
IMPLEMENTATION MODULE FibMod;

TYPE Index = 1 .. MaxArg;
VAR FibZahl: ARRAY [Index] OF CARDINAL;
    Ind: Index;

PROCEDURE Fib(n: CARDINAL): CARDINAL;
BEGIN IF (n < 1) OR (n > MaxArg) THEN RETURN 0
      ELSE RETURN FibZahl[n]
      END:
END Fib;

BEGIN (* Modul-Initialisierung *)
      FibZahl[1] := 1; FibZahl[2] := 1;
      FOR Ind := 3 TO MaxArg 
      DO FibZahl[Ind] := FibZahl[Ind-1] + FibZahl[Ind-2];
      END;
END FibMod.
Der Aufruf von Fib  hat nun konstanten Aufwand. Will man nicht alle Werte auf Verdacht vorweg berechnen, so kann dies auch in Fib  nachgeholt werden: 
IMPLEMENTATION MODULE FibMod;

TYPE Index = 1 .. MaxArg;
VAR FibZahl: ARRAY [Index] OF CARDINAL;
    Ind: Index;

PROCEDURE Fib(n: CARDINAL): CARDINAL;
BEGIN IF (n < 1) OR (n > MaxArg) THEN RETURN 0
      ELSE WHILE Ind < n 
           DO Ind := Ind + 1;
              FibZahl[Ind] := FibZahl[Ind-1] + FibZahl[Ind-2];
           END;
           RETURN FibZahl[n]
      END:
END Fib;

BEGIN (* Modul-Initialisierung *)
      FibZahl[1] := 1; FibZahl[2] := 1; Ind := 2;
END FibMod.
Zur Zeit der Modul-Initialisierung berechnen wir jetzt nur die Startwerte F(1) und F(2); alle anderen bis zum höchsten jeweils benötigten Wert werden erst bei Bedarf nachgezogen.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36