kann man einen rekursiven Algo auch iterativ darstellen?

[Poison Nuke]

Hallo,

ich hoffe die Frage ist für euch nicht zu einfach :o :)

also, einfach rein interessehalber:
kann man einen rekursiven Algo auch iterativ realisieren? Ich versuch mich gerade daran, finde aber irgendwie keine wirklich funktionierende Lösung...

(nicht als das es wichtig wäre, die rekursive Lösung läuft ja bei mir, ich würde halt nur gerne wissen, ob es überhaupt möglich ist :))

[Jan Krüger]

Ja, das geht. Die einfachste Moeglichkeit ist, einen eigenen Stack zu implementieren und die Rekursion damit zu simulieren.

Ein Beispiel findet sich auf http://en.wikipedia.org/wiki/Quicksort.

[Scavi]

@Jan: Und was ist mit Ackermann? Ich glaube du verwechselst Primitiv Rekursiv mit Rekursiv.

[Jan Krüger]

Es ging hier nur darum, Rekursion aufzuloesen. Wenn ich also eine Funktion schreibe, die die Ackermann-Funktion berechnet und sich nicht selbst aufruft, ist das im Sinne der Frage nicht mehr iterativ.

Moeglich ist das eindeutig, denn meine Funktion koennte ja z.B. eine Turingmaschine simulieren, die die Ackermann-Funktion fuer die Eingabe berechnet.

Man koennte sich jetzt natuerlich damit befassen, mathematische Rekursionen aufzuloesen, bzw. auf simplere Rekursionen wie z.B. Addition und Multiplikation zurueckzufuehren. Das ist aber wesentlich komplizierter und scheint mir nicht Teil der Frage zu sein.

[Firefall]

Man könnte doch einfach ineinander verschachtelte Loops schreiben? Ist dann natürlich nicht allgemeingültig sondern muss je nach Rekursion geschrieben werden.

[Scavi]

Moeglich ist das eindeutig, denn meine Funktion koennte ja z.B. eine Turingmaschine simulieren, die die Ackermann-Funktion fuer die Eingabe berechnet. ..mach das mal und die Thoeretische Informatik Profs. dieser Welt werden sich freuen ;)


Es ging hier nur darum, Rekursion aufzuloesen. Wenn ich also eine Funktion schreibe, die die Ackermann-Funktion berechnet und sich nicht selbst aufruft, ist das im Sinne der Frage nicht mehr iterativ. ???

[Jan Krüger]

..mach das mal und die Thoeretische Informatik Profs. dieser Welt werden sich freuen ;)
Wo soll denn da bitteschoen das Problem sein?

???
Diese Frage verstehe ich nicht.

[Scavi]

Wo soll denn da bitteschoen das Problem sein?. ...simuliere mal bitte eine Maschine mit unendlich Speicher auf einer Maschine mit endlich Speicher. Wenn dir das gelingt, dann kannst du auch A(100,100) mit Leichtigkeit berechnen.

...was aber mit den ursprünglichen Thema nix mehr zu tun hat.

Diese Frage verstehe ich nicht. ...sie sollte auch nur meine Verwirrung beim Lesen deines Satzes ausdrücken ;)

[Jan Krüger]

...simuliere mal bitte eine Maschine mit unendlich Speicher auf einer Maschine mit endlich Speicher. Wenn dir das gelingt, dann kannst du auch A(100,100) mit Leichtigkeit berechnen.
Oh, Verzeihung. Ich dachte, das verstaende sich von selbst.

[Mr.Homm]

@Jan: Und was ist mit Ackermann? Ich glaube du verwechselst Primitiv Rekursiv mit Rekursiv.

Hier http://www.imn.htwk-leipzig.de/~theinric/download/ginf/ackerm.jpg (http://www.imn.htwk-leipzig.de/%7Etheinric/download/ginf/ackerm.jpg) gibt's Ackermann mit Rekursion und Iteration.

[Scavi]

die Implementierung ist nice.

Oh, Verzeihung. Ich dachte, das verstaende sich von selbst. da gibts schon wieder "???" Hast du gesoffen oder was?

[DarkTom]

Man könnte doch einfach ineinander verschachtelte Loops schreiben? Ist dann natürlich nicht allgemeingültig sondern muss je nach Rekursion geschrieben werden.Nein, das geht nicht. Egal, wieviele Schleifen du schreibst, du bist dann immer in der Rekursionstiefe eingeschränkt.


Bzgl. Ackermann (das Bild lässt sich gerade nicht laden):
Das ist iterativ doch schnell hingeschrieben:ackermann(val1, val2)

Stack s
s.push(val1)
s.push(val2)
WHILE es sind mind. zwei Werte auf dem Stack DO
val2 = s.pop()
val1 = s.pop()

IF (val1 == 0) THEN
s.push(val2 + 1)
ELSE IF (val2 == 0) THEN
s.push(val1 - 1)
s.push(1)
ELSE
s.push(val1 - 1)
s.push(val1)
s.push(val2 - 1)

RETURN s.pop()

edit:
Es sei noch angemerkt, dass man nicht nur Turing-Berechenbarkeit anführen könnte, sondern auch WHILE-Berechenbarkeit. Alle mü-rekursiven Funktionen lassen sich mit einem Algorithmus in der Sprache WHILE berechnen. Und da gibt es keine rekursiven Konstrukte.

[Poison Nuke]

hallo,

danke für eure Antworten.

Also meine Rekursion ist derzeit bei der Auswertung einer beliebigen Baumstruktur. Da ja jeder Ast eine beliebige Anzahl an weitere Ästen haben kann und es keine Begrenzung in der Tiefe gibt und auch die Anzahl der Ebenen je Ast verschieden ist, ist eine Rekursion aufjedenfall das einfachste.


Nur irgendwie interessiert es mich halt gerade auch, ob ich diese Auswertung nicht auch iterativ gestalten könnte. Die Sache mit einem Stack ist da aufjedenfall ne gute Sache für die Ergebnisse, ich blick derzeit nur noch nicht ganz, wie ich am besten die Abbruchbedingungen gestalte und wie die Schleifen verschachtelt werden müssen.

Na da werd ich am besten noch ein wenig knobeln, vorsagen lassen ist ja doch etwas langweilig :)
(es sei denn ihr sagt, es ist aussichtslos und es nur zu Frust führt )

[DarkTom]

Das ist keineswegs aussichtslos. Wenn es dir im Grunde nur darum geht, den Baum zu traversieren ist das gut machbar. Das einfachste wäre eine Breitensuche, aber jede andere Traversierung ist auch nicht viel schwerer. Zeig doch mal ein bisschen Code, am besten auf das Relevante gekürzt.

[Mr.Homm]

hallo,

danke für eure Antworten.

Also meine Rekursion ist derzeit bei der Auswertung einer beliebigen Baumstruktur. Da ja jeder Ast eine beliebige Anzahl an weitere Ästen haben kann und es keine Begrenzung in der Tiefe gibt und auch die Anzahl der Ebenen je Ast verschieden ist, ist eine Rekursion aufjedenfall das einfachste.
...

Ich gebe mal Niklaus Wirth aus "Algorithmen und Datenstrukturen mit Modula-2" zum Besten:
"Rekursive Algorithmen eignen sich besonders, wenn das zugrundeliegende Problem oder die zu behandelnden Daten rekursiv definiert sind. Das bedeutet aber nicht, dass eine solche rekursive Definition eine Garantie dafür bietet, dass ein rekursiver Algorithmus der beste Weg zur Lösung des Problems ist. Tatsächlich hat die Erklärung des Konzeptes rekursiver Algorithmen anhand von ungeeigneten Beispielen wesentlich zur Entstehung einer weitverbreiteten Abneigung und Antipathie gegen die Rekursion in der Programmierung beigetragen und zur Gleichsetzung von Rekursion mit Ineffizienz geführt"

[Poison Nuke]

da bin ich gerade noch am Werkeln, weil ich will da schon einige nette Funktionen mit ausführen, die mir auch in der Rekursiven Version für etwas Kopfzerbrechen sorgen -> es ist also noch kein Code da, den man zeigen könnte :o

größtes Problem ist die rechentechnische Optimierung, weil der Baum könnte unter Umständen arg groß werden

(der Baum ist genauer gesagt die Datenstruktur von einem Forum wie diesem hier. Ich will nun in einer Funktion alle Statistiken aktualisieren. Also wieviele Unterforen hat ein Forum, wieviele Threads in jedem Forum, wieviele Posting, welches POsting das letzte usw. Am Ende wird das schon mehr als gewaltig und extrem CPU lastig, wenn ich es falsch mache....werde also erstmal so oder so noch etwas knobeln müssen (bzw wollen :cool: ) )

PS: bevor ihr jetzt meint, in einem Forum sei die Anzahl der Ebenen bekannt, trifft nicht bei meinem zu. Es ist so ausgelegt, dass theoretisch eine unendliche Zahl an Unterforenebenen möglich ist, was je nach Themenbereich auch ganz praktisch sein kann.

[Xpyder]

In "Unterbäume" hineinzuverzweigen erinnert mich so ein wenig an das "Flood Fill" Problem: Eben, beliebige Formen auf einer Fläche mit gleichfarbigen Pixeln füllen zu können... (entweder nur in 4 Hauptrichtungen oder in 8 Richtungen, also mit zusätzlicher Berücksichtigung von diagonalen Pixeln)
Ganz zu Anfang, als ich mit relativ kleinen "Bildern" gearbeitet habe (und noch nicht sehr lang sowas gemacht hatte) - ich hatte damals ein "Malprogramm" für den 80x50 Textmode geschrieben - habe ich mit dem Stack und Rekursion gearbeitet.

Später jedoch habe ich einige andere Probleme bewältigen müssen und dabei wollte ich eine "bessere Kontrolle" haben und habe deswegen die Rekursion iterativ nachgebaut. (In einem neueren Malprogramm habe ich Auflösungen bis zu 1024x768 unterstützt (im 16bit Mode) und im Worst case reicht da der max. 64kB große Stack einfach nicht aus. Ich habe da u.a. mit teilweisem temporären Auslagern auf Platte gearbeitet usw.

D.h. eigentlich ist es immer noch eine Art Rekursion - nur mit etwas kreativerem Einsatz eines (selbstverwalteten) Pseudo-Stacks und ohne daß (wie bei "echter" Rekursion) wirkliche Unterprogramm(selbst)aufrufe geschehen.

Aber - das sollte man vielleicht dazusagen - es ist ja auch möglich, viele Probleme, die nicht explizit auf Rekursion angewiesen wären, trotzdem rekursiv zu lösen... Im Umkehrschluß kann man also auch sagen: Das (bisher) alleinige Vorliegen einer rekursiven Lösung eines Problems ist nicht notwendigerweise der Beweis dafür, daß das Problem ohne Rekursion unlösbar wäre.

Außerdem habe ich auch ein anderes interessantes Problem ebenfalls mit einem stark modifizierten "Flood Fill" Algorithmus gelöst - nämlich das Bauen eines Zufalls-Labyrinths (mit festlegbaren Bildungsregeln, die u.a. die Schwierigkeit definieren) - wird auch u.a. im Random Level Generator meines Spiels (Xpyderz) benutzt.

Ein weiteres Problem, das ich mit Flood Fill gelöst habe, ist eines, das vor einiger Zeit mal hier im Coding-Board nachgefragt wurde, nämlich das Auffinden von Buchstabenfolgen in einer Buchstabenmatrix. (Weiß grade nicht genau, ob ich die Rekursion auch da iterativ gelöst habe, aber wie ich mich kenne, schon...)

Nicht zuletzt habe ich - zu der Zeit, als ich mich mit der Programmierung von "Grafik-Engines" zur Darstellung von 3D-Computerlevels beschäftigt habe - auch die Arbeit mit den binären Bäumen iterativ gelöst, da hier wohl jeder Stack exorbitant überlastet gewesen wäre. (u.a. zur Berechnung der Verdeckungsreihenfolge von Wänden sowie zur Feststellung der Position im Level im Verhältnis zu den Levelelementen)

Achja, und ich habe auch vor einiger Zeit mal etwas getan, das dem zu lösenden Problem ziemlich nahe kommen dürfte: Ein Programm zur "Synchronisation" von Verzeichnissen (ähnlich der Funktion des Norton Commander, nur mit mehr Features). Hauptsächlich natürlich für mehrere Rechner gedacht. (Zweck des Ganzen: Wenn ich mal "außerhalb" unterwegs bin, will ich die ganze Arbeit des Hauptrechners natürlich auf dem Laptop eins zu eins haben - und wenn ich wieder zurück bin, das ganze natürlich wieder vice versa.) Dies nur zur Erklärung. Der für das Problem interessante Teil ist wohl die Findung der Verzeichnispfade und aller dazugehörigen Unterpfade - und das scheint mir schon nahe an das Problem eines Forums mit einer
beliebigen Anzahl von Stufen und Unterstufen, sowie beliebiger "Breite" jeder einzelnen Stufe heranzureichen.

Falls es z.B. darum geht, so ein Forum zu organisieren, würde ich auf genau so etwas - d.h. eine Datenträger-Datei/Verzeichnis-ähnliche Struktur zurückgreifen - entweder, indem ich das Forum in genau dieser Form auf dem Datenträger (z.B. dem Server-Laufwerk) anlegen würde, oder (wenn z.B. nicht möglich oder nicht gewünscht, aus technischen Gründen oder wegen Datensicherheits-Aspekten) indem ich ein solches System "manuell nachbilden" würde (in einer Art "Image File").

Warum schreib ich so viel? Nun, will eigentlich lediglich damit sagen: Wenn es darum ginge, einen geeigneten Ansatz sowohl für die Datenorganisation als auch für die Programmierung von solchen und ähnlich gearteten Problemen zu finden, hätte ich wohl einige davon anzubieten, die eben auch schon in der Praxis funktioniert haben.

Kleiner Tip: In verzweigenden Baumstrukturen kann oftmals (wie z.B. bei binären Bäumen üblich) die Arbeit mit Knoten ("Nodes") ganz nützlich sein - hier wird einem Element einem oder mehrere "Zeiger" auf "benachbarte" (oder in Beziehung zu diesem stehende) Elemente beigefügt. Ein solcher Zeiger kann dann entweder "Ende" anzeigen oder eben auf ein weiteres Element zeigen. Das schöne daran ist, daß auf diese Art der Baum an jeder Stelle beliebig erweitert werden kann, indem der jeweilige "Ende" Zeiger geändert wird auf einen Zeiger auf eine gültige neue Struktur. Auch nachträglich können so Beziehungen einzelner Elemente oder ganzer Baumteile zueinander geändert werden.

Ansatz für ein "Filestruktur"-ähnliches Forum:
Man definiert ein Pseudo-"Filesystem", in dem es (erst einmal) zwei Arten von Datenstrukturen gibt: "Verzeichnisse" und "Daten".
Alle Files sind dabei einfach "durchnumerierte" Dateien.
Ein "Verzeichnis" ist dabei eine besondere Datei, die einfach nur die Einträge des jeweiligen Verzeichnisses enthält, "Daten"/"Dateien" sind die Daten selbst. In einem Verzeichniseintrag ist den Daten beigefügt:
- Ihr TYP (d.h. "Verzeichnis" oder "Daten"), denn Verzeichnisse dürfen weitere Verzeichnisse enthalten
- Ihr NAME (fakultativ, aber eben oft nützlich und meist sowieso gebraucht)
- Ihre NUMMER - d.h. wie der "wahre" Dateiname heißt. NUMMER kann man hier natürlich auch durch STARTPOSITION ersetzen, wenn man z.B. mit einer "Image File"-ähnlichen Struktur arbeitet. Gemeint ist also einfach, wo der INHALT zu finden ist.
- Evtl (aber nicht notwendigerweise nötig) die Größe der Daten
- "Flags". Nicht unbedingt gebraucht, aber für ein Forum evtl nützlich. Diese können beispielsweise Nutzungsrechte oder Mindest-Userlevel u.ä. angeben. Genauere Angaben sind hier möglich, wenn man weiß, welche Features das Forum haben soll.

Um ein wenig "Sicherheit" zu haben, kann man die Files auch nicht direkt benennen, sondern die den wahren Filenamen durch einen Hash bilden lassen, den man über Nummer, kombiniert mit einem (nur dem Foremnbetreiber bekannten) "Bias-Wert" bildet... (Ist nur ein Vorschlag.) Zusätzliche Verschlüsselung der Daten kann natürlich ebenfalls nie schaden.
Zur Vermeidung des seltenen Falls, daß unterschiedliche Nummern denselben Hash ergeben, hätte ich auch schon Lösungen anzubieten (eine davon ist, die Nummer einfach zu überspringen). Neu anzulegende Daten erhalten einfach fortlaufende Nummern. Natürlich kann man diese Nummern auch nach anderen Algorithmen vergeben. Wer aufgepaßt hat: Sie sind sowieso nur ein INDEX, der lediglich der eindeutigen Zuordnung dient. Die Nummern selbst haben dabei keine besondere Bedeutung für den Dateninhalt und auch keine weitergehende Beziehung zu demselben.

Die ganze Baum-Struktur beginnt, wie immer, mit der "Wurzel", die ein Verzeichnis ist (eben das "Root"-Verzeichnis - ja, jetzt wird langsam klarer, worauf die Übung hinausläuft, oder?)
Dieses hat die Nummer 0 - und ausgehend davon kann dann jedes andere Unterverzeichnis oder (über "Weiterhangeln" in den Unterverzeichnissen) enthaltene Daten gefunden werden. Man geht also zwar über mehrere Stufen des Baums und kann auch bei Bedarf feststellen, wo genau sich die Elemente befinden. Aber die Indizes sind (eleganterweise) lediglich EINDIMENSIONAL - so daß man also schlimmstenfalls einen Mini-Stack (eindimensionales Array o.ä.) bräuchte, um wirklich die "Kette" zurückzuverfolgen.
Eine andere Lösung (die eben NICHT MAL diesen Mini-Stack braucht), wäre, zu den Verzeichnisdaten ein weiteres Datum einzuführen: das der VORHERIGEN_NUMMER. Dieses dient dann dazu, jederzeit von jedem Punkt zurückverfolgen zu können, "woher man kam".

Achtung! Die Arbeit mit solchen indirekten Indizes ("Node Pointern") erfordert einige Sorgfalt beim Programmieren! Falsch eingeordnete Knoten können den ganzen Baum durcheinanderbringen. Schlimmstenfalls führen sie (durch "Back Loops") zum "Totlaufen" eines Such-Systems! Es gibt aber Mittel und Wege, um dem vorzubeugen oder dies zu reparieren. (Schließlich gibts ja auch Programme, die völlig defragmentierte Festplatten mit teils falschen Verlinkungen zum großen Teil regenerieren können.)

Eine naheliegene Lösung wäre die doppelte Datensicherung. Beispiel: Die Baumstruktur wird andernorts in vereinfachter Form nochmals gespeichert. Bei der Reparatur fehlerhafter Strukturen werden nun die Vorwärts- und Rückwärtszeiger des Baums, sowie die Vorwärts- (und evtl vorhandene Rückwärts!) Zeiger der "gespiegelten" Baumstruktur geprüft. Das wären vier Zeiger. Wenn drei davon ein konsistentes Bild ergeben und einer nicht, ist der eine der falsche. Achja - um da sicherzugehen, kann man natürlich auch noch mit Checksummen arbeiten...

Hinweis zum Schluß: Ein Forum habe ich selbst noch nicht programmiert - aber eben viele andere funktionierende Dinge.

Hm... In welcher Programmiersprache soll das Ganze denn stattfinden? (Was "web-basierte" Sprachen angeht, könnte ich z.B. nur mit PHP dienen.)

Vielleicht hat der kleine Text etwas weitergeholfen. Es war höchstwahrscheinlich wieder mehr Information als nötig gewesen wäre. Ich hoffe, ich habe trotzdem nicht alle nur gelangweilt.
(Falls noch Fragen bezüglich der Umsetzung vorhanden wären, kann ich da gerne noch weiterhelfen.)

[Poison Nuke]

danke für die sehr ausführliche Antwort :)

aber hättest du nicht vorher nachfragen können, was ich schon gemacht habe? dann hättest du dir ne ganze Menge text ersparen können :eek:


also, das Forum arbeitet mit Zeigern, allerdings nur mit Rückwärtszeigern, weil bei belieger Stufenbreite sind vorwärtszeiger nicht realisierbar, da nicht im Node selbst verwaltbar.

Also, mein Root ist Zeiger 0, dann hat jedes Element einen eindeutigen Index und in jedem Element steht dann das Vorgängerelement drin. Bei den Hauptforen ist es also 0, da sie im Root sind, und alle anderen ordnen sich da unter. da die Elemente im Root den Rückwärtszeiger 0 haben, ist auch eindeutig feststellbar, wo der Baum anfängt, diese Prüfung ist immer die erste bei meinen Abfragen.


Das Problem mit den Kreisverweisen hatte ich auch schon mal im Kopf, allerdings müsste da ein Fehler in der Datenbank entstehen, weil rein vom Programmcode ist es absolut unmöglich, dass sowas entstehen kann. Und wenn es mal passierern sollte, dann hab ich ja den Vorteil, dass in PHP (jop, mit dieser Sprache wird gearbeitet) die Ausführung nach 30sek beendet wird. Man kann also im Fall der Fälle einfach dann in die Verwaltungsoberfläche rein und den Link manuell korrigieren.


also, die Struktur besteht zumindest, an dieser wird auch nix geändert. Sie ist in meinen Augen schon recht ähnlich zu einem Dateisystem im Aufbau, nur das es bei mir 3 Klassen gibt: Foren, Threads und Postings. Bei einem Dateisystem wären das also Ordner/Dateien/Daten in den Dateien.


Problem bei der rekursiven Arbeit im Baum ist nun halt, ich muss immer linear die Tabelle durchlaufen, um herauszufinden, welche Elemente zum gerade übergeordneten Element gehören, da wie gesagt die Sache mit den Vorwärtszeigern in einem Nicht Binären Baum einfach etwas "unhandlich" ist, wie ich finde, bzw ich finde keine wirkliche saubere Lösung.

Denn der Vorteil von der Nichtexistenz von Vorwärtszeigern ist ja, dass ich jeden Eintrag wie ich will an jede Stelle verschieben kann, und an jeder Stelle neue Einträge erzeugen kann usw. Wenn ich nun Vorwärtszeiger hätte, müsste ich bei jeder dieser Aktionen das übergeordnete Element aktualisieren, was dann schonwieder eine Quelle für eventuelle Fehler sein könnte (falsche ID im Vorwärtszeiger gespeichert, oder falschen Zeiger gelöscht usw).

daher will ich darauf einfach verzichten, es ist mir zu unsicher (vorallem weil ein einfacher Fehler bei der Skriptausführung reicht, damit der Fehler reinkommt....nehmen wir an, ich verschiebe Threads, diese haben dann einen neuen Rückwärtszeiger, aber während nun das Skript die Vorwärtszeiger anpassen will, gibt es einen Servererror oder was auch immer. Tja, dann klappt erstmal gar nix mehr so recht.
Also negativ, keine Vorwärtszeiger.
Nur eigene ID und Rückwärtszeiger, so wie es auch aktuell aussieht.



Dennoch will ich erstmal jetzt selbst überlegen, wie man es machen könnte. Da ich ja jetzt weiß, dass es iterativ wie auch rekursiv lösbar ist, will ich auch meinen eigenen Gehirnschmalz aufbringen, um das Problem zu lösen, weil wenn es dann am Ende klappt, wie man es sich denkt, dann macht es am meisten Spaß.
Sollte ich bei der Lösung irgendwann doch nicht weiterkommen, dann komme ich auf dein Angebot zurück :)

[Xpyder]

Hatte dazu eine ausführliche Antwort geschrieben, die ist aber schon wieder 11kB groß geworden. Kanns bei Bedarf ja nachreichen.
Nur soviel:
Nein, vorwärtsgerichtete Zeiger bedeuten in dem Fall nicht, daß die Elemente nicht "beliebig breit" sein können.
Verzeichnisse, genau wie Daten (also Forum, Thread, Posting) enthalten ALLE Daten, die Daten des Postings sind das Posting selbst, die Daten von Foren und Threads wären in dem Fall Listen, bestehend aus Verweisen auf weitere (Sub)Foren, Threads oder Postings.
(Im Falle eines Threads würden in einer solchen Liste natürlich nur Postings auftauchen, keine Foren.)

Und, wie gesagt, um dem Problem mit dem Daten schreiben und Abstürzen (für genau solche Fehler ist ja der angesprochene Datensicherheits-Kram gedacht) gibt es verschiedene Lösungsansätze.

Und, ja: Vom Programm her dürfen so falsche Verknüpfungen gar nicht entstehen. Ich sagte ja auch nicht, daß sie das tun. Sondern nur, daß man aufpassen muß.
Es soll ja schon vereinzelt vorgekommen sein, daß Programme schwer nachvollziehbare (da nur in bestimmten kaum reproduzierbaren Situationen auftretende) Bugs enthalten haben.
Wäre ja äußerst ärgerlich, wenn man so einen Bug dann erst 6 Monate, nachdem das Forum läuft, findet und dann 200 MB Daten anfangen muß, "zu Fuß" zu reparieren...
(Murphy's Law: Komplexe Systeme neigen zu komplexen Fehlern.)
Wollt's nur gesagt haben.

[Poison Nuke]

hm, aber mir missfällt das System der Vorwärtszeiger auf beliebig breite Äste dennoch irgendwie. Es ist halt ne ganze Menge Aufwand notwendig, um die möglichen Fehler abzufangen.

Dann doch lieber ausschließlich Rückwärtsfehler, dafür aber absolut keine Probleme, bis auf den "Kreisverkehr", aber das abzusichern ist ja nicht mehr so umfangreich.


und da meine "Recount" Funktion ja so oder so den kompletten Baum durchforsten muss, wäre es glaube nicht so schlimm, wenn man auf die Performancevorteile von Vorwärtszeigern verzichtet. Diese Funktion soll ja eh nur nach komplexeren Arbeiten am Forum aufgerufen werden und kommt keinesfalls in "alltäglichen" Abfragen vor.

ansonsten hab ich ja im Forum keine weiteren Aktionen, die von Vorwärtszeiger profitieren würden. Auch die Suchfunktion würde davon nicht wirklich profitieren, da bei der ja der Hauptteil der Abfrage dass Suchen im Text ist, als die Abfrage der Postings usw.
(sieht man gut im Taskmanager: SQL verbraucht bei komplexen Abfragen gerade mal 2-3% oder so, wohingegen der Apache schon bei 40-50% liegt, IMHO heißt das wohl, dass das PHP Skript selbst viel arbeitet, die Datenbankabfragen aber in Grenzen bleiben.)



oder gibt es außer der Perfomance noch andere Gründe für die Verwendung von Vorwärtszeigern?

[Xpyder]

Also, wie performant die ganze Geschichte ist, hängt dabei wohl stark von der Art der Implementierung des Ganzen ab - aber im Falle von so Skript-Kram wie PHP wohl ohnehin noch viel stärker von der Qualität des Interpreters...
Hab das alles im "11k Text" geschrieben, fasse mal kurz n paar Punkte zusammen:

1) Bei Bäumen mit "gleichwertigen" Knoten ist die Richtung der Zeiger völlig egal.
Die hier betrachtete Struktur ist jedoch hierarchisch, d.h. sowas wie
Gruppe > Forum > Unterforum > Unterforum > Thread > Posting(s)
Bei hierarchischen Strukturen ist die logischere Wahl eigentlich die "von oben nach unten".
(Man weiß, in welchem Forum man sich befindet, sucht dann das passende Unterforum und darin die passenden Beiträge...
So wie in einem Dateisystem eben. Man geht von oben nach unten in die Verzeichnisse.
Der umgekehrte Fall (mit "Rückwärtszeigern") entspräche diesem Bild: Man hat eine Festplatte voller Dateien und bei jeder Datei muß man über das Springen "von Uplink zu Uplink" feststellen, in welchem Verzeichnis(pfad) sie sich befindet.
Funktioniert zwar auch - ist aber nicht so wirklich die wahre Lehre, zumindest imo.

2) Die Anzahl möglicher Fehler beim Vorwärts-verlinken ist gleich der Anzahl möglicher Fehler beim Rückwärts-verlinken.

3) Wenn ohnehin jedesmal für alles die komplette Datenbank durchsucht werden muß, ist weder Einsatz von Bäumen, noch von Rekursion oder Iteration irgendwie gerechtfertigt und verkompliziert nur das Ganze.
Einfacher wäre wohl in dem Fall, einfach alle Daten "plain" irgendwo sequentiell hinzulegen, immer mit entsprechenden Headern (Datenköpfen), aus denen die Daten, Flags und Zugehörigkeiten ersichtlich sind und dann bei jeder Abfrage die komplette Datenbank zu durchforsten auf der Suche nach allem, was auf das gewünschte Suchmuster paßt.
Die Performance wäre wohl dieselbe (wenn nicht sogar besser) als die eines (nicht richtig genutzten) Baums und die eventuellen "im Kreis verlinken" Fehler könnten dann ausgeschlossen werden.

(Anmerkung: Wenn man sich einen Sportwagen mit 5-Gang-Getriebe kauft, der auf guten Straßen 320 km/h Spitze fährt, könnte man damit natürlich auch die ganze Zeit im Rückwärtsgang durch den Wald fahren, aber das kann man eigentlich auch ohne Sportwagen haben...)

[Poison Nuke]

aber so gesehen ist es bei SQL ja eh egal, mit welcher Art von Zeigern ich arbeite, SQL geht so oder so die gesamte Datenbank durch. Denn ob ich nun ein untergeordnetes Forum anhand dessen ID suche, die im Vorwärtszeiger steht, oder ob ich ein Forum suche, dessen Rückwärtszeiger auf das aktuelle zeigt, ist rein von der Performance bei SQL egal, genauer gesagt wäre sogar die Methode mit den Rückwärtszeigern bei SQL schneller, denn es gibt nur ein Suchkriterium, wohingegen bei Vorwärtszeigern jeder einzelne Zeiger das Suchkriterium darstellt...im Falle von einem Unterforum, in dem mehrere tausend bis zehntausend Threads drin sind wird das schon ne "interessante" Suche.


Aber so gesehen arbeitet man bei SQL ja auch nicht mit Bäumen, die interne Verwaltung im Skript handhabt es dann aber so, da es logischer ist.


wenn man mit einem echten Baum arbeiten wollte, müsste die Datenstruktur auch entsprechend so aussehen, dass die Zeiger auf Adressen zeigen und man dann direkt die Adresse anspringen kann, und nicht erst nach dieser suchen muss (obwohl, sogesehen ist das Anspringen einer Adresse auch nix anderes, weil intern wird jede Datenstruktur linear gespeichert und bei jedem Zugriff muss dann irgendeine Instanz suchen, wo die gewünschte Adresse ist).


Ergo: Vorwärtszeiger sind zwar logisch in der Handhabung, aber aus meiner Sicht umständlich, und ich erkenne auch nicht, warum Rückwärtszeiger genauso fehleranfällig sein sollten? :confused:
Bei Rückwärtszeigern ist nur ein einziger Fehler möglich: Kreisverkehr. Bei Vorwärtszeigern hingegen gibt es nebem diesem Kreisverkehr noch die Möglichkeit, dass Unterbereiche doppelt verlinkt sind, oder dass Bereiche gar nicht verlinkt sind.




achja, wie arbeitet eigentlich das Dateisystem bei Windows? Mit Vorwärtszeigern oder Rückwärtszeigern?

[cracki]

einfach rekursiv = iterativ

mehrfach rekursiv = stack unabdingbar

jede sprache mit prozeduren hat nen stack. die rekursion der sprache sollte man nutzen und sie nicht auf einen selbstbau-stack verlagern.

ich hoffe fuer euch, dass das schon gesagt wurde. wenn nicht, mein midleid habt ihr.

[Jan Krüger]

jede sprache mit prozeduren hat nen stack. die rekursion der sprache sollte man nutzen und sie nicht auf einen selbstbau-stack verlagern.
Dafuer gibt es einige Ausnahmen. Beispielsweise haben einige Embedded-Systeme laecherlich wenig Stackspeicher. Da kann man bei diversen Algorithmen nicht darauf verzichten, etwas selbstzubauen. Beispielsweise ist bei Palm OS die integrierte Quicksort-Methode iterativ.

[Poison Nuke]

So, hab mir heut mal Zeit genommen, und erstmal den Algo, wie er sein sollte, fertig gestellt.

Funktioniert zumindest einwandfrei, nur ich glaub in nem sehr großen Forum könnte er eventuell den Server ganz schön belasten :o :rolleyes: :D


diese Funktion wird aber nur dann aufgerufen, wenn umfangreichere verschiebe und Löschaktionen vorgenommen wurden, weil das manuelle Aktualisieren jedes einzelnen Forums usw bei solchen Aktionen finde ich ganz schön unsauber. Wenn man es ordentlich macht, sollte es ja eigentlich funktionieren, aber bei dieser Funktion hier kann ich wenigstens 100% sicher gehen, dass alle Foren wieder perfekt stimmen.
Und irgendwie ist es mir vom Gefühl her lieber, wenn ich alles durchzählen lasse, als wenn ich dann vorhande Werte rauf und runteraddiere und subtrahiere und lösche und update und .... ach ne :cool:


ist halt nur viel Quelltext...



//zählen, wieviele Threads und Postings in jedem Unterforum sind
//aktualisieren des letzten Threads und der Statistiken eines jedes Forums



function UFo($FID) {
global $LastUID, $LastTime, $LastThread, $Threads, $Postings;
global $UFO, $Level;
global $Resultcount;

//gibt es weitere Unterforen?
for ($z=1; $z<=$Resultcount; $z++) {
if ($UFO[$z]['vFID']==$FID) {
//wenn ja, dann Level erhöhen, und neue Indizes anlegen
$Level++;

$LastUID[$Level]=0;
$LastTime[$Level]=0;
$LastThread[$Level]=0;
$Threads[$Level]=0;
$Postings[$Level]=0;

UFo($UFO[$z]['FID']);

$Level--;
}
}

//schauen, was in diesem Unterforum an Threads und Postings vorhanden ist

$query=mysql_query("SELECT * FROM Threads WHERE FID=".$FID);
$Anzahl=@mysql_num_rows($query);
if ($Anzahl>0) {
for ($z=1; $z<=$Anzahl; $z++) {
$Thread=mysql_fetch_assoc($query);
//nachdem der Thread geladen ist, wieviele Postings enthält er, und welches ist das letzte Posting?
$Pquery=mysql_query("SELECT count(PID) FROM Postings WHERE TID=".$Thread['TID']);
$PostCount=mysql_result($Pquery,0);
$Pquery=mysql_query("SELECT Zeit, UID FROM Postings WHERE TID=".$Thread['TID']." ORDER BY Zeit DESC");
if ($Pquery) {
$LastPost=mysql_fetch_assoc($Pquery);
} else {
$LastPost['Zeit']=0;
}

//Stats für jeden Thread in diesem Unterforum aktualsieren
if ($Thread['LastTime']<$LastPost['Zeit']) {
$Tquery=mysql_query("UPDATE Threads SET countPosts=".$PostCount.", LastTime=".$LastPost['Zeit'].", LastUser=".$LastPost['UID']." WHERE TID=".$Thread['TID']);
} else {
$Tquery=mysql_query("UPDATE Threads SET countPosts=".$PostCount." WHERE TID=".$Thread['TID']);
}


//Stats für jede Ebene aktualisieren
for ($L=$Level; $L>0; $L--) {
$Threads[$L]++;
$Postings[$L]=$Postings[$L]+$PostCount;
if ($LastPost['Zeit']>$LastTime[$L]) {
$LastUID[$L]=$LastPost['UID'];
$LastTime[$L]=$LastPost['Zeit'];
$LastThread[$L]=$Thread['TID'];
}
}

}
}

//nachdem auf dieser Ebene alles gezählt wurde, die Werte in die Statistiken dieses Forums eintragen
//außer die Funktion befindet sich im Rootlevel (Forum 0 existiert ja in dem Sinne nicht in der Datenbank)
IF ($FID>0) {
$query=mysql_query("UPDATE Foren SET
countThreads=".$Threads[$Level].",
countPosts=".$Postings[$Level].",
LastThread=".$LastThread[$Level].",
LastUser=".$LastUID[$Level].",
LastTime=".$LastTime[$Level]."
WHERE FID=".$FID);
if (!$query) {
std_dialog("Fehler beim Aktualisieren", mysql_error(), "", "", "");
die();
}
}

}




//Stackvariablen vordefinieren
//müssen als global definiert werden, damit sie für die nächste Funktion zur Verfügung stehen, ohne dass dazu diese Variablen
//außerhalb dieser Funktion definiert werdne müssten.
global $LastUID, $LastTime, $LastThread, $Threads, $Postings;
global $UFO, $Level;
global $Resultcount;




//alle Foren in $UFO laden
$query=mysql_query("SELECT * FROM Foren");
$Resultcount=mysql_num_rows($query);
for ($i=1; $i<=$Resultcount; $i++) {
$UFO[$i]=mysql_fetch_assoc($query);
}

//und los gehts, Start der Funktion auf Rootebene
$Level=0;
UFo(0);




//bei der rekursiven Aktualisierung des Forums werden zuerst die Rootforen gesucht. Wenn eins gefunden würde,
//werden die Stackvariablen auf Null gesetzt. Danach wird die rekursive Funktion aufgerufen. Diese Funktion sucht nun nach
//weiteren Unterforen. Wurde eins gefunden, ruft sie sich selbst auf und sucht wiederrum nach unterforen.
//gibt es keine weiteren Unterforen, zählt die Funktion alle Threads im Unterforum.
//danach zählt sie alle Postings in den Threads.
//danach wird ermittelt, welches der Postings das aktuellste ist, samt dem Beistzer
//wenn die unterste Instanz fertig ist, trägt diese die gefundenen Werte in das ihr übergebene UFO ein
//da die Werte ebenfalls global gespeichert sind, dienen sie als Berechnungsgrundlage für die sie aufrufende Funktion, welche ebenfalls auf ihrer Ebene nun
//nach allen Threads und Postings durch. Dabei wird die Anzahl immer dazuaddiert, die letzten Einträge werden
//vorher aber verglichen
//
//um auch die Statistiken auf jeder Ebene zu aktualisieren, gibt es neben den primären Stackvariablen auch noch weitere
//welche in einem Array gespeichert sind.
//dabei wird für jede neue Ebene ein neuer Arrayindiz angelegt.
//wenn es auf der Ebene weitergeht, dann wird der Inhalt dieses Indizes auf Null gesetzt, damit beim nächsten
//Ast wieder gezählt werden kann
//über $Level wird dabei mithilfe einer globalen Variable gezählt, auf welcher Ebene im Baum man sich gerade befindet





ob man hier überhaupt mit ner iterativen Version anfangen sollte? Weil so wie ich das sehe, scheint hier die meiste Performance an den Datenbank zugriffen zu hängen, und da ich so oder so jeden Thread zählen muss :Y