Optimierung gesucht

[Campus]

ich mein $x[?][0], ja, das weiss ich, aber wie steigend ? linear, exponenziel oder stark unterscheidlich ?

[Campus]

$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;
        }
    }
 if ($treffer) {
   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;
    }
} else echo "nix gefunden";
}
$end = explode(" ", microtime());
$end = $end[1] + $end[0] - $time;
echo "\nZeit: $end\n\n"; 

probiert mal ob jetzt auch mit keinem das funkt...

[TBT]

keine Regeln dafür, kann alles sein.
Ist abhängig vom Benutzer

[Campus]

ups, das fehlte weiter unten ein else... hab korrigiert

[TBT]

@Campus:

stimmt, ist noch nen Tick schneller, doch hat noch einen Fehler.

bei slarti und bei mir gibt es:

Test7 Test1 Test8

bei dir nur

Test7 Test1

weil die Mitte bei dir immer abgerundet wird, er also Test8 ($mitte müßte dann 7 sein) nie erreicht.

er kommt auf obere Grenze = 7 untere Grenze = 6 und die Mittenberechnung daraus ist 6
obwohl bei mitte=7 eine Lösung wäre

[Campus]

while($og > $ug and !$treffer){ 

zu

while($og >= $ug and !$treffer){ 

sorry, ich mach immer solche dummheitsfehler..
müsste nun aber klappen.. hoffe ich

[TBT]

funktioniert, aber jetzt läufste hier über die Arraygrenzen

if ($x[$mitte][0] < $value)
    $ug = $mitte + 1;
else
    $og = $mitte - 1; 

[Campus]

wie meinst du das ??
kann ja ruhig, solange kein array damit angesprochen wird ?! sicher ja die while bedingung, oder nicht ?

[TBT]

muß heissen

while($og >= $ug and !$treffer){
    $mitte = (int)(($ug + $og) / 2);
    if ($mitte < $count && $x[$mitte][0] == $value)
        $treffer = true;
    else
        if ($mitte < $count && $x[$mitte][0] < $value)
            $ug = $mitte + 1;
        else 
            $og = $mitte - 1;
} 

ansonsten gibs ein "undefined index 10 ..."

[Campus]

achso... sorry..
mach doch lieber wie ich das weiter oben gemacht hab. nur statt

$og = $count;

zu

$og=$count-1;

und nochmal ausprobieren, ich kann grad nix ausprobieren, sorry

[CHnuschti]

was ist damit?

<?php

$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";

$sucharray=array(1,4,9);

foreach($x as $a) $s[]=$a[0]; // $a[0] = Dimension wo zu suchen,
foreach ($sucharray as $b) $resultatarray[]=array_search ($b, $s);
// oder direkt das Resultat
//$resultatarray[]=$x[array_search ($b, $s)][1];

while(list($k, $v) = each($resultatarray)):
printf("k=%s v=%s<br>\n", $k, $v);
endwhile;


?>

bin doch stolz auf mich: 2 Zeilen!

[Campus]

kanns du uns mal die benchmark ergebnisse presentieren ?

[CHnuschti]

Damit bekommst du alle Schlüssel, auch jene der Mehrfachwerte.
Allerdings musst du den Resultatarray noch weiter bearbeiten, wenn er denn "kompakter" sein soll, habs nicht gerade zur Hand, wies gehen soll.

<?php

$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[3][1]="Test4";
$x[4][0]=4;
$x[4][1]="Test5";
$x[5][0]=4;
$x[5][1]="Test6";

$sucharray=array(1,4,9);

foreach($x as $a) $s[]=$a[0]; // $v[0] = Dimension wo zu suchen, hier 1te Dimension
foreach($sucharray as $b) $result[]=array_keys($s,$b);

while(list($k, $v) = each($result)):
echo "v0=$v[0]; v1=$v[1]; v2=$v[2]<br>";
endwhile;


?>

[TBT]

@ Chnuschti:

gute Idee, doch leider änderst du die Voraussetzungen. Die gegebenen
Arrays sind so, und nicht anders
Aber deine Lösung hat mich auf eine Idee gebracht:

Variante TBT 2

foreach($x as $key=>$value)
    $suche_in[$key]=$value[0];

$anzahl = count($such);
for($i=0;$i<$anzahl;++$i){
    $erg=array_search($such[$i][0],$suche_in);
    if(is_numeric($erg)){
        echo $x[$erg][1];
        while(isset($x[++$erg][0])&&$x[$erg][0]==$such[$i][0])
            echo $x[$erg][1];
    }
} 

und als Zeitmessung ergab sich dies:
( 100 % = Zeit für allererste Variante)

1. Variante TBT 100%
2. Variante slarti 105 %
3. Variante Campus 87%
4. Variante TBT 2 47%

[CHnuschti]

Deine letzte Lösung findet aber m.E. die doppelten Einträge nicht.
Jedenfalls scheint foreach() das Rennen zu machen. Siehe Anhang
mfg