---

Hej gruppe.


Jeg har et forholdsvis meget stort array, som der skal gennemgås flere
tusind gange.

En mindre version kunne se således ud:

0 => 1040
3 => 1203
9 => 933
10 => 512
24 => 2033


Keys og values er begge ukendte.


På et tidspunkt i min kode, får jeg at vide tallet 3 (svarende til den
key i arrayet). Jeg vil nu gerne checke om den efterfølgende (9)
eksisterer - Jeg ved dog ikke, at tallet er 9.

Jeg tænkte på at gøre noget lignende ($array er mit array):

<?
set_pointer_to_key($array, 3);

if (next($array)){
// Der eksiterer en efter 3, hvis bare at,
// "set_pointer_to_value" var en funktion :'(
}else{
// Der eksisterer IKKE en efter 3.
}
?>


Kan overstående laves uden at lave en total gennemløbning med
eksempelvis "foreach"? Altså at springe rundt i mit array.


--
Med venlig hilsen
Kasper Johansen

---

Det skal måske siges, at jeg allerede har en løsning, hvor jeg
gennemløber hele arrayet og afbryder med med en "return", når jeg finder
et resultat.

Jeg kunne bare forstille mig, at det andet var mærkbart hurtigere.


--
Med venlig hilsen
Kasper Johansen

---

Kasper Johansen wrote:
> Det skal måske siges, at jeg allerede har en løsning, hvor jeg
> gennemløber hele arrayet og afbryder med med en "return", når jeg finder
> et resultat.
>
> Jeg kunne bare forstille mig, at det andet var mærkbart hurtigere.

Du kan gøre det at du fortsætter fra den sidste position du er kommet
til i arrayet, ved at bruge "key" til at checke hvor du er, og bruge
"next" og "prev" afhængig af om du er for lavt eller højt.

Meen, så simpelt behøver det ikke være.

I bedste fald, hvor de keys du søger efter ligger tæt op ad hinanden,
vil det blive væsentligt hurtigere.
I værste fald, i det tænkte tilfælde hvor du har skiftevis en høj og
en lav værdi du søger efter, bliver den gennemsnitlige søgelængde
væsentligt længere.

Hvis du kender fordelingen på nøglerne, kan du evt forbedre
ovenstående metode, ved at hoppe til starten("reset") eller
enden("end"), hvis du kan vurdere om det du søger efter ligger i
toppen eller bunden.

Det kan du evt. tage et skridt videre, ved at opdele arrayet du søger
i, i flere mindre arrays. Det kræver at du udfra en key kan afgøre
(eller ramme tæt på) hvilket array du skal have fat i, som vil svare
lidt til at hoppe rundt i arrayet, som du nævnte. Det kræver
selvfølgelig lidt mere logik, og længere "forberedelse".

Et skridt videre, kan du med sqlite oprette en database i memory. Som
sandsynligvis ville kunne gøre søgningen hurtigere, i alle generelle
tilfælde, men igen længere forberedelse førend du kan begynde at søge,
som gør at det måske ikke kan svare sig.
http://dk2.php.net/manual/en/function.sqlite-open.php


/Bent

---

Kasper Johansen wrote:
> Det skal måske siges, at jeg allerede har en løsning, hvor jeg
> gennemløber hele arrayet og afbryder med med en "return", når jeg finder
> et resultat.
>
> Jeg kunne bare forstille mig, at det andet var mærkbart hurtigere.

Hvis du skal finde den efterfølgende nøgle til de samme nøgler mange
gange, er det oplagt at lave en funktion som cacher resultatet.

Pseudokode:

i,j heltal
cache, tabel array

function next(i)
   if(defined(cache(i))) {
      return cache(i)
   }
   j = i + 1
   while(not defined(tabel(j)) {
      j = j + 1
   }
   cache(i) = j
   return j
}

Med andre ord: lav en funktion som finder det efterfølgende element ved
hjælp af lineær søgning, men ved samme lejlighed cacher resultatet. Det
vil reducere køretiden dramatisk.

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

Kasper Johansen skrev:

> En mindre version kunne se således ud:

> 0 => 1040
> 3 => 1203
> 9 => 933
> 10 => 512
> 24 => 2033

> Keys og values er begge ukendte.

> På et tidspunkt i min kode, får jeg at vide tallet 3 (svarende til den
> key i arrayet). Jeg vil nu gerne checke om den efterfølgende (9)
> eksisterer - Jeg ved dog ikke, at tallet er 9.

Er det kun key du skal kunne finde? I så fald kan du vende dit
array om for array_search(3,$array) vil så returnere 1203.

Her er en løsning der virker hvis du kun skal søge på value:
<?
$testarray = array ( 0 => 1040, 3 => 1203, 9 => 933, 10 => 512, 24 => 2033);
$pointer=array_search(2033,$testarray);
echo "<p>Pointer: ".$pointer." Value: ".$testarray[$pointer]."</p>";
echo "<p>End: ".end($testarray)."</p>";
if ($testarray[$pointer]==end($testarray)) echo "<p>Det var det sidste element.</p>";
else echo "<p>Det var <strong>ikke</strong>det sidste element.</p>";
?>

Hvis det er ligemeget hvor elementet findes kan du gentage
operationen på array_flip($testarray).

Her er et hav af array-funktioner:

   http://dk.php.net/manual/en/ref.array.php

I det hele taget er manualen et studium værd.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen skrev:
> Her er en løsning der virker hvis du kun skal søge på value:
> <?
> $testarray = array ( 0 => 1040, 3 => 1203, 9 => 933, 10 => 512, 24 => 2033);
> $pointer=array_search(2033,$testarray);
> echo \"<p>Pointer: \".$pointer.\" Value: \".$testarray[$pointer].\"</p>\";
> echo \"<p>End: \".end($testarray).\"</p>\";
> if ($testarray[$pointer]==end($testarray)) echo \"<p>Det var det sidste element.</p>\";
> else echo \"<p>Det var <strong>ikke</strong>det sidste element.</p>\";
> ?>

Følgende løste mit problem og gav mig en kraftig optimering (forskel på 1,4 sekunder i flere tilfælde ud af total 1,9 sek).

Jeg skrev mit array lidt om, så jeg kunne søge efter value i stedet.


> Her er et hav af array-funktioner:
>
>    http://dk.php.net/manual/en/ref.array.php
>
> I det hele taget er manualen et studium værd.

Jeg havde skam allerede kigget på det i flere timer, da jeg skrev ;)


Jeg takker mange gange for alle svar, som der er kommet til mit spørgsmål :)


Hvis det har interesse, så skulle det bruges til det grafiske design til min selvskrevne Usenet-gateway, som i kan se her:

http://partyworm.dk/index.php?show=usenet_msgs&groupid=1



--
Med venlig hilsen
Kasper Johansen