Optimierung gesucht

[TBT]

Hallo, ich habe ein zweidimensionales Array, welches
durchlaufen wird. Nun suche ich eine Möglichkeit das ganze
schneller zu machen. Am liebsten wäre mir eine Möglichkeit
ohne Schleife.

Beispiel

$x[0][0]=1;
$x[0][1]="Test1";
$x[1][0]=4;
$x[1][1]="Test2";
$x[2][0]=7;
$x[2][1]="Test3";
$x[3][0]=9;
$x[4][1]="Test4";

$such=7;

for($i=0;$i<$count($x);++$i){
    if($such==$x[$i][0]) {
        echo $x[$i][1];
        break;
    }
} 

dieses Array wird recht schnell mal 100 Felder groß, und wird
dann auch 100 mal durchlaufen => also maximal
10 000 Durchläufe

Jemand eine Idee, wie man das besser machen kann ?

[MoRtAlAn]

sind die [?][0]-Werte eindeutig ?? ich geh mal von ja aus.

schau mal hier: array_search()

geht auch mit multidimensionalen arrays (macht nichts anderes, als deine Funktion, nur schneller )

gruss

[TBT]

die [?][0] sind nicht eindeutig, und bei Mehrfachvorkommen sollen auch alle ausgegeben werden.
Aber die werte in [?][0] snd aufsteigend sortiert.

Mit dem array_search bei mehrdimensionalen Arrays komm ich nicht klar,
haste mal nen Stück Code ?

[MoRtAlAn]

mh... grade nicht auffindbar und vor WE komm ich nicht dazu... reicht das evtl. ???

schreib mich aber bitte nochmal per Mail an (nickname@php-resource.de), mit nem link in den Thread oder am besten nochmal mit nem kurzen beispielcode, wie das array aussieht und wie du es momentan löst, dann kann ich beide Codes mal gegeneinander antreten lassen ...

ach ja, hast du mehrere Treffer, bekommst du die auch zurück, in Array-Form...

gruss

[TBT]

so, habs jetzt nochmal ausführlicher, und den derzeit aktuellen
Algorithmus, welcher bereits einige Schleifendurchläufe spart.

$such[0][0] = 5;
$such[1][0] = 11;
$such[2][0] = 1;
// ... Array wird größer, derzeit ca 15 lang
// die Werte in $such sind unsortiert (bzw. nach einem anderen Kriterium)

$x[0][0] = 1;
$x[0][1] = "Test1";
$x[1][0] = 4;
$x[1][1] = "Test2";
$x[2][0] = 7;
$x[2][1] = "Test3";
$x[3][0] = 7;
$x[3][1] = "Test4";
$x[4][0] = 9;
$x[4][1] = "Test5";
// ... Array wird größer, derzeit ca 24 lang
// die Werte in $x sind nach $x[?][0] aufsteigend sortiert

// derzeitiger Algorithmus
$anzahl = count($such);
for($i = 0;$i < $anzahl;++$i){
    reset($x);
    while(list($key, $val) = each($x)){
        // frühzeitig die Schleife verlassen wenn Wert schon größer
        if($val[0] > $such[$i][0])
            break;
        // Wert gefunden, 2.Array ausgeben und verkleinern
        if ($val[0] == $such[$i][0]){
            echo $val[1];
            unset($x[$key]);
        }
    }
    // Ausgabe von Werten aus $such[$i][1...]    
} 

[slarti]

also, wenns schneller sein soll, am besten recursiv mit intervallhalbierung:

funktion suche($suchewert,$x,$lg,$rg)
 {
  if($lg>$rg)return false;     //nix gefunden
  $middle=$lg+intval((($rg-$lg)/2));   //mitte suchen
  if($x[$middle][0]==$suchwert)return $middle;  //index des treffers
  if($x[$middle][0]>$suchwert) return suche($suchwert,$x,$lg,$middle-1);
  else return suche($suchwert,$x,$middle+1,$rg);
 }
$erg=suche($suchwert,$x,0,(count($x)-1)); 

(not tested)

...das sollte dir den index des ersten treffers zurückgeben bzw. false.
mußt halt nur noch nachschauen, ob links oder rechts daneben auch noch welche sind.

[Campus]

also ich hab deine array zuweisungen nicht ganz verstanden. aber hab mir sowas änliches wie slarti überlegt:

<?php
$x[0][0] = 2;
$x[0][1] = 2;
$x[0][2] = 2;
$x[0][3] = 2;
$x[0][4] = 2;
$x[0][5] = 2;
$x[0][6] = 2;
      $count=count($x[0]);
      $ug=0;
      $og=$count;
      $value=2;
      $treffer=false;
      while($og > $ug and !$treffer) 
    { $mitte = (int)(( $ug + $og ) / 2); 
      if ($x[0][$mitte]==$value) 
          $treffer=true; else 
          if ($x[0][$mitte]<$value) $ug=$mitte + 1; 
          else $og=$mitte - 1;
        }
        echo $mitte."<br>";
        $treffer=false;
        $i=0;
        $oben=true;
        $unten=true;
        while($oben or $unten) {
        $i++;
        if ($mitte-$i>=0 and $unten) if($x[0][$mitte-$i]==$value) echo ($mitte-$i)."<br>";
        else $unten=false;
        else $unten=false;
        if($mitte+$i<$count and $oben) if($x[0][$mitte+$i]==$value) echo ($mitte+$i)."<br>";
        else $oben=false;
        else $oben=false;
        }
?>

check das mal auch, habs nur mit ein paar bespielen probiert..
ps:sorry für meine programmier art
pps: wenn die array ziemlich lang wird, und die so ziemlich linear gefüllt ist, könnte man sich überlegen, das die halbierung nicht in der mitte sein sollte, sondern etwas zu value wert geneigt..

[TBT]

gute Idee, gleich getestet.
muß auf jeden Fall

function suche($suchwert,$x,$lg,$rg)

heißen, ist aber ein mü langsammer als die Schleifenvariante.
Dabei sind die Mehrfachvorkommen aber noch nicht geprüft.

Umso größer die Arrays werden, umso mehr Geschwindigkeitsvorteil
bringt die Schleifenvariante.

Schade

[Campus]

Original geschrieben von TBT

Umso größer die Arrays werden, umso mehr Geschwindigkeitsvorteil
bringt die Schleifenvariante.

Schade

bist du dir da sicher ?
oder versuch mal meine ganze porcedure mit sagen wirmal 10000 arrayelementen und der vorletzte ist der gesuchte..

[TBT]

ich habe hier das Array immer weiter vergrößert, und die Schleifenvariante war immer etwas schneller.
Du bergißt, das die Schleife das Array immer kleiner macht
mit unset

PS: ich meinte die Lösung von slarti

[slarti]

...könnte daran liegen, das meine funktion immer das komplette array mit übergibt, das kostet zeit.
also entweder dat array als referenz übergeben oder global machen...

...is ja wie bei corewars hier

[Campus]

achso, hab nur dein ersten code angeguckt, .. poste mal die 2 varianten, bitte .

ps:solche themen liebe ich

[TBT]

Testfeld:

$such[0][0] = 5;
$such[1][0] = 11;
$such[2][0] = 1;
$such[3][0] = 6;
$such[4][0] = 113;
$such[5][0] = 12;
// ... Array wird größer, derzeit ca 15 lang
// die Werte in $such sind unsortiert (bzw. nach einem anderen Kriterium)
$x[0][0] = 1;
$x[0][1] = "Test1";
$x[1][0] = 4;
$x[1][1] = "Test2";
$x[2][0] = 7;
$x[2][1] = "Test3";
$x[3][0] = 7;
$x[3][1] = "Test4";
$x[4][0] = 9;
$x[4][1] = "Test5";
$x[5][0] = 9;
$x[5][1] = "Test6";
$x[6][0] = 11;
$x[6][1] = "Test7";
$x[7][0] = 12;
$x[7][1] = "Test8";
$x[8][0] = 13;
$x[8][1] = "Test9";
$x[9][0] = 14;
$x[9][1] = "Test10"; 

TBT

$time = explode(" ", microtime());
$time = $time[1] + $time[0];

$anzahl = count($such);
for($i = 0;$i < $anzahl;++$i){
    reset($x);
    while(list($key, $val) = each($x)){ 
        // frühzeitig die Schleife verlassen wenn Wert schon größer
        if($val[0] > $such[$i][0])
            break; 
        // Wert gefunden, 2.Array ausgeben und verkleinern
        if ($val[0] == $such[$i][0]){ 
            echo $val[1];
            unset($x[$key]);
        }
    } 
    // Ausgabe von Werten aus $such[$i][1...]
}

$end = explode(" ", microtime());
$end = $end[1] + $end[0] - $time; // 0.003
echo "\nZeit: $end\n\n"; 

slarti

function suche($suchwert, $x, $lg, $rg){
    if($lg > $rg)
        return false; //nix gefunden
    $middle = $lg + intval((($rg - $lg) / 2)); //mitte suchen
    if($x[$middle][0] == $suchwert)
        return $x[$middle][1]; //wert des treffers
    if($x[$middle][0] > $suchwert)
        return suche($suchwert, $x, $lg, $middle-1);
    else
        return suche($suchwert, $x, $middle + 1, $rg);
}

$time = explode(" ", microtime());
$time = $time[1] + $time[0];
for($i = 0;$i < $anzahl;++$i){
    echo suche($such[$i][0], $x, 0, (count($x)-1));
}
$end = explode(" ", microtime());
$end = $end[1] + $end[0] - $time;
echo "\nZeit: $end\n\n"; 

Campus (PS: ist noch nen kleiner Fehler drin, wenn der Suchwert nicht gefunden wird)

$time = explode(" ", microtime());
$time = $time[1] + $time[0];

$count = count($x);
for($z = 0;$z < $anzahl;++$z){
    $ug = 0;
    $og = $count;
    $value = $such[$z][0];
    $treffer = false;
    while($og > $ug and !$treffer){
        $mitte = (int)(($ug + $og) / 2);
        if ($x[$mitte][0] == $value)
            $treffer = true;
        else{
            if ($x[$mitte][0] < $value)
                $ug = $mitte + 1;
            else
                $og = $mitte - 1;
        }
    }
    echo $x[$mitte][1];
    $treffer = false;
    $i = 0;
    $oben = true;
    $unten = true;
    while($oben or $unten){
        $i++;
        if ($mitte - $i >= 0 and $unten){
            if($x[$mitte - $i][0] == $value)
                echo $x[$mitte-$i][1];
            else $unten = false;
        }else $unten = false;
        if($mitte + $i < $count and $oben){
            if($x[$mitte + $i][0] == $value)
                echo $x[$mitte+$i][1];
            else $oben = false;
        }else $oben = false;
    }
}
$end = explode(" ", microtime());
$end = $end[1] + $end[0] - $time;
echo "\nZeit: $end\n\n"; 

sieht ganz so aus, wenn sich mit ein bischen Optimierung die Variante "Campus" als schnellste entpuppen könnte )

[Campus]

achja, ist das denn so, das der array halbwegs linear sortiert ist ?
also so ungefähr

1,2,4,7,8,9,13,14 ?

oder meistens eher :
1,1,1,1,1,1,1,1,10,100 ?

[TBT]

das Array $x[?][0] ist aufsteigend sortiert.

das Array $such[?][0] ist unsortiert