PHP: Rekursives Einlesen von Ordnern und Dateien liefert doppelte Werte

[Julius]

Hallo Rolf,

ich glaube nicht, dass array_diff prinzipiell O(n²) hat, weil ja nicht ein Array mit sich selbst gematcht wird, sondern zwei Arrays miteinander, wovon eins fix ist. Die Laufzeitkomplexität ist also O(2n), und das ist O(n).

Aaah. Danke fürs Aufklären meines Irrtums! Als ich – leider erfolglos – versucht habe, den Quellcode der Originalimplementierung von array_diff in PHP ausfindig zu machen (bin wohl zu doof 😟), bin ich auf diesen Beispielcode gestoßen, wo mir das auch klar wurde.

Die relevante Frage ist nach dem Anteil an Verzeichnissen in den gefundenen Filesystemobjekten - der könnte sinken wenn man größere Bäume traversiert, und an der Effizienz von array_diff an sich.

Du meinst, dass sich array_diff bei einer gewissen Menge an Dateien pro Ordner ggü. der Lösung mit den if’s in foreach im Vorteil ist?

---

Ich habe – weil es mich interessiert – einen kleinen Testaufbau (s.u.) gebastelt und ein wenig gebenchmarkt. Wenn ich die (Beispiel-)Werte ['.', '..', '.htaccess'] ausschließe, ist bei 1.000.000 (Zahlen bei 100.000 und 10.000 Einträgen ähnlich) Einträgen im Array array_diff tatsächlich im Vorteil. Beispiel-Werte (weniger ist besser, foreach mit if’s ist 100):

|foreach|100| |array_diff|61| |foreach in_array|108|

Geht man vom Anwendungsfall des TO aus (nur ['.', '..'] ausschließen, eher kleine Array-Größen), nehmen sich die Funktionen nicht mehr viel. Beispiel-Werte:

|foreach|100| |array_diff|90| |array_slice|40| |foreach in_array|140|

Nach diesem schnellen Test scheinen array_diff bzw. array_slice (falls es nur um die ersten beiden Werte im Array – .. und . – geht) eine gute Alternative für das if im foreach zu sein. Ich habe bei den (mehrfach ausgefühten) Tests ab und an einen Ausreißer gehabt, ich habe dann grob passende Ausgaben genommen (hier könnte man natürlich mehrere Messreihen ausführen und dann Mittelwert oder Median benutzen). Außerdem bin ich mir nicht sicher, ob PHP da nicht doch etwas wegoptimiert.

Der Code (quick and dirty):

<?php
// Hilfsfunktionen:
function generateRandomString($length = 10) {
    $characters = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_,;.:#\'\\+~*()/&$"!?';
    $charactersLength = strlen($characters);
    $randomString = '';
    for ($i = 0; $i < $length; $i++) {
        $randomString .= $characters[rand(0, $charactersLength - 1)];
    }
    return $randomString;
}

function fillArrayRandomStr($size=20) {
  $result = [];
  for($i=0; $i<$size; $i++) {
    $result[] = generateRandomString(rand(1, 25));
  }
  return $result;
}

// Ausgabe von scandir() simulieren:
$a = fillArrayRandomStr(1000);
$a = array_merge(['.', '..'], $a);

$ts = microtime(true);
foreach($a as $val) {
  if($val != '.' && $val != '..') {
    //continue;
  }
}
$_foreach = microtime(true) - $ts;
echo "foreach\t\t=".round($_foreach/$_foreach*100)."\n";

$ts = microtime(true);
$b = array_diff($a, ['.', '..']);
foreach($b as $val) {
}
echo "array_diff\t=".round((microtime(true) - $ts)/$_foreach*100)."\n";

$ts = microtime(true);
$b = array_slice($a, 2);
foreach($b as $val) {
}
echo "array_slice\t=".round((microtime(true) - $ts)/$_foreach*100)."\n";

$ts = microtime(true);
foreach($a as $val) {
  if(!in_array($val, ['.', '..'])) {
    //continue;
  }
}
echo "foreach in_array=".round((microtime(true) - $ts)/$_foreach*100)."\n";
?>

Verwendete PHP-Version:

PHP 7.0.18-0ubuntu0.16.04.1 (cli) ( NTS )
Copyright (c) 1997-2017 The PHP Group
Zend Engine v3.0.0, Copyright (c) 1998-2017 Zend Technologies
    with Zend OPcache v7.0.18-0ubuntu0.16.04.1, Copyright (c) 1999-2017, by Zend Technologies

Mein Nickname ist prima in Ordnung. Der sollte nur die Behauptung von CK und GB testen, dass Unicodezeichen außerhalb von Basic Latin und Latin-1 Supplement eine eigene CSS Klasse bekommen. Dumm nur, dass das kleine ß in Latin-1 liegt, werde das mal ändern.

Das header-Element bekommt die Klasse suspicious also zugewiesen. Ich musste dreimal die Entwicklertools öffnen, bevor ich das gesehen habe 😂.

Edit: Yup - class .suspicious greift.

Rein Interessenshalber: Warum behältst du dann das ẞ bei? Um die anderen Nutzer zu verwirren (wäre ein valider Grund 😉)? Zumindest bei Sophie hat das ja scheinbar geklappt...

Gruß
Julius