[php] Array-Frage - Danke

[Ulf Wendel]

Mark Kronsbein wrote:
> Danke! Das war übrigens die Lösung, auf die ich eigentlich selber hätte
> kommen sollen.
> 
> for($i=0;$i<count($spambots);$i++){
>  if(getenv("HTTP_USER_AGENT") == $spambots[$i]){
>  header ("Location: http://www.microsoft.com");
> exit;
> }
> }

Mark, 

Du nimmst einen Lösungsansatz mit dem Aufwand n/2 und verschmähst die
Lösung mit dem konstanten Aufwand von 1. Das nicht das, was ein
Einsteiger lernen sollte. 

Spiel dein Skript mal von Hand durch. Du hast eine Werteliste von n
Elementen und möchtest wissen, ob ein konstanter Wert in der Werteliste
enthalten ist. Du organisiert Dein Array wie folgt:

0 => "BotA",
1 => "BotB",
[...]
25 => "BotZ"

Um zu erfahren ob "BotJ" im Array enthalten ist, durchläufst Du das
komplette Array:

[Ansatz 1]
reset($spambots);
for ($i=0; $i<count($spambots); $i++) {
 if (getenv("HTTP_USER_AGENT") == $spambot[$i]) {
    [...]
 }
}

Je nach Wert den Du suchst, sind 1...n Durchläufe notwendig. Im
Idealfall suchst Du nach "BotA" und hast nach einem Durchlauf Erfolg.
Schlimmstenfalls benötigst Du zum Auffinden von "BotZ" oder dem Test auf
einen unbekannten Wert n Durchläufe. Im Mittel sind n/2 Durchläufe
notwendig.

Leider ist Deine Schleife ineffektiv. PHP muß bei jedem Durchlauf die
Länge des Arrays $spambots durch einen Funktionsaufruf ermitteln. Dabei
ist garantiert, daß der Wert invariant ist. Folgendes wäre besser:

[Ansatz 2]
$len = count($spambots);
for ($i=0; $i<$len; $i++) {
  [...]
}

Richtig schön ist das aber auch noch nicht. Die Schleife hat einen
variablen Endwert, selbst ein Kompiler kann hier nichts rausschlagen.
Und auch ein "while (list($k, $v)=each($spambots))" wird nicht viel
besser abschneiden. Ist auch Schnuppe, was nervt ist der Aufwand n/2.

Organisierst Du $spambots nur ein klein wenig anders, sinkt der Aufwand
auf einen konstanten Wert von 1:

$spambots = array (
  "BotA" => true,
  "BotB" => true,
  [...]
  "BotZ" => true
);

[Ansatz 3]
if (isset($spambots[getenv("HTTP_USER_AGENT")])) {
 [...]
}

Eigentlich sollte sogar folgendes funktionieren:

[Lösung]
if (isset($spambots[$HTTP_USER_AGENT]))

Laß uns mal den Aufwand für die einzelnen Lösungen aufsummieren, ich
rechne mal etwas feiner, um die Optimierungsstufen herauszustellen.
Eigentlich summiert man nicht die Anzahl der Funktionsaufrufe auf,
sondern nur die Schleifendruchläufe. 

+++ Deine Arrays +++

[Ansatz1]         [Ansatz2]

1 x reset()       1 x reset()
1 x for() {}      1 x for() {}
n/2 x count()     1 x count()
n/2 x if () {}    n/2 x if() {}
n/2 x getenv()    n/2 x getenv() 
( = 3/2n + 2)     ( = n + 3)

+++ schlaue Arrays +++

[Ansatz3]        [Lösung]
1x if() {}       1x if() {}
1x isset()       1x isset()
1x getenv()
( = 3 )          ( = 2 ) 

Alle variablen Kosten wurden eingespart. Aus einem linearen Aufwand,
wird ein konstanter Aufwand, der nicht kleiner sein kann. Mit ordentlich
organisiertem Array benötigst Du genau einen Test. In deiner Lösung sind
es n/2, bei n>2 ist das ineffektiv, der arme Rechner.

Verliert man irgendetwas, wenn das Array anders organisiert wird? Nein.
Durchlaufen und die Position eines Elements ermitteln kann man immer
noch. Der Aufwand ist dabei identisch zur for()-Schleifen bei n/2. Gegen
irgendwelche Werte verloren? Nein. Kostet es mehr Speicher? Nein.

Wie ich schon in einem anderem Posting sagte kann man, wenn man unsicher
beim Umgang mit derart indizierten Arrays ist, die Werte durchaus
doppeln und es sieht fast so aus wie eine automatische, numerische
Indizierung. Es ist nun wirklich schnuppe welche der untenstehenden
Schleifen ich benutze, um die Elemente nummeriert anzuzeigen:

reset($spambots);
$len = count($spambots);
for ($i=0; $i<$len; $i++)
  printf("%d %s<br>\n", $i, $spambots[$i]);

reset($spambots);
$i = 0;
while (list($k, $v)=each($spambots)
  printf("%d %s<br>\n", $i++, $v);


Ulf