Iteration oder Rekursion
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
aufruf
befehlen
beispiel
date
datei
daten
fragen
funktion
gewinnen
lehrer
ordner
rekursion
sekunde
sen
speicher
stack
typische parade
verzeichnis
vier
wesentlichen performance
-
Hi Leute
Ich habe ein Script geschrieben das mir aus jeder Datei das ?nderungsdatum auslie?t, sortiert und das h?chste das ich habe ist dann mein aktuelles Homepage Update (so wie auf meiner Seite http://www.elpra.de rechts unten).
Ich lasse das script alle vier Stunden per Cronjob ausf?hren und in eine Datenbank schreiben, weil es einfach Ladezeit kosten w?rde, da das Script doch einige Sekunden braucht zum ablaufen.
Daher eine Frage, mehr so aus Interesse:
L?sst sich das Problem auch durch Iteration l?sen und wenn ja, bring das einen wesentlichen Performance Gewinn?
Vielen Dank.
Gru? Tobi -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Du machst das doch bereits iterativ. Oder meintest du rekursiv?
Dein Skript l?uft viel zu lange, f?r die paar Sachen, die da gemacht werden. Wenn du etwas deutlicher beschreibst, wie dein Code aussieht (am besten in Pseudocode), kann man vielleicht schon rausfinden, was bei dir so lange dauert. -
Hi
Ne ich mach das rekursiv.
Also ich beschreib mal den Pseudocode (PS: mir gehts eigentlich gar nicht so um die Performance, sondern mehr um die Theorie iterativ und rekursiv
).
Also:
(mit var bezeichne ich die Variablen die als Referenz ?bergeben werden)
$daten vom Typ Array;
funktion datumsuche(var $daten, $ordner)
{
verzeichnis $ordner ?ffnen
while $datei = $ordner lesen
{
wenn $datei existiert dann
{
$daten[index] = dateidatum;
{
$tempordner = $startdir + "/" + $datei;
wenn verzeichnis $tempordner existiert dann
{
datumsuche ($daten, $tempordner);
}
}
}
// das w?re die Hauptfunktion. Es existiert noch eine kleine Nebenfunktion,w elche allerdings nur die Dateinamen etwas konvertiert um sie den PHP befehlen kompatibel zu machen
//aufgerufen wird das ganz nun so (richtige PHP Code)
$daten = array();
$startdir = '..';
$aktuelldir = $startdir;
datumsuche($daten, $startdir);
rsort($daten);
// und nun ist $daten[0] mein neuestes Datum von allen
-------------------------------------------------------------------
So hab ich das ganze nun gel?st, funktioniert auch einwandfrei.
Jetzt gab es folgendes in der Schule:
Ich: Herr Lehrer, machen wir auch mal das Thema Rekursionen und ?bungen dazu.
Lehrer: Nein, Rekursionen sind zu schwer, kapiert eh keiner, wird heute eh alles iterativ gemacht weil es schneller ist.
Ich: Was ist iterativ?
Lehrer: Durch probieren, mu? mal da r?ber ....
Na toll, jetzt wei? ich wirklich was iterativ ?berhauot sein soll. Naja durch etwas googlen bin ich halt draufgekommen, das iterativ wirklich durch probieren ist und man immer eine Stufe weitere geht bis einem das Ergebnis gut genug erscheint.
Daher wollt ich wissen wir ich den Code iterativ schreiben kann, da der Lehrer ja meint das geht mit jeder rekursion. Und ob es schneller w?re.
(Mir sind eh ein paar Dinge eingefallen wie ich den Algorithmus schneller machen kann).
Gru? Tobi
PS: irgendiwe wusste ich das 0-Checka sich hier sofort meldet ;) -
Ich habe ein Script geschrieben das mir aus jeder Datei das ?nderungsdatum auslie?t, sortiert und das h?chste das ich habe ist dann mein aktuelles Homepage Update (so wie auf meiner Seite http://www.elpra.de rechts unten).
Wenn du nur das h?chste Datum haben willst brauchst du nicht zu sortieren.
Ich lasse das script alle vier Stunden per Cronjob ausf?hren und in eine Datenbank schreiben, weil es einfach Ladezeit kosten w?rde, da das Script doch einige Sekunden braucht zum ablaufen.
Einige Sekunden???
Wie viele Dateien hast du denn???
Also das halte ich schon f?r sehr komisch.
Daher eine Frage, mehr so aus Interesse:
L?sst sich das Problem auch durch Iteration l?sen und wenn ja, bring das einen wesentlichen Performance Gewinn?
Iteration und Rekursion lassen sich von der einen in die andere ?berf?hren.
Und in wesentlichen werden die selben Operationen durchgef?hrt.
Somit sind beide ungef?hr gleich lang. Allerdings verbraucht Rekursion oft mehr Speicher ist daf?r aber in manchen F?llen wesentlich einfacher zu Programieren.
Edit
Ach ja Iterativ k?nnte man das mit einen Stack machen.
stack.put = getOrdner;
datei = stack.pop
lastDate= datei.date
while (!stack.leer){
datei = stack.pop
if(datei == ordner) {
stack.put = datei.getOrdner
}
if (lastDate > datei.date){
lastDate = datei.date
}
}
P.S. zu dem was dein Lehrer sagt, sage ich besser mal nichts.
Jens -
jacr schrieb:
Wenn du nur das h?chste Datum haben willst brauchst du nicht zu sortieren.
Mu? ich nicht ganz, aber wenns den Befehl schon fertig in PHP gibt, wieso dann nicht auch gleich verwenden?
jacr schrieb:
Einige Sekunden???
Wie viele Dateien hast du denn???
Also das halte ich schon f?r sehr komisch.
Einige Sekunden sind bei meinem Script ca *nochmal test* ....
Olla was geht jetzt. War jetzt vielleicht ne halbe Sekunde nur. War der Server irgendwie gestern lahm?
Es sind 1133 Dateien um genau zu sein. Liegt am Forum und am g?stebuch Script. Die sind nat?rlich geklaut, daher hab ich soviel Dateien ;)
Mit der Rekursion und Speicher Sache:
Wenn meine Page w?chst werd ich sicher bald an Grenzen sto?en, da ein Script ja nur begrenzten Speicher in Anspruch nehmen darf, oder?
Eigentliches Thema in diesm Thread sollte eigentlich sein:
Iteration - Rekursion., was schneller und "Was genau ist Iteration, wie wendet man es an und was sind so typische Parade Iteration Beispiele".
Gru? Tobi -
Iteration - Rekursion., was schneller und "Was genau ist Iteration, wie wendet man es an und was sind so typische Parade Iteration Beispiele".
Jeder andere w?rde Fragen was Rekursion ist.
Vielleicht schaust du mal hier:
http://de.wikipedia.org/wiki/Iteration
Es ist zwar nur ein kleiner Teil welcher sich mit Programmen besch?ftigt, aber das andere ist auch lesenswert.
Ach ja.
Mit Iteration hattest du bestimmt schon zutun.
Jede For-Schleife ist eine Iteration.
Genau so wie While- und Until- Schleifen.
Eigendlich lernt man zuerst Iteration.
Jens -
Iteration - Rekursion., was schneller und "Was genau ist Iteration, wie wendet man es an und was sind so typische Parade Iteration Beispiele".
Jeder andere w?rde Fragen was Rekursion ist.
Was in der Mathematik eine iteration ist wei? ich ja (Beispiel: Newtonsches N?herungsverfahren), aber mit dem Begriff Iteration im Sinne der Informatik kont ich bis jetzt halt nix anfangen =(
hoffentlich ?ndert sich das ;)
Gru? Tobi
PS: Bitte nicht wundern, hab ausversehen falscher Button geklickt um Jacrs Beitrag zu zitiere. Ich hoffe er schreibt es nochmal ;) SRY JACR!!!!
Edit jacr
Du weisst nicht was f?r ein schlechtes Ged?chniss ich habe. :D
Aber ich habe mal wieder was hingeschreiben.
Gru? Tobi -
Alsoooo... f?r den Unterschied zwischen Iteration und Rekursion hast du dir das denkbar schlechteste Beispiel ausgesucht, dann das Durchsuchen von Verzeichnisstrukturen kann man iterativ nur machen, wenn man GOTO-Befehle benutzt (ich weiss jetzt nicht einmal, ob es die unter PHP ?berhaupt gibt) oder mehrdimensionale Felder zur Zwischenspeicherung aufbaut. Vielleicht solltest du dir ein anderes Beispiel raussuchen *g*
Ganz allgemein wegen der Performanceunterschiede bei Iteration und Rekursion:
Rekursionen sind langsamer, weil f?r jeden Aufruf und Return der Funktion der Stack manipuliert werden muss, um die Parameter der Funktion und R?ckgabewerte zwischen zu speichern bzw. diese Werte von ?lteren Aufrufen der Funktion wieder in den Stack zu schieben. Diese gilt f?r Sprachen wie C, Pascal, Delphi, Java, etc.. Ob das aber auch f?r PHP gilt, weiss ich nicht. Es k?nnte sein, das der PHP-Parser alles nur auf einen eigenen "Stack" schiebt, was dann eigentlich nicht viel lansamer sein sollte als andere Speicherstellen bei einer iterativen Programmierweise zu manipulieren. Aber dazu m?sste man mal in den PHP-Code (also den des Parsers) schauen. Download unter www.php.net
Ich hab da jedenfalls keinen Bock zu
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
