This post originated from an RSS feed registered with .NET Buzz
by -.
Original Post: Rekursive Methoden mit Hilfe eines Stacks abbilden
Feed Title: Norbert Eder - Living .NET
Feed URL: http://feeds.feedburner.com/NorbertEder-Livingnet
Feed Description: Copyright (c)2005, 2006 by Norbert Eder
Rekursionen werden recht gerne für unterschiedlichste Zwecke eingesetzt. Beispielsweise um ein bestimmtes Steuerelement auf einem Formular (oder darunterliegenden Containern) zu finden. Allerdings muss eine Rekursion nicht immer sein. Der Nachteil einer Rekursion besteht im zahlreichen Aufruf derselben Methode. Methodenaufrufe sind kostspielig und und sollten daher nicht übertrieben werden. In einigen Fällen der Rekursion läßt sich das vermeiden.
Im nachfolgenden Beispiel wird eine vorhandene Rekursion mit Hilfe eines Stacks ersetzt. Die Stack-Variante ist recht einfach umgesetzt und zudem auch noch performanter als die rekursive.
Um ein bestimmtes Steuerelement auf einem Formular zu finden, würde uns folgender rekursiver Ansatz zum Ziel bringen:
private Control FindRecursively(Control c, string strControlName)
{
if (c.Name == strControlName)
return c;
foreach (Control cf in c.Controls)
{
Control cTemp = FindRecursively(cf, strControlName);
if (cTemp != null)
return cTemp;
}
returnnull;
}
Recht schnell erklärt: Das jeweils übergebene Control wird auf den Namen hin überprüft. Entspricht dieser nicht dem gewünschten, wird die Controls-Auflistung durchlaufen und dieselbe Methode wieder aufgerufen. Dies wird so lange gemacht bis entweder das gewünschte Steuerelement gefunden wurde, oder alle durchlaufen wurden. Das nachfolgende Beispiel zeigt, wie dies nicht-rekursiv, mit Hilfe eines Stacks gelöst werden kann:
private Control FindNotRecursively(Control c, string strControlName)
{
if (c.Name == strControlName)
return c;
Stack stack = new Stack();
stack.Push(c);
while (stack.Count > 0)
{
Control cTemp = stack.Pop();
if (cTemp.Name == strControlName)
return cTemp;
foreach (Control cf in cTemp.Controls)
stack.Push(cf);
}
returnnull;
}
Auch diese Variante ist schnell erklärt: Das übergebene Steuerelement wird auf den Stack gelegt. Die darauffolgende Schleife durchläuft den Stack solange, solange sich Elemente darauf befinden. Per Pop wird immer ein Steuerelement vom Stack genommen und die Eigenschaft Name überprüft. Danach werden alle Steuerelemente aus der Controls-Auflistung auf den Stapel gelegt und ebenfalls durchlaufen. Dies geschieht ebenfalls so lange bis das gewünschte Steuerelement gefunden wurde, oder sich keine weiteren Elemente mehr auf dem Stapel befinden.
Ein kleiner Testfall wurde durch ein dynamisches Anlegen von Steuerlementen geschaffen:
Panel currentPanel = new Panel();
this.Controls.Add(currentPanel);
for (int i = 0; i < 40; i++)
{
Panel p = new Panel();
for (int i2 = 0; i2 < 80; i2++)
{
Label l = new Label();
p.Controls.Add(l);
}
currentPanel.Controls.Add(p);
currentPanel = p;
}
Button btn1 = new Button();
btn1.Name = "button1";
currentPanel.Controls.Add(btn1);
Danach wurden die unterschiedlichen Varianten mittels Stopwatch gemessen. Hier das Ergebnis:
// Zahlen in Millisekunden// Erster Durchlauf
Recursively: 4
!Recursively: 1
// Folgende Durchläufe
Recursively: 1
!Recursively: 0
Die zahlen wirken auf den ersten Blick nicht sehr spektakulär. Zu beachten ist jedoch, dass die Beispielrekursion recht klein ist und wenig Aufwand verursacht. In der Realität sind viele Rekursionen meist aufwändiger, wodurch sich der Geschwindigkeitsunterschied verdeutlicht.
Previous Topic
