Rekursion oder Iteration - verkettete Listen

[Jake?!]

Hallo,

Mir ist heute eine Frage in den Sinn gekommen, die Rekursion und Iteration betrifft. Ich habe 2 Methoden geschrieben, eine rekursiv, die andere iterativ, um Elemente an eine Warteschlange, also eine einfach verkettete FIFO-Liste anzuhaengen. (Wie wird das eigentlich ausgesprochen? F-I-F-O oder fiefoh?) Ausserdem habe ich noch eine dritte Methode geschrieben, die vermutlich besser als beide vorherigen ist, jedoch interessieren mich die beiden vorherigen trotzdem. Hier erstmal der Quellcode:

public class List 			//Beginn der Liste, zeigt auf ersten Knoten
{
	private Node next;				//Zeiger auf ersten bzw. auf den naechsten Knoten
	private List currentNode;		//Zeiger, der immer auf den "aktuellen" Knoten zeigt, wichtig fuer 3. Implementierung
	
	public List()			
	{
		this.currentNode = this;
	}
	
	public Node getNext()	//Methode fuer die Testklasse
	{
		return next;
	}
	
	public void appendRec(Node n)	//Die rekursive Methode
	{
		if (next != null)
			next.appendRec(n);
		else
			next = n;
	}
	
	public void appendIt(Node n)	//Die 1. iterative Methode
	{
		List localCurrent = this;
		while (localCurrent.next != null)
		{
			localCurrent = localCurrent.next;
		}
		localCurrent.next = n;
	}
	
	public void append3(Node n)		//Die 3. Methode,
	{									//liesse sich mit leichter Modifikation vermutlich
		currentNode.next = n;			//auch gut fuer LIFO-Stacks verwenden
		currentNode = currentNode.next;
	}
	
}


public class Node extends List		//Als Subklasse von List implementiert, um die Methoden einfacher implementieren zu koennen
{
	private String element;
	public Node(String e)
	{
		this.element = e;
	}
	
	public void print()				//Methode fuer die Testklasse
	{
		System.out.println(element);
	}
}


public class TestList 	//Eine kleine Testklasse
{
	public static void main(String args[])
	{
		List list1 = new List();
		List list2 = new List();
		List list3 = new List();
		
		String i = new String("1");
		String ii = new String("2");
		String iii = new String("3");
		
		list1.appendRec(new Node(i));
		list1.appendRec(new Node(ii));
		list1.appendRec(new Node(iii));
		
		list2.appendIt(new Node(i));
		list2.appendIt(new Node(ii));
		list2.appendIt(new Node(iii));
		
		list3.append3(new Node(i));
		list3.append3(new Node(ii));
		list3.append3(new Node(iii));
		
		list1.getNext().print();
		list1.getNext().getNext().print();
		list1.getNext().getNext().getNext().print();
		
		list2.getNext().print();
		list2.getNext().getNext().print();
		list2.getNext().getNext().getNext().print();
		
		list3.getNext().print();
		list3.getNext().getNext().print();
		list3.getNext().getNext().getNext().print();
	}
}

Scheint soweit alles zu funktionieren. Wenn ich die Landau-Notation richtig verstanden habe (kann durchaus sein, dass das nicht der Fall ist), dann hat die dritte Methode eine Laufzeit von O(1) und ist damit kaum zu toppen.

Da sind jedoch noch die ersten beiden Methoden. Also eine kleine Fallunterscheidung.

Gilt jeweils fuer einen Methodenaufruf bei der rekursiven oder einen Schleifendurchlauf bei der iterativen Methode:

Falls Zeiger.next != null:
rekursiv: 1 Abfrage + 1 Methodenaufruf = 2
iterativ: 1 Abfrage + 1 Zuweisung = 2

Falls Zeiger.next == null:
rekursiv: 1 Abfrage + 1 Zuweisung = 2
iterativ: 1 Abfrage + 1 Zuweisung = 2

Fuer beide Methoden gilt (glaube ich) eine Laufzeit von O(n), n entspricht der Anzahl der Listenelemente. Damit sind sie deutlich langsamer als die 3. Methode, aber welche von den beiden ersten ist schneller? Dauert ein Methodenaufruf laenger als eine Zuweisung oder ist die iterative Methode sowieso aufgrund der geringeren (?) Arbeitsspeicherbelastung vorzuziehen?

Mir kommen rekursive Algorithmen immer ein wenig eleganter vor...

Vielen Dank fuer Antworten!

Jake

 

[Dekker]

Die dritte Methode ist die Performanteste. Wenn du immer ans Ende anfügst, merk dir das letzte Element. Die Rekursive und die Iterative Variante gehen beide, allerdings ist in Java die iterative Variante vorzuziehen. Java muss bei der Rekursion immer auf den Stack schreiben und bei einer Liste dir voll genug ist, kann es dann zu einem Stackoverflow kommen.

 

[Jake?!]

Alles klar, soweit schon mal danke!

bleibt nur noch die Frage (ja, ich weiß, für dieses Beispiel spielt es keine unglaublich große Rolle, aber es interessiert mich allgemein) ob ein Methodenaufruf länger dauert als eine Zuweisung

Jake

 

[nillehammer]

Dauert ein Methodenaufruf laenger als eine Zuweisung

Tendenzell ja. Eine Zuweisung ist nur das Speichern eines Werts (bei primitiven) oder einer Referenz (bei Objekten) in einem Speicherbereich, dem Du einen Namen gegeben hast. Methoden enthalten mindestens mehrere Opertationen manchmal sogar sehr Komplizierte.

oder ist die iterative Methode sowieso aufgrund der geringeren (?) Arbeitsspeicherbelastung vorzuziehen?

Im Sinne der Lesbarkeit des Codes ist Iteration meist vorzuziehen. Im Sinne der Arbeitsspeicherbelastung denke ich auch. Wobei man bestimmt Fälle finden kann, bei denen eine Rekursion weniger Arbeitsspeicher benötigt als eine Iteration.

 

[Denny1989]

die 3. implementierung hat meiner meinung nach aber nichts mehr mit den ersten beiden zu tun, da du bei den ersten beiden immer den anfangspunkt deine kette im currentNode hast und bei der 3. variante immer den zu letzt geschriebenen node. was ja ein unterschied ist, deswegen hinkt hier der vergleich würde ich sagen. das verhält sich dann ja anders.

 

[bERt0r]

currentNode.next = n;
currentNode = currentNode.next;

ist das selbe wie

x.next=n;
x=n;

Das schlechte an deiner Implementierung ist, dass sowohl in deiner List, als auch in deinen Nodes überall UNTERSCHIEDLICHE currentNode Zeiger sind, und die zeigen alle auf sich selbst - ausser bei dem Node/der List wo du deine appends aufrufst. Das ganze funktioniert solange du nicht auf irgendeine Node in der Mitte ein append3 machst, dann überschreibst du nämlich einfach das nächste Element.

 

[Jake?!]

@Denny: Das ist mir bewusst. Es ging auch primaer um den Vergleich von Methode #1 und #2, #3 habe ich hinzugefuegt damit, wenn ich schon zwei von der Laufzeit her suboptimale Methoden vergleiche, ich wenigstens eine schnelle Alternative habe.

@bERt0r: Stimmt, ich frage mich gerade warum mir das nicht aufgefallen ist... (bezogen auf das Codefragment)

immernoch @bERt0r: Hmm, vermutlich sollte ich Node nicht von List erben lassen... Das habe ich eigentlich fuer die rekursive Methode gemacht, aber fuer die andern liess es sich auch ganz gut nutzen, ich denke es wuerde trotzdem nicht schwer sein, das anders zu implementieren. Ich versuche es gleich mal. (Man koennte natuerlich auch mit instanceOf-Abfrage ueberpruefen, ob das Objekt, auf dem die Methode aufgerufen wird, eine List ist, aber das wuerde sich glaube ich nicht wirklich lohnen)

Jake

edit: OK, habs, die Methode ist zwar laenger, hat aber immernoch eine Laufzeit von O(1)

 

[Denny1989]

äh nochmal.

deine Laufzeit von 1 und das die #3 länger ist als die 1. und 2. spielt doch garkeine rolle wenn sie doch sowieso nicht das selbe tun und somit nciht zum gleichen ergebnis führen!? was macht ein vergleich da für einen sinn?

 

[Jake?!]

Irgendwo tun sie ja schon dasselbe, sie haengen ein Element an die Liste an... (Sie erreichen das Ziel nur auf unterschiedlichen Wegen, und es ist so gedacht, dass man die Methoden nur von einem List-Objekt aufruft)

Aber mir ging es ja auch nicht darum, #1 mit #3 oder #2 mit #3 zu vergleichen, sondern vorallem #1 mit #2.

Und falls du das hier meintest:

edit: OK, habs, die Methode ist zwar laenger, hat aber immernoch eine Laufzeit von O(1)

damit meinte ich, dass die Methode laenger als vorher ist, nicht laenger als #1 oder #2

Jake