Algorithmus optimieren

[levu]

Den folgenden Algoritmus verwende ich, um ein Array zu generieren, in welchem die Pfade drinnen stehen, in denen ich Klassen in __autoload suche. Am Anfang steht was drin wie "./plugins/" oder "./classes/". Der Algorithmus geht nun diese Verzeichnisse durch und guckt, ob sie noch Unterverzeichnisse haben. Wenn ja werden auch diese wieder analysiert.

Das Problem ist, dass man in einer Schleife nichts zum Array hinzufügen oder aus dem Array entfernen kann, über das man iteriert. Deswegen einige Hilfsarrays.

Geht der Code noch effizienter/kürzer ohne Rekursion?

    function autoload_paths_update() {  
        $check = $GLOBALS['autoload_paths'];  
        $new = array();  
        while(count($check) > 0) {  
            $add = array();  
            $remove = array();  
            foreach($check as $key=>$path) {  
                $items = scandir($path);  
                $subdirs = array();  
                foreach($items as $item) {  
                    if (is_dir($path.$item) && substr($item, 0, 1) != '.') {  
                        $subdirs[] = $path.$item.'/';  
                    }  
                }  
                foreach($subdirs as $sd) {  
                    $add[] = $sd;  
                }  
                $remove[] = $key;  
                $new[] = $path;  
            }  
            foreach($remove as $key) {  
                unset($check[$key]);  
            }  
            foreach($add as $a) {  
                $check[] = $a;  
            }  
        }  
        $GLOBALS['autoload_paths'] = $new;  
    }

[Bademeister]

Hi Flo.

Am Anfang steht was drin wie "./plugins/" oder "./classes/". Der Algorithmus geht nun diese Verzeichnisse durch und guckt, ob sie noch Unterverzeichnisse haben. Wenn ja werden auch diese wieder analysiert.

Da wirst Du Dir das Leben erheblich leichter machen, wenn Du die Funktion rekursiv aufrufst.

Das Problem ist, dass man in einer Schleife nichts zum Array hinzufügen oder aus dem Array entfernen kann, über das man iteriert.

1.: Doch, das kann man. Warum sollte man es nicht koennen?
2.: Warum willst Du eigentlich etwas aus einem Array (dem Array $check) entfernen?

Geht der Code noch effizienter/kürzer ohne Rekursion?

Ginge auch ein bisschen kuerzer ohne. Aber: Warum denn ohne?

Nochmal ein paar Sachen zum Code. Eins vorneweg: Er ist annaehernd unlesbar, weil nicht kommentiert. Da solltest Du Deine Gewohnheiten dringend aendern.

function autoload_paths_update() {

$check = $GLOBALS['autoload_paths'];

// Warum uebergibst Du $autoload_paths nicht als Parameter?

$new = array();
        while(count($check) > 0) {

// Du solltest per foreach-Schleife ueber das Array, das Du ausliest iterieren (s.o.), und in ein anderes Array Deine Ausgabe schreiben. Das erspart Dir einiges an Schleifen.

$add = array();
            $remove = array();
            foreach($check as $key=>$path) {
                $items = scandir($path);
                $subdirs = array();
                foreach($items as $item) {
                    if (is_dir($path.$item) && substr($item, 0, 1) != '.') {
                        $subdirs[] = $path.$item.'/';
                    }
                }

foreach($subdirs as $sd) {
                    $add[] = $sd;
                }

// wozu das Array $add bauen, wenn es am Ende == $subdirs ist, und wozu dann auchnoch so umstaendlich?

$remove[] = $key;
                $new[] = $path;
            }
            foreach($remove as $key) {
                unset($check[$key]);
            }
            foreach($add as $a) {
                $check[] = $a;
            }
        }

// Alles ueberfluessig, s.o.

$GLOBALS['autoload_paths'] = $new;

// NEIN, NEIN, NEIN!

}

  
Deine Funktion hat keine globalen Variablen zu veraendern - jedenfalls nicht, so lange der Benutzer der Funktion (das aufrufende Skript) das nicht explizit erlaubt, in dem er einen Pointer auf die Variable uebergibt. Lass die Funktion einfach ein Array mit den ganzen Verzeichnissen zurueckgeben. Und nenne sie dann danach, was sie eigentlich tut. Sie hat per se nichts mit irgendwelchem autoload zu tun, also nenne sie eher sowas wie scan\_paths\_recursive o.ae.  
  
Oder: Lass die Autoload-Funktion selber die ganze Arbeit machen und das erzeugte Array in einer statischen Variable speichern.  
  
  
Viele Gruesse,  
der Bademeister

[levu]

Hi Flo.

Am Anfang steht was drin wie "./plugins/" oder "./classes/". Der Algorithmus geht nun diese Verzeichnisse durch und guckt, ob sie noch Unterverzeichnisse haben. Wenn ja werden auch diese wieder analysiert.

Da wirst Du Dir das Leben erheblich leichter machen, wenn Du die Funktion rekursiv aufrufst.

Ja, ich wollte es eigentlich als Lambda-Funktion und deswegen ohne parameter und nicht rekursiv. Ich werde es jetzt rekursiv machen.

Das Problem ist, dass man in einer Schleife nichts zum Array hinzufügen oder aus dem Array entfernen kann, über das man iteriert.

1.: Doch, das kann man. Warum sollte man es nicht koennen?

weil sich php z.B. merkt "ich bin beim 3. Element" und wenn du jetzt das 2 löschst, hast du als nächstes das 4. (original das 5.) und das ehemalige 4. damit übersprungen

Nochmal ein paar Sachen zum Code. Eins vorneweg: Er ist annaehernd unlesbar, weil nicht kommentiert. Da solltest Du Deine Gewohnheiten dringend aendern.

Ja, das war nur schnell runtergetippt ;) sonst is er auch lesbarer inkl guten Variablennamen

Oder: Lass die Autoload-Funktion selber die ganze Arbeit machen und das erzeugte Array in einer statischen Variable speichern.

statt statisch nehme ich immer globale Variablen - statische sind aber auch ne gute idee :)

Mein neuer Code:

    function get_dirs_recursive($directory) {  
        $new = array();  
        $items = scandir($directory); //we have all items - even files  
        foreach ($items as $item) { //now we iterate over $items  
        //and we only want to have directories not starting with an .  
            if (is_dir($directory.$item) && substr($item, 0, 1) != '.') {  
                //we add the current subdirectory...  
                $new[] = $directory.$item.'/';  
                //...and all the ones below  
                $new = array_merge($new, get_dirs_recursive($directory.$item.'/'));  
            }  
        }  
        return $new;  
    }

Wie gesagt - es war der Versuch, so etwas als Lambda Funktion zu schreiben ;)

[Bademeister]

Das Problem ist, dass man in einer Schleife nichts zum Array hinzufügen oder aus dem Array entfernen kann, über das man iteriert.

1.: Doch, das kann man. Warum sollte man es nicht koennen?
weil sich php z.B. merkt "ich bin beim 3. Element" und wenn du jetzt das 2 löschst, hast du als nächstes das 4. (original das 5.) und das ehemalige 4. damit übersprungen

Hui, jetzt ist mir schwindelig :-) Nein, ernsthaft - so stimmt das nicht ganz.

Wenn Du (vermeindlich) ueber Dein Array $check iterierst, dann iterierst Du in Wahrheit ueber eine Kopie davon, die zu Beginn erstellt wird. Wenn Du innerhalb der Schleife dann was am Array $check aenderst, dann hat das keinerlei Einfluss auf die Schleife, weil $check nichts (mehr) mit der Schleife zu tun hat.

Deine Bedenken koennten sich also hoechstens auf den Fall beziehen, in dem Du tatsaechlich die Struktur, ueber die Du tatsaechlich technisch iterierst, aendern wolltest. Das ist aber erstens sinnlos und zweitens in der Form, wie Du schreibst, annaehernd nicht moeglich. Nur mal so ganz theoretisch:

In einem bestimmten Schleifendurchlauf hast Du i.a. keinerlei Zugriff mehr auf die aktuellen Werte der vorherigen Schleifendurchlaeufe. Mittels der von Dir im Schleifenkopf festgelegten Variable - etwa $thisValue in

(foreach $array as $thisValue) ... -

hast Du Zugriff auf das aktuelle Element, das wars. Um es ueberhaupt zu schaffen, an Werte, ueber die Du bereits iteriert hast, ranzukommen, muesstest Du in dem vorherigen Durchlauf einen Pointer auf $thisValue speichern, etwa

$pointer = &$thisValue;

Das an sich nuetzt auch noch nichts, weil schlicht und einfach dieselbe Variable $thisValue (an derselben Speicheradresse) im naechsten Schleifendurchlauf mit dem aktuellen Wert ueberschrieben wird. Was geht, ist, den Pointer zu setzen und dann $thisValue zu loeschen:

  
$pointer = &$thisValue;  
unset($thisValue);  

Dann wird $thisValue im naechsten Schleifendurchlauf wieder neu (und an anderer Speicheradresse) erzeugt, und $pointer zeigt immer noch auf den alten Speicherplatz. Wenn Du an dem was rumdoktorst, hat es aber auch keinen Einfluss auf den weiteren Verlauf der Iteration. Und ein Skript, das das macht, ist ein Anwaerter fuer den Preis des daemlichsten Skriptes aller Zeiten. Und wenn ich gewusst haette, wie lang die Sache hier wird, haette ich stattdessen lieber Daeumschen gedreht. ;-) Der Rede kurzer Sinn: Deine Bedenken im Hinblick auf das Veraendern eines Arrays innerhalb des Iterationsvorgenages sind unbegruendet. Toll, nicht? :-)

function get_dirs_recursive($directory) {

$new = array();
        $items = scandir($directory); //we have all items - even files
        foreach ($items as $item) { //now we iterate over $items
        //and we only want to have directories not starting with an .
            if (is_dir($directory.$item) && substr($item, 0, 1) != '.') {
                //we add the current subdirectory...
                $new[] = $directory.$item.'/';
                //...and all the ones below
                $new = array_merge($new, get_dirs_recursive($directory.$item.'/'));
            }
        }
        return $new;
    }

  
  
Ich finde, das sieht schon mal deutlich besser aus als die erste Variante. Aber mal aus Interesse: was hast Du eigentlich vor? Soll dann die \_\_autoload-Funktion mal auf gut Glueck alle Dateien in Deinen gefundenen Pfaden einbinden, in der Hoffnung, dass irgendwo darin die gewuenschte Klasse definiert ist?  
  
  
Viele Gruesse,  
der Bademeister  

[levu]

Das Problem ist, dass man in einer Schleife nichts zum Array hinzufügen oder aus dem Array entfernen kann, über das man iteriert.

1.: Doch, das kann man. Warum sollte man es nicht koennen?
weil sich php z.B. merkt "ich bin beim 3. Element" und wenn du jetzt das 2 löschst, hast du als nächstes das 4. (original das 5.) und das ehemalige 4. damit übersprungen

Hui, jetzt ist mir schwindelig :-) Nein, ernsthaft - so stimmt das nicht ganz.

Wenn Du (vermeindlich) ueber Dein Array $check iterierst, dann iterierst Du in Wahrheit ueber eine Kopie davon, die zu Beginn erstellt wird. Wenn Du innerhalb der Schleife dann was am Array $check aenderst, dann hat das keinerlei Einfluss auf die Schleife, weil $check nichts (mehr) mit der Schleife zu tun hat.

Deine Bedenken koennten sich also hoechstens auf den Fall beziehen, in dem Du tatsaechlich die Struktur, ueber die Du tatsaechlich technisch iterierst, aendern wolltest. Das ist aber erstens sinnlos und zweitens in der Form, wie Du schreibst, annaehernd nicht moeglich. Nur mal so ganz theoretisch:
[...] Toll, nicht? :-)

Allerdings - und ich habe meinen Denkfehler gefunden. Ich arbeite normalerweise nicht mehr mit nativen Arrays, sondern mit einer Collection Klasse, die in einem Framework ist, an dem ich arbeite. Da ist es so, dass über die Klasse selber iteriert wird und nicht über eine Kopie derer (durch das Implementieren von Iterator? kann man mit foreach drüber iterieren).
Dort hatte ich das Problem bisher und hab garnicht bedacht, dass das bei Arrays nicht der Fall ist.

function get_dirs_recursive($directory) {

$new = array();
        $items = scandir($directory); //we have all items - even files
        foreach ($items as $item) { //now we iterate over $items
        //and we only want to have directories not starting with an .
            if (is_dir($directory.$item) && substr($item, 0, 1) != '.') {
                //we add the current subdirectory...
                $new[] = $directory.$item.'/';
                //...and all the ones below
                $new = array_merge($new, get_dirs_recursive($directory.$item.'/'));
            }
        }
        return $new;
    }

>   
>   
> Ich finde, das sieht schon mal deutlich besser aus als die erste Variante. Aber mal aus Interesse: was hast Du eigentlich vor? Soll dann die \_\_autoload-Funktion mal auf gut Glueck alle Dateien in Deinen gefundenen Pfaden einbinden, in der Hoffnung, dass irgendwo darin die gewuenschte Klasse definiert ist?  

Nein. So nicht. Das wäre ja ein katastrophaler Designfehler. Die Dateien heißen bei mir <Classname>.class.php . Darin ist jeweils nur diese eine Klasse definiert. Jetzt ist es so, dass manche Klassen im Framework Scope liegen und manche Klassen in Application Scope - und damit in anderen Verzeichnissen.  
Bisher war es einfach, da es genau 4 Verzeichnisse gab, wo Klassen liegen konnten. Jetzt werde ich aber verschiedene Sachen einbauen, wo es notwendig ist, dass Klassen auch in Unterverzeichnissen dieser Verzeichnisse liegen (z.B. liegen die Klassen eines Plugins im Verzeichnis dieses Plugins und nicht im allgemeinen Plugin-Verzeichnis). Also brauche ich alle diese Pfade.  
  
In der Hoffnung, dass nicht alles Hirnlos geklungen hat,  
![](http://levu.phicode.de/html/up/mfgwq.png)

-- 
ie:{ br: fl:( va:) ls:& fo:| rl:( n4:( de:] ss:) ch:| js:| mo:| sh:( zu:)

[Bademeister]

Allerdings - und ich habe meinen Denkfehler gefunden. Ich arbeite normalerweise nicht mehr mit nativen Arrays, sondern mit einer Collection Klasse, die in einem Framework ist, an dem ich arbeite. Da ist es so, dass über die Klasse selber iteriert wird und nicht über eine Kopie derer (durch das Implementieren von Iterator? kann man mit foreach drüber iterieren).

Ok, mit dem Iterator-Interface wäre es schwierig zu implementieren, dass über Kopien iteriert wird. Aber das Iterator-Interface ist m.E. für Implementierungen von Array-Objekten ohnehin unbrauchbar, denn es bringt noch ein anderes gefährliches Problem mit, über das ich mal gestolpert bin:
Wenn man in die Situation kommt, verschachtelte Iterationen machen zu wollen, weil man zum Beispiel über alle Paare von Werten iterieren will:

  
foreach ($myArray as $thisValue1) {  
    foreach $myArray as $thisValue2) {  
         ....  
  
    }  
}  

dann geht das i.a. mächtig schief. Grund - klar - die beiden Schleifen benutzen nicht nur dieselben Werte, sondern auch denselben (virtuellen) internen Zeiger. Das heißt, dass, wenn man nicht einige Verränkungen anstellt, die äußere Schleife nach dem ersten Durchlauf beendet ist, weil der interne Zeiger nach der ersten Abarbeitung der inneren Schleife am Ende des (virtuellen) Arrays steht.

Daher empfehle ich Dir im allgemeinen stark die Implementierung von IteratorAggregate statt Iterator, was dann für jede Schleife einen eigenen externen Iterator erzeugt, der sich mit den anderen nicht in die Quere kommt. Dann ist es i.a. auch wieder problemlos möglich, über eine Kopie der eigenen Daten zu iterieren, um Deinem Daten-Änder-Problem wieder aus dem Weg zu gehen.
Das Iterator-Interface eignet sich nur gut, wenn es sinnvoll ist, verschachtelte Iterationen konzeptionell zu verbieten (und ggf. mit einem Fehler zu würdigen), wie zum Beispiel für das iterative Auswerten von Ressourcen o.ä.

Darin ist jeweils nur diese eine Klasse definiert. Jetzt ist es so, dass manche Klassen im Framework Scope liegen und manche Klassen in Application Scope - und damit in anderen Verzeichnissen.
Bisher war es einfach, da es genau 4 Verzeichnisse gab, wo Klassen liegen konnten. Jetzt werde ich aber verschiedene Sachen einbauen, wo es notwendig ist, dass Klassen auch in Unterverzeichnissen dieser Verzeichnisse liegen (z.B. liegen die Klassen eines Plugins im Verzeichnis dieses Plugins und nicht im allgemeinen Plugin-Verzeichnis). Also brauche ich alle diese Pfade.

Verstehe ich immer noch nicht. Kannst Du der Klasse (d.h. Klassenname und ggf. Namespace) ansehen, in welchem Verzeichnis die Datei liegt? Und wenn nicht, was macht die __autoload()-Funktion dann?

Viele Grüße,
der Bademeister

[levu]

Darin ist jeweils nur diese eine Klasse definiert. Jetzt ist es so, dass manche Klassen im Framework Scope liegen und manche Klassen in Application Scope - und damit in anderen Verzeichnissen.
Bisher war es einfach, da es genau 4 Verzeichnisse gab, wo Klassen liegen konnten. Jetzt werde ich aber verschiedene Sachen einbauen, wo es notwendig ist, dass Klassen auch in Unterverzeichnissen dieser Verzeichnisse liegen (z.B. liegen die Klassen eines Plugins im Verzeichnis dieses Plugins und nicht im allgemeinen Plugin-Verzeichnis). Also brauche ich alle diese Pfade.

Verstehe ich immer noch nicht. Kannst Du der Klasse (d.h. Klassenname und ggf. Namespace) ansehen, in welchem Verzeichnis die Datei liegt? Und wenn nicht, was macht die __autoload()-Funktion dann?

Nein, kann man nicht. Da aber zwei Klassen nicht gleich heißen dürfen (die im Application Scope heißen z.B. MailinglistController oder MailinglistView oder eben, wenn man sontige Klassen macht, muss man halt gucken, dass die nicht heißen wie die im Framework).
Namespaces nutze ich nicht, da unser Framework hauptsächlich darauf ausgelegt ist, möglichst wenig schreiben zu müssen. Man kennt als Anwendsungsentewickler ja die Namen von allen Klassen im Framework Scope und kann seinen Klassen entweder ein Prefix geben oder die Namen anders entsprechen wählen.
Ich kann verstehen, wenn es jetzt noch alles etwas komisch/unbenutzbar/was weiß ich klingt, aber so gegen nächstes Frühjahr werde ich die erste Version hier vorstellen und Fragen bis dahin beantworten, selbst die ehemaligen schärfsten Kritiker des Designs sind inzwischen zufrieden damit.
Bitte versteht auch, dass ich es erst ausführlich vorstelle, wenn es in einem sehr weiten Stadium ist.

[dedlfix]

Hi!

Nein. So nicht. Das wäre ja ein katastrophaler Designfehler. Die Dateien heißen bei mir <Classname>.class.php . Darin ist jeweils nur diese eine Klasse definiert. Jetzt ist es so, dass manche Klassen im Framework Scope liegen und manche Klassen in Application Scope - und damit in anderen Verzeichnissen.

Was ist, wenn nun zwei Klassen gleich heißen, aber in unterschiedlichen Scopes unterschiedliche Aufgaben lösen sollen? Benennst du dann eine so um, dass der Name weniger beschreibend ist, oder so, dass er explizit noch den Scope benennt, zu der sie gehört? Und wenn letzteres, warum machst du das nicht mit allen Klassen so, so dass sich gleichzeitig aus ihrem Namen das Verzeichnis extrahieren lässt (siehe Benennungsschema vom Zend Framework). Sollten die unterschiedlichen Scopes an verschiedenen Plätzen liegen (falls das überhaupt notwendig ist und nicht alles von einem gemeinsamen Library-Verzeichnis ausgeht), so ist ihre Anzahl doch meist endlich und im include_path gut unterzubringen.

Lo!

[levu]

Ich möchte nur kurz auf die Kritikpunkte eingehen, die ich dem Bademeister noch nicht beantwortet habe :)

Nein. So nicht. Das wäre ja ein katastrophaler Designfehler. Die Dateien heißen bei mir <Classname>.class.php . Darin ist jeweils nur diese eine Klasse definiert. Jetzt ist es so, dass manche Klassen im Framework Scope liegen und manche Klassen in Application Scope - und damit in anderen Verzeichnissen.

Sollten die unterschiedlichen Scopes an verschiedenen Plätzen liegen (falls das überhaupt notwendig ist und nicht alles von einem gemeinsamen Library-Verzeichnis ausgeht), so ist ihre Anzahl doch meist endlich und im include_path gut unterzubringen.

Ja, das ist notwendig, aber mit include_path ist es nicht möglich, weil ich auch für manche Sachen den genauen Pfad zu der Datei brauche, wo die Klasse drin definiert ist, das wäre aber sehr umfangreich, das hier alles darzustellen. Wenn du es willst, erklär ich es gerne auch ausführlich…

[dedlfix]

Hi!

[...] weil ich auch für manche Sachen den genauen Pfad zu der Datei brauche, wo die Klasse drin definiert ist, [...]

Ich kann mir nur vorstellen, dass dann auch noch Datendateien im Code-Verzeichnissen liegen. Das hielte ich nicht für besonders gut organisiert. Aber gut, am besten lernt man aus den selbst gemachten Fehlern :-)

Lo!

[levu]

[...] weil ich auch für manche Sachen den genauen Pfad zu der Datei brauche, wo die Klasse drin definiert ist, [...]

Ich kann mir nur vorstellen, dass dann auch noch Datendateien im Code-Verzeichnissen liegen. Das hielte ich nicht für besonders gut organisiert. Aber gut, am besten lernt man aus den selbst gemachten Fehlern :-)

Das lernen gilt dann wohl für die, in einem Ordner "classes" was anderes als Klassen ablegen. Für Daten etc. habe ich extra Verzeichnisse (/app/conf/ für Konfigurationen, /app/etc/sqlite für sqlite datenbanken, /app/etc/csv für CSV datendateien, oder allgemein /app/etc für was anderes)