Thread Rekursiver Algorithmus zur Kombinatorik optimierbar? (11 answers)
Opened by ariser at 2013-10-05 21:31

topeg
 2013-10-07 21:44
#171047 #171047
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Ja Funktionsaufrufe sind nicht günstig, da ein ganz neuer Gültigkeitsbereich erzeugt wird, mit allen definierten und speziellen Variablen, deren Inhalte kopiert werden müssen. Aber das ist immer noch günstiger als das kopieren von Variablen mit "der Hand", da eine ganze Reihe von Prüfungen nicht gemacht werden.

Zudem hat mein Code vier Schleifen, von denen bis zu drei in einander gestaffelt sind, jede erzeugt einen eigenen Gültigkeitsbereich, und Variablen werden erzeugt/kopiert. Über eine Rekursion kann man sich einige Schleifen sparen, da der übergeordnete Gültigkeitsbereich direkt im Core erhalten und verwaltet wird. Vieles was man ansonsten im eigenen Code implementieren müsste (z.B über einen eigenen Stack) macht perl für einen so effizient wie möglich.
Man muss es halt abwägen/ausprobieren, wann das kopieren bei Funktionen das Verwalten im Core überwiegt.

Mein Code ist auch nicht der Effizienteste den man in Perl schreiben kann. Dieses Beispiel wäre in Assembler/C sehr schnell, da er sich mit wenig und effizientem Code implementieren lässt.
Es handelt sich um einen n stelligen Zähler (hier n=4), der in einem "m-wertigen" Zahlenraum arbeitet (hier m=10-n). Wenn die Summe aller Stellen 10 ist erfolgt eine Ausgabe. Alle Durchläufe sind erreicht wenn der Zähler überläuft.
Das erzeugt in Perl viele unnötige und "teure" Durchläufe, die alle Zeit kosten, da jedes mal der Gültigkeitsbereich der Schleifen neu erstellt wird. Man könnte sich wahrscheinlich noch zwei Schleifen sparen, wenn man $len und $left nicht über eine Schleife jedes mal neu erzeugt, sondern bei allen Operationen auf @lst passend addiert oder subtrahiert. Dennoch wäre man dann immer noch bei zwei Schleifen. gegenüber eines Funktionsaufrufs, der einem auch noch die Verwaltung der Gültigkeitsbereiche abnimmt.
Last edited: 2013-10-07 21:47:58 +0200 (CEST)

View full thread Rekursiver Algorithmus zur Kombinatorik optimierbar?