Im Bezug auf diesen Thread: Iterative und rekursive Algorithmen
Ich hab mir mal überlegt, wie man rekursive Funktionen so ausführen kann, dass auch bei beliebig großen Rekursionstiefen der Stapel nicht beliebig groß wird. Das Problem ist nämlich, dass bei rekursiven Funktionen relativ schnell ein StackOverflow auftreten kann (und damit ist nicht die Website gemeint ).
Weil das hier etwas länger geworden ist, als ich anfangs erwartet habe, habe ich es etwas gegliedert:
Problemstellung
Die wohl bekannteste, rekursive Funktion ist die Fibonacci-Funktion, welche so definiert ist (wir gehen davon aus, dass n immer >= 0 ist):
Hier ist die Anzahl an benötigten StackFrames im Regelfall n. Also RecursiveFibonacci(30) = 832040 und es werden 30 StackFrames benötigt.
ErfinderDesRades hat in diesem Post gezeigt, wie die Fibonacci-Funktion iterativ implementiert werden kann.
Mit der Ackermann-Funktion geht das aber nicht mehr ganz so einfach. Die ist nämlich so definiert (die Argumente sind ebenfalls >= 0):
Also wenn m und n nicht 0 sind muss man die Funktion rekursiv aufrufen, nur um ein Argument zu bekommen, mit dem man die Funktion nochmal rekursiv aufruft. Die Anzahl an StackFrames explodiert förmlich:
RecursiveAckermann(4, 1) und RecursiveAckermann(5, 0) lösen bei mir nach ca. 8600 StackFrames eine StackOverflowException aus. Abgesehen davon, dass es eine Weile dauert, das alles zu berechnen: Wenn möglich möchte man StackOverflows verhindern.
Lösungsansatz
Ich habe da an folgendes Konzept gedacht:
Es gibt eine Liste von auszuführenden Tasks.
Ein Task repräsentiert einen Rekursions-Aufruf. Also ein Task stellt alle Informationen bereit, die die Funktion benötigt, wie z.B. Argumente.
Ein Task kann außerdem "Wartend" oder "Abgeschlossen" sein. Wenn ein Task abgeschlossen wird, wird er aus der Liste von auszuführenden Tasks entfernt.
Ein Task kann unter-Tasks haben, von denen er abhängt. Ein Task kann ausgeführt werden, wenn alle unter-Tasks abgeschlossen sind (also auch, wenn keine unter-Tasks vorhanden sind). Während ein Task ausgeführt wird, kann er unter-Tasks einreihen. Wenn unter-Tasks eingereiht werden, muss der aktuelle Task abgebrochen werden, damit zuerst die unter-Tasks abgeschlossen werden können.
Als Beispiel soll Fibonacci(4) berechnet werden:
Viele Bilder und Text
Zu Beginn wird der allererste Task eingereiht. Fibonacci(4) soll berechnet werden.
Dann beginnt der eigentliche Ablauf. Die Liste wird immer von rechts nach links durchlaufen. Da nur ein Task in der Liste ist, wird mit diesem begonnen. Da alle unter-Tasks abgeschlossen sind (bzw. in diesem Fall keine unter-Tasks vorhanden sind), wird der Task ausgeführt. Fibonacci(4) lässt sich aber nicht trivial berechnen. Stattdessen werden Fibonacci(3) und Fibonacci(2) eingereiht und der aktuelle Task abgebrochen.
Dann wird mit dem nächsten Task weitergemacht. Da der aktuelle ganz links in der Liste ist, wird wieder rechts begonnen. Da Fibonacci(2) auch nicht trivial berechnet werden kann, werden wieder 2 weitere Tasks (Fibonacci(1) und Fibonacci(0)) eingereiht.
Fibonacci(3) kann ebenfalls nicht trivial berechnet werden. Fibonacci(2) und Fibonacci(1) werden eingereiht.
Der nächste Task kann nicht ausgeführt werden, weil er nicht abgeschlossene unter-Tasks hat, was logisch ist, denn er ist ja der allererste Task, der überhaupt eingereiht wurde.
Also wieder ganz nach rechts. Dieser Task kann ausgeführt werden. Da Fibonacci(1) trivial ist, wird das Ergebnis direkt berechnet, ohne unter-Tasks einzureihen.
Der nächste Task kann ebenfalls ausgeführt werden, aber es müssen wieder Tasks eingereiht werden (Fibonacci(1) und Fibonacci(0)).
Die nächsten beiden Tasks sind wieder trivial.
Der nächste Task wurde bereits einmal ausgeführt, ist aber noch nicht abgeschlossen. Da alle unter-Tasks abgeschlossen sind, wird er erneut ausgeführt und da die Ergebnisse von Fibonacci(1) und Fibonacci(0) jetzt berechnet sind, wird auch dieser Task abgeschlossen.
Bei den nächsten beiden Tasks sind nicht alle unter-Tasks abgeschlossen, deswegen werden sie noch nicht ausgeführt.
Und wieder nach rechts. Die nächsten Beiden Tasks sind wieder trivial.
Und bei den nächsten beiden Tasks werden wieder Ergebnisse abgeschlossener Tasks zusammengerechnet.
Und damit bleibt noch der letzte (bzw. erste) Task übrig. Da alle unter-Task abgeschlossen sind, kann auch dieser ausgeführt und schlussendlich abgeschlossen werden.
Das Ergebnis des letzten Tasks ist dann das Ergebnis, das man ursprünglich haben wollte.
Wie muss nun die Fibonacci-Funktion aussehen, um mit diesem System zu funktionieren?
Pseudocode-mäßig würde das inetwa so aussehen:
Also es muss irgendwie festgestellt werden, ob die Funktion schon mal ausgeführt wurde. Und es muss irgendwie auf andere Tasks verweisen werden. Wie oben beschrieben muss ein Task alle Informationen bereitstellen, die für die Funktion notwendig sind. Darunter sind Argumente, Ergebnis und andere Dinge, die je nach Anwendungsfall unterschiedlich sein können.
Implementierung
Generica!
Die Funktion kann dann diese Signatur haben:
Der Kontext mit den Informationen wird als Parameter mitgegeben. Man beachte, dass die Funktion nichts mehr zurückgibt, sondern das Ergebnis im Kontext ablegt.
Der Kontext sieht so aus:
Alles ziemlich selbsterklärend, bis auf die TaskExecutor-Klasse, aber die kommt gleich.
Es gibt eine Liste von Tasks, die abgeschlossen sein müssen, bevor dieser Task ausgeführt werden kann und eine Property, um genau das unkompliziert abzufragen. Dann noch Properties für Parameter, Ergebnis, Zustand und ob der Task abgeschlossen ist. Die QueueTask-Funktion reiht einen neuen Task ein und fügt diesen der oben genannten Liste hinzu. Die Finish-Methode stellt klar, dass der Task abgeschlossen ist. Hier wird auch das Ergebnis festgelegt.
Im TaskExecutor ist dann die eigentliche Logik verpackt, die die einzelnen Tasks in der richtigen Reihenfolge ausführt.
TaskMethod ist ein Delegat auf die Funktion, die ausgeführt werden soll. RunningTasks ist die weiter oben beschriebene Liste von Tasks, die auszuführen ist.
InitialStateGenerator ist ein Delegat auf eine Funktion, die eine Instanz von TState zurückgibt. Man kann nicht einfach eine TState-Instanz im Konstruktor angebe, die man bei allen Tasks verwendet. Denn die Tasks würden sich in die Quere kommen, weil sie alle die gleiche Instanz verwenden. Natürlich wäre es möglich,
Die QueueTask-Funktion (die von der TaskContext.QueueTask-Funktion verwendet wird) erstellt einen neuen Task mit den angegebenen Argumenten, holt sich einen Anfangszustand vom InitialStateGenerator-Delegaten und reiht den Task ein.
Und in der Execute-Funktion passiert die Magic. Ist auch nicht sonderlich kompliziert und ich denke, der Code ist ziemlich selbsterklärend. Nur ein Hinweise: Anders als die Darstellung mit den Bildchen vermittelt werden die abgeschlossenen Tasks aus der Liste etnfernt. Es war nur einfacher zu zeichnen (und auch für die Verständlichkeit besser, wenn die Tasks nicht ins Nirvana verschwinden.
Fibonacci
Um die Fibonacci-Funktion passend umzuschreiben braucht es jetzt noch die passende Zustands-Klasse:
Und dann kann auch schon losgelegt werden:
Und ein Aufruf:
Ackermann
Und weils so schön war hier noch die Ackermann-Funktion nach dem Schema:
Und der Aufruf:
Yield in C#
Die Funktion wird auf diese Weise leider etwas auseinandergerissen. Das lässt sich auch nicht einfach vermeiden. Je komplexer die Funktion, desto schlimmer wird es. C# hat Iterator-Funktionen. Damit könnte man vermutlich was basteln, wenn man das alles etwas umschreibt. Könnte inetwa so aussehen:
Das sieht wesentlich übersichtlicher aus.
Der Compiler generiert automatisch Code, mit dem er sich "merkt", wo aktuell Code ausgeführt wird:
Das hat eine verblüffende Ähnlichkeit zur VB-Implementierung oben.
Man beachte, dass der Compiler hier absichtlich Bezeichner verwendet, die man in C# normalerweise nicht hinschreiben kann. Das
Eventuell könnte sowas ähnliches auch mit Await/Async funktionieren. Damit habe ich aber nicht genug Erfahrung.
Hausaufgabe
Als Hausaufgabe für den Leser :
1.: Die Fibonacci-Funktion optimieren, indem man ein Dictionary verwendet, um bereits berechnete Ergebnisse zwischenzuspeichern. Wie man beim Beispiel oben erkennt, wird bei Fibonacci(4) mehrmals Fibonacci(2) berechnet. Erhöht man n, wird das umso schlimmer. In einem Dictionary kann gespeichert werden, was bereits berechnet wurde.
2.: Das Ganze so umschreiben, dass man nicht nur eine Funktion rekursiv verwenden kann, sondern beliebige, die auch nicht die gleiche Signatur haben müssen. Also z.B.
3.: So umschreiben, dass in C# Iterator-Funktionen damit verwendet werden können. Nur doof, dass es dann in VB noch schlimmer wird.
Anhang
Ich habe ein Projekt mit einer Bibliothek und Beispielanwendung angehängt. Im Code oben ist das eine oder andere als Friend deklariert (internal in C#). Diese Sachen sind nicht dazu gedacht, von außen angegriffen zu werden. Wenn sich TaskExecutor, TaskContext und TaskMethod in einer eigenen Bibliothek befinden, wie in der Projektmappe, dann sind diese Sachen von außen nicht sichtbar.
Es kann sein, dass beim ersten Öffnen das falsche Startprojekt eingestellt ist. Hier einfach im Projektmappen-Explorer mit der rechten Maustaste auf TestApplication klicken und dann "Als Startprojekt festlegen".
RecursiveTaskIteration.zip (19.9 KB gepackt, 50.2 KB entpackt)
Ich hab mir mal überlegt, wie man rekursive Funktionen so ausführen kann, dass auch bei beliebig großen Rekursionstiefen der Stapel nicht beliebig groß wird. Das Problem ist nämlich, dass bei rekursiven Funktionen relativ schnell ein StackOverflow auftreten kann (und damit ist nicht die Website gemeint ).
Weil das hier etwas länger geworden ist, als ich anfangs erwartet habe, habe ich es etwas gegliedert:
- Problemstellung
- Lösungsansatz
- Implementierung
- Fibonacci
- Ackermann
- Yield in C#
- Hausaufgabe
- Anhang
Problemstellung
Die wohl bekannteste, rekursive Funktion ist die Fibonacci-Funktion, welche so definiert ist (wir gehen davon aus, dass n immer >= 0 ist):
Hier ist die Anzahl an benötigten StackFrames im Regelfall n. Also RecursiveFibonacci(30) = 832040 und es werden 30 StackFrames benötigt.
ErfinderDesRades hat in diesem Post gezeigt, wie die Fibonacci-Funktion iterativ implementiert werden kann.
Mit der Ackermann-Funktion geht das aber nicht mehr ganz so einfach. Die ist nämlich so definiert (die Argumente sind ebenfalls >= 0):
Also wenn m und n nicht 0 sind muss man die Funktion rekursiv aufrufen, nur um ein Argument zu bekommen, mit dem man die Funktion nochmal rekursiv aufruft. Die Anzahl an StackFrames explodiert förmlich:
Quellcode
- Für n = 0, 1, 2, 3, 4, 5, 6
- Bei m = 0: Anzahl an StackFrames = 1, 1, 1, 1, 1, 1, 1
- Bei m = 1: Anzahl an StackFrames = 2, 3, 4, 5, 6, 7, 8
- Bei m = 2: Anzahl an StackFrames = 4, 6, 8, 10, 12, 14, 16
- Bei m = 3: Anzahl an StackFrames = 7, 15, 31, 63, 127, 255, 511
- Bei m = 4: Anzahl an StackFrames = 16, >8596, ?, ?, ?, ?, ?
- Bei m = 5: Anzahl an StackFrames = >8593, ?, ?, ?, ?, ?, ?
RecursiveAckermann(4, 1) und RecursiveAckermann(5, 0) lösen bei mir nach ca. 8600 StackFrames eine StackOverflowException aus. Abgesehen davon, dass es eine Weile dauert, das alles zu berechnen: Wenn möglich möchte man StackOverflows verhindern.
Lösungsansatz
Ich habe da an folgendes Konzept gedacht:
Es gibt eine Liste von auszuführenden Tasks.
Ein Task repräsentiert einen Rekursions-Aufruf. Also ein Task stellt alle Informationen bereit, die die Funktion benötigt, wie z.B. Argumente.
Ein Task kann außerdem "Wartend" oder "Abgeschlossen" sein. Wenn ein Task abgeschlossen wird, wird er aus der Liste von auszuführenden Tasks entfernt.
Ein Task kann unter-Tasks haben, von denen er abhängt. Ein Task kann ausgeführt werden, wenn alle unter-Tasks abgeschlossen sind (also auch, wenn keine unter-Tasks vorhanden sind). Während ein Task ausgeführt wird, kann er unter-Tasks einreihen. Wenn unter-Tasks eingereiht werden, muss der aktuelle Task abgebrochen werden, damit zuerst die unter-Tasks abgeschlossen werden können.
Als Beispiel soll Fibonacci(4) berechnet werden:
Zu Beginn wird der allererste Task eingereiht. Fibonacci(4) soll berechnet werden.
Dann beginnt der eigentliche Ablauf. Die Liste wird immer von rechts nach links durchlaufen. Da nur ein Task in der Liste ist, wird mit diesem begonnen. Da alle unter-Tasks abgeschlossen sind (bzw. in diesem Fall keine unter-Tasks vorhanden sind), wird der Task ausgeführt. Fibonacci(4) lässt sich aber nicht trivial berechnen. Stattdessen werden Fibonacci(3) und Fibonacci(2) eingereiht und der aktuelle Task abgebrochen.
Dann wird mit dem nächsten Task weitergemacht. Da der aktuelle ganz links in der Liste ist, wird wieder rechts begonnen. Da Fibonacci(2) auch nicht trivial berechnet werden kann, werden wieder 2 weitere Tasks (Fibonacci(1) und Fibonacci(0)) eingereiht.
Fibonacci(3) kann ebenfalls nicht trivial berechnet werden. Fibonacci(2) und Fibonacci(1) werden eingereiht.
Der nächste Task kann nicht ausgeführt werden, weil er nicht abgeschlossene unter-Tasks hat, was logisch ist, denn er ist ja der allererste Task, der überhaupt eingereiht wurde.
Also wieder ganz nach rechts. Dieser Task kann ausgeführt werden. Da Fibonacci(1) trivial ist, wird das Ergebnis direkt berechnet, ohne unter-Tasks einzureihen.
Der nächste Task kann ebenfalls ausgeführt werden, aber es müssen wieder Tasks eingereiht werden (Fibonacci(1) und Fibonacci(0)).
Die nächsten beiden Tasks sind wieder trivial.
Der nächste Task wurde bereits einmal ausgeführt, ist aber noch nicht abgeschlossen. Da alle unter-Tasks abgeschlossen sind, wird er erneut ausgeführt und da die Ergebnisse von Fibonacci(1) und Fibonacci(0) jetzt berechnet sind, wird auch dieser Task abgeschlossen.
Bei den nächsten beiden Tasks sind nicht alle unter-Tasks abgeschlossen, deswegen werden sie noch nicht ausgeführt.
Und wieder nach rechts. Die nächsten Beiden Tasks sind wieder trivial.
Und bei den nächsten beiden Tasks werden wieder Ergebnisse abgeschlossener Tasks zusammengerechnet.
Und damit bleibt noch der letzte (bzw. erste) Task übrig. Da alle unter-Task abgeschlossen sind, kann auch dieser ausgeführt und schlussendlich abgeschlossen werden.
Das Ergebnis des letzten Tasks ist dann das Ergebnis, das man ursprünglich haben wollte.
Wie muss nun die Fibonacci-Funktion aussehen, um mit diesem System zu funktionieren?
Pseudocode-mäßig würde das inetwa so aussehen:
Quellcode
- 'Fibonacci-Funktion:
- 'Wenn das der erste Aufruf ist
- 'Wenn n = 0
- 'Ergebnis = 0
- 'Angeben, dass der Task abgeschlossen ist
- Return
- 'Wenn n = 1
- 'Ergebnis = 1
- 'Angeben, dass der Task abgeschlossen ist
- Return
- 'Ansonsten
- 'Task einreihen mit n - 1
- 'Task einreihen mit n - 2
- 'Angeben, dass der Task nicht abgeschlossen ist
- Return
- 'Ansonsten
- 'Ergebnis = (Ergebnis von Task mit n - 1) + (Ergebnis von Task mit n - 2)
- 'Angeben, dass der Task abgeschlossen ist
- Return
Also es muss irgendwie festgestellt werden, ob die Funktion schon mal ausgeführt wurde. Und es muss irgendwie auf andere Tasks verweisen werden. Wie oben beschrieben muss ein Task alle Informationen bereitstellen, die für die Funktion notwendig sind. Darunter sind Argumente, Ergebnis und andere Dinge, die je nach Anwendungsfall unterschiedlich sein können.
Implementierung
Generica!
Die Funktion kann dann diese Signatur haben:
Der Kontext mit den Informationen wird als Parameter mitgegeben. Man beachte, dass die Funktion nichts mehr zurückgibt, sondern das Ergebnis im Kontext ablegt.
Der Kontext sieht so aus:
VB.NET-Quellcode
- Public Class TaskContext(Of TInput, TOutput, TState)
- Public ReadOnly Property ReadyToExecute As Boolean
- Get
- Return _DependingOn.All(Function(i) i._IsFinished)
- End Get
- End Property
- Dim _IsFinished As Boolean
- Public ReadOnly Property IsFinished As Boolean
- Get
- Return _IsFinished
- End Get
- End Property
- Dim _Input As TInput
- Public ReadOnly Property Input As TInput
- Get
- Return _Input
- End Get
- End Property
- Dim _Result As TOutput = Nothing
- Public ReadOnly Property Result As TOutput
- Get
- Return _Result
- End Get
- End Property
- Public Property State As TState
- Dim Executor As TaskExecutor(Of TInput, TOutput, TState)
- Dim DependingOn As New List(Of TaskContext(Of TInput, TOutput, TState))
- Friend Sub New(NewExecutor As TaskExecutor(Of TInput, TOutput, TState), NewInput As TInput, NewState As TState)
- Executor = NewExecutor
- _Input = NewInput
- _State = NewState
- End Sub
- Public Function QueueTask(Input As TInput) As TaskContext(Of TInput, TOutput, TState)
- Dim Result = Executor.QueueTask(Input)
- DependingOn.Add(Result)
- Return Result
- End Function
- Public Sub Finish(Result As TOutput)
- _IsFinished = True
- _Result = Result
- End Sub
- End Class
Alles ziemlich selbsterklärend, bis auf die TaskExecutor-Klasse, aber die kommt gleich.
Es gibt eine Liste von Tasks, die abgeschlossen sein müssen, bevor dieser Task ausgeführt werden kann und eine Property, um genau das unkompliziert abzufragen. Dann noch Properties für Parameter, Ergebnis, Zustand und ob der Task abgeschlossen ist. Die QueueTask-Funktion reiht einen neuen Task ein und fügt diesen der oben genannten Liste hinzu. Die Finish-Methode stellt klar, dass der Task abgeschlossen ist. Hier wird auch das Ergebnis festgelegt.
Im TaskExecutor ist dann die eigentliche Logik verpackt, die die einzelnen Tasks in der richtigen Reihenfolge ausführt.
VB.NET-Quellcode
- Public Class TaskExecutor(Of TInput, TOutput, TState)
- Dim TaskMethod As TaskMethod(Of TInput, TOutput, TState)
- Dim InitialStateGenerator As Func(Of TState)
- Dim RunningTasks As New List(Of TaskContext(Of TInput, TOutput, TState))
- Public Sub New(NewTaskMethod As TaskMethod(Of TInput, TOutput, TState), NewInitialStateGenerator As Func(Of TState))
- TaskMethod = NewTaskMethod
- InitialStateGenerator = NewInitialStateGenerator
- End Sub
- Public Function Execute(Input As TInput) As TOutput
- Dim InitialTask = QueueTask(Input)
- Do
- For i = RunningTasks.Count - 1 To 0 Step -1
- Dim CurrentTask = RunningTasks(i)
- If CurrentTask.ReadyToExecute Then
- TaskMethod(CurrentTask)
- If CurrentTask.IsFinished Then
- RunningTasks.RemoveAt(i)
- End If
- End If
- Next
- Loop Until RunningTasks.Count = 0
- Return InitialTask.Result
- End Function
- Friend Function QueueTask(Input As TInput) As TaskContext(Of TInput, TOutput, TState)
- Dim Result As New TaskContext(Of TInput, TOutput, TState)(Me, Input, InitialStateGenerator())
- RunningTasks.Add(Result)
- Return Result
- End Function
- End Class
TaskMethod ist ein Delegat auf die Funktion, die ausgeführt werden soll. RunningTasks ist die weiter oben beschriebene Liste von Tasks, die auszuführen ist.
InitialStateGenerator ist ein Delegat auf eine Funktion, die eine Instanz von TState zurückgibt. Man kann nicht einfach eine TState-Instanz im Konstruktor angebe, die man bei allen Tasks verwendet. Denn die Tasks würden sich in die Quere kommen, weil sie alle die gleiche Instanz verwenden. Natürlich wäre es möglich,
TState As New
zu deklarieren, um über einen parameterlosen Konstruktor Instanzen erzeugen zu können, aber dadurch verliert man etwas Kontrolle über den Startzustand. Kann natürlich abgeändert werden.Die QueueTask-Funktion (die von der TaskContext.QueueTask-Funktion verwendet wird) erstellt einen neuen Task mit den angegebenen Argumenten, holt sich einen Anfangszustand vom InitialStateGenerator-Delegaten und reiht den Task ein.
Und in der Execute-Funktion passiert die Magic. Ist auch nicht sonderlich kompliziert und ich denke, der Code ist ziemlich selbsterklärend. Nur ein Hinweise: Anders als die Darstellung mit den Bildchen vermittelt werden die abgeschlossenen Tasks aus der Liste etnfernt. Es war nur einfacher zu zeichnen (und auch für die Verständlichkeit besser, wenn die Tasks nicht ins Nirvana verschwinden.
Fibonacci
Um die Fibonacci-Funktion passend umzuschreiben braucht es jetzt noch die passende Zustands-Klasse:
Und dann kann auch schon losgelegt werden:
VB.NET-Quellcode
- Private Shared Sub NonRecursiveFibonacci(Context As TaskContext(Of Integer, Integer, FibonacciState))
- If Context.State.IsInitialCall Then
- Select Case Context.Input
- Case Is < 0
- 'Darf eigentlich nie passieren, wird aber zur Sicherheit nochmal geprüft, für den Fall, dass sich irgendwo ein Bug eingeschlichen hat.
- Throw New NopeException
- 'Triviale Fälle abfragen
- Case 0
- Context.Finish(0)
- Return
- Case 1
- Context.Finish(1)
- Return
- Case Else
- 'Rekursion einleiten. Durch das Setzen von IsInitialCall auf False wird beim nächsten Aufruf der Code weiter unten ausgeführt.
- Context.State.IsInitialCall = False
- 'Tasks einreihen und im Zustand einen Verweis darauf behalten.
- Context.State.RecursionTask1 = Context.QueueTask(Context.Input - 1)
- Context.State.RecursionTask2 = Context.QueueTask(Context.Input - 2)
- Return
- End Select
- Else
- 'Ergebnisse der Rekursionen addieren und als Ergebnis festlegen.
- Context.Finish(Context.State.RecursionTask1.Result + Context.State.RecursionTask2.Result)
- Return
- End If
- End Sub
Und ein Aufruf:
Ackermann
Und weils so schön war hier noch die Ackermann-Funktion nach dem Schema:
VB.NET-Quellcode
- 'Ackermann benötigt 2 Parameter
- Private Structure AckermannInput
- Public m As Integer
- Public n As Integer
- End Structure
- '... und 3 Schritte
- Private Enum AckermannStateNumber As Integer
- Initial = 0
- Recurse1 = 1
- Recurse2 = 2
- End Enum
- Private Class AckermannState
- Public Number As AckermannStateNumber = AckermannStateNumber.Initial
- Public RecursionTask As TaskContext(Of AckermannInput, Integer, AckermannState)
- End Class
- Private Shared Sub NonRecursiveAckermann(Context As TaskContext(Of AckermannInput, Integer, AckermannState))
- Select Case Context.State.Number
- Case AckermannStateNumber.Initial
- 'Auch hier kann man sicherheitshalber nochmal prüfen, ob die Argumente überhaupt gültig sind.
- If Context.Input.m < 0 OrElse Context.Input.n < 0 Then
- Throw New NopeException
- End If
- 'Trivialer Fall
- If Context.Input.m = 0 Then
- Context.Finish(Context.Input.n + 1)
- Return
- End If
- 'Rekursion einleiten
- Context.State.Number = AckermannStateNumber.Recurse1
- If Context.Input.n = 0 Then
- Context.State.RecursionTask = Context.QueueTask(New AckermannInput With {.m = Context.Input.m - 1, .n = 1})
- Return
- End If
- Context.State.RecursionTask = Context.QueueTask(New AckermannInput With {.m = Context.Input.m, .n = Context.Input.n - 1})
- Return
- Case AckermannStateNumber.Recurse1
- 'Hier muss ein zweites Mal geprüft werden, ob Ackermann(m - 1, 1) oder Ackermann(m - 1, RecursiveAckermann(m, n - 1)) berechnet wird.
- If Context.Input.n = 0 Then
- 'In ersterem Falle ist der Task nämlich schon fertig.
- Context.Finish(Context.State.RecursionTask.Result)
- Return
- End If
- 'In letzterem muss nochmal gewartet werden.
- Context.State.Number = AckermannStateNumber.Recurse2
- Context.State.RecursionTask = Context.QueueTask(New AckermannInput With {.m = Context.Input.m - 1, .n = Context.State.RecursionTask.Result})
- Return
- Case AckermannStateNumber.Recurse2
- Context.Finish(Context.State.RecursionTask.Result)
- Return
- End Select
- End Sub
Und der Aufruf:
VB.NET-Quellcode
- Dim AckermannTaskExecutor As New RecursiveTaskIteration.TaskExecutor(Of AckermannInput, Integer, AckermannState)(AddressOf NonRecursiveAckermann, Function() New AckermannState)
- For m = 0 To 4
- For n = 0 To 4
- Console.WriteLine("Ackermann({0}, {1}) = {2}", m, n, AckermannTaskExecutor.Execute(New AckermannInput With {.m = m, .n = n}))
- Next
- Next
Yield in C#
Die Funktion wird auf diese Weise leider etwas auseinandergerissen. Das lässt sich auch nicht einfach vermeiden. Je komplexer die Funktion, desto schlimmer wird es. C# hat Iterator-Funktionen. Damit könnte man vermutlich was basteln, wenn man das alles etwas umschreibt. Könnte inetwa so aussehen:
C#-Quellcode
- public class TaskContext<TInput, TOutput> { ... }
- private static IEnumerable<int?> FibonacciTest(TaskContext<int, int> Context)
- {
- if (Context.Input == 0)
- {
- yield return 0; //0 als Ergebnis festlegen.
- yield break; //Vermutlich unnötig, weil die Funktion sowieso nicht mehr aufgerufen wird, nachdem ein Ergebnis zurückgeliefert wurde.
- }
- if (Context.Input == 1)
- {
- yield return 1; //1 als Ergebnis festlegen.
- yield break;
- }
- var Task1 = Context.QueueTask(Context.Input - 1); //Tasks einreihen.
- var Task2 = Context.QueueTask(Context.Input - 2);
- yield return null; //Rekursion benötigt.
- yield return Task1.Result + Task2.Result; //Summe der Ergebnisse als Ergebnis festlegen.
- yield break;
- }
Das sieht wesentlich übersichtlicher aus.
Der Compiler generiert automatisch Code, mit dem er sich "merkt", wo aktuell Code ausgeführt wird:
C#-Quellcode
- //Gaaaaaanz stark vereinfacht!
- private static IEnumerable<int?> FibonacciTest(TaskContext<int, int> Context)
- {
- <FibonacciTest>d__0 <FibonacciTest>d__ = new <FibonacciTest>d__0(-2);
- <FibonacciTest>d__.Context = Context;
- return <FibonacciTest>d__;
- }
- private class <FibonacciTest>d__0 : IEnumerable<int?>, IEnumerator<int?>
- {
- private int? <>2__current;
- private int <>1__state;
- public TaskContext<int, int> Context;
- public TaskContext<int, int> <Task1>5__1;
- public TaskContext<int, int> <Task2>5__2;
- public <FibonacciTest>d__0(int <>1__state)
- {
- this.<>1__state = <>1__state;
- }
- int? IEnumerator<int?>.Current { get { return this.<>2__current; } }
- IEnumerator<int?> IEnumerable<int?>.GetEnumerator()
- {
- //Extrem vereinfacht!
- return this;
- }
- bool IEnumerator.MoveNext()
- {
- switch (this.<>1__state)
- {
- case 0:
- this.<>1__state = -1;
- if (this.Context.Input == 0)
- {
- this.<>2__current = new int?(0);
- this.<>1__state = 1;
- return true;
- }
- if (this.Context.Input == 1)
- {
- this.<>2__current = new int?(1);
- this.<>1__state = 2;
- return true;
- }
- this.<Task1>5__1 = this.Context.QueueTask(this.Context.Input - 1);
- this.<Task2>5__2 = this.Context.QueueTask(this.Context.Input - 2);
- this.<>2__current = null;
- this.<>1__state = 3;
- return true;
- case 1:
- this.<>1__state = -1;
- break;
- case 2:
- this.<>1__state = -1;
- break;
- case 3:
- this.<>1__state = -1;
- this.<>2__current = new int?(this.<Task1>5__1.Result + this.<Task2>5__2.Result);
- this.<>1__state = 4;
- return true;
- case 4:
- this.<>1__state = -1;
- break;
- }
- return false;
- }
- }
Das hat eine verblüffende Ähnlichkeit zur VB-Implementierung oben.
Man beachte, dass der Compiler hier absichtlich Bezeichner verwendet, die man in C# normalerweise nicht hinschreiben kann. Das
<FibonacciTest>
gehört zum Bezeichner und stellt keinen generischen Typenparameter dar. Dadurch soll verhindert werden, dass der Compiler einen Namen generiert, den man schon woanders im Programm verwendet.Eventuell könnte sowas ähnliches auch mit Await/Async funktionieren. Damit habe ich aber nicht genug Erfahrung.
Hausaufgabe
Als Hausaufgabe für den Leser :
1.: Die Fibonacci-Funktion optimieren, indem man ein Dictionary verwendet, um bereits berechnete Ergebnisse zwischenzuspeichern. Wie man beim Beispiel oben erkennt, wird bei Fibonacci(4) mehrmals Fibonacci(2) berechnet. Erhöht man n, wird das umso schlimmer. In einem Dictionary kann gespeichert werden, was bereits berechnet wurde.
2.: Das Ganze so umschreiben, dass man nicht nur eine Funktion rekursiv verwenden kann, sondern beliebige, die auch nicht die gleiche Signatur haben müssen. Also z.B.
Function A(n As Integer) As String
verwendet Function B(s As String) As Integer
und umgekehrt.3.: So umschreiben, dass in C# Iterator-Funktionen damit verwendet werden können. Nur doof, dass es dann in VB noch schlimmer wird.
Anhang
Ich habe ein Projekt mit einer Bibliothek und Beispielanwendung angehängt. Im Code oben ist das eine oder andere als Friend deklariert (internal in C#). Diese Sachen sind nicht dazu gedacht, von außen angegriffen zu werden. Wenn sich TaskExecutor, TaskContext und TaskMethod in einer eigenen Bibliothek befinden, wie in der Projektmappe, dann sind diese Sachen von außen nicht sichtbar.
Es kann sein, dass beim ersten Öffnen das falsche Startprojekt eingestellt ist. Hier einfach im Projektmappen-Explorer mit der rechten Maustaste auf TestApplication klicken und dann "Als Startprojekt festlegen".
RecursiveTaskIteration.zip (19.9 KB gepackt, 50.2 KB entpackt)
"Luckily luh... luckily it wasn't poi-"
-- Brady in Wonderland, 23. Februar 2015, 1:56
Desktop Pinner | ApplicationSettings | OnUtils
-- Brady in Wonderland, 23. Februar 2015, 1:56
Desktop Pinner | ApplicationSettings | OnUtils