ein Kapitel zurück                                           ein Kapitel weiter

Memoizing ist ein Technik die viele aufwendige Funktionen in Perl beschleunigen kann.
Die Prinzip funktioniert mit einer Cache in der bereits gerechnete Ergebnisse zwischengespeichert werden. Bei einer erneuten Berechnung mit der Funktion wird also erst mal in die Cache geschaut, ob dieser bereits berechnete Werte beinhaltet. Falls ja wird die Cache verwendet und es kann auf eine erneute aufwendige Berechnungen verzichtet werden. Befindet sich kein bereits berechneter Wert in der Cache, muss eben eine aufwendige Berechnung durchgeführt werden.

Am besten können sie das ganze Anhand der Berechnung der Fibonaccizahlen sehen.....

#!/usr/bin/perl -w

{
 local %cache;
 sub fibonacci_cache{
   return 1 if $_[0] == 0 || $_[0] == 1;
   return $cache{$_[0]} if exists $cache{$_[0]};
   return $cache{$_[0]} = fibonacci_cache($_[0]-1) + fibonacci_cache($_[0]-2);
   }
}

sub fibonacci_nocache{
   return 1 if $_[0] == 0 || $_[0] == 1;
   return fibonacci_nocache($_[0]-1) + fibonacci_nocache($_[0]-2);
   }

print "Fibonacci mit Cache........\n";
$fib1 = fibonacci_cache(30);
print $fib1 , "\n";

print "Fibonacci ohne Cache.........\n";
$fib2 = fibonacci_nocache(30);
print $fib2 , "\n";


Die Berechnung mit Cache (fibonacci_cache) ist von der Zeit her nicht Erwähnenswert. Ohne Cache dagegen warten wir schon ein paar Sekunden.

Die Unterbringung des Caches mussten wir in einem Block mit einer dynamischen lokalen Variablen verwenden.

Obwohl wir hier einen Hash verwendet haben, muss dies nicht unbedingt so gemacht werden. Im Gegenteil, mit Arrays könnten wir diese Perfomance noch mehr Beschleunigen, da Array weniger Speicher benötigen.

Memoizing würde sich auch sehr gut für einen aufwendige Sortierung eignen.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf