Arrayværdi = arrayværdi

Hov glemte at sige: Hold det simpelt :) Den nemmest forståelige løsning vinder point. Jeg har leget med

foreach ($x as $value) {
echo $value;
}

- byg gerne på den :).

Med en milliard værdiere i dine arrays, knækker serveren sig nok pga. memory problemer eller timeout. ;^)

for ($id=0; $id<count($x); $id++) {
    if ($x[$id] == $y[$id]) {
        echo $id . " " . $x[$id] . "<br>";
    }
}

Hvis det ikk blev helt afklaret, så får i lige lidt ekstra info:

x[1] hører sammen med y[1]
x[2] hører sammen med y[2]
osv...

I skal finde de koordinater som er ens ... Hvis x[1] = x[2] og y[1] = y[2] .. Så det bingo!

Jeg prøver lige din kode, nielle :)

Vist ikk helt korrekt, Nielle :). Din checker hvis x = y. Det er x = x og y = y. Lidt forvirrende vist, du må sige hvis du skal have det forklaret bedre.

Kan se at jeg har forklaret hoved-spørgsmålet som en klaphat. Det er pga. for lidt søvn, for meget cola og programmering. Håber du forstår det nu, Nielle.

Alle mennesker i verdens' x og y-koordinater står i arrayet. Vi skal finde X/Y/id på de mennesker som står på hovedet af hinanden (dem som har samme X/Y)

I ved godt at jesus ikk bliver født, før i har svaret? Godt...!

Og så lidt flueknepperi. Hvis der er en milliard entries, så kan der optimeres en del ved blot at udskifte

for ($id=0; $id<count($x); $id++) { ...

med

$cnt = count($x);
for ($id=0; $id<$cnt; $id++) { ...


(jf. PHP 5 Power Programming, 013147149X, p. 45)

Mere søvn og mindre cola, tak! Jeg vil så gerne have gaver i år. ;^)

Jeg tror desværre at du lige må gøre dig lidt mere besvære med at forklare hvordan dine arrays sre ud. Lige nu forestiller jeg mig ialt to gigantiske arrays i stil med:

$x = array(123, 234, 543, 239, ...);
$y = array(123,  1,  2, 239, ...);

men at dømme efter det dus skriver, så ser de ikke sådan ud?

Jo de ser præcist sådan ud.

dvs. person nr. "0" har (hvis vi tager udgangspunkt i dine array's, Nielle):

x=123
y=123

Person nr. 1 har:

x=234
y=1

Vi skal finde de personer som har samme X og Y.

Jeg forstår det sådan, at de enkelte (x, y)-koordinater skal sammenlignes med de resterende mhp. at finde dupletter.

Præcis, Jensgram.

Jeg undskylder for forvirringen.

Jeg hopper i seng, knægte - jeg checker her igen omkring kl 20. :) Gaab. God dag til jer alle. Sikker på i kan finde en løsning :).

$dup = array();


$cnt = count($x);
for ($id = 0; $id < $cnt; $id++) {
    $c = $x[$id] . ';' . $y[$id]; // x;y

    if (in_array($c, $dup) {
        print 'Duplet: ' . $c;
    } else {
        $dup[] = $c;
    }
}


Blot et bud. Sikkert ikke ret økonomisk.

$antalPersoner = count($x)
for ($id=0; $id<$antalPersoner; $id++) {

    $dubletter = false;
    for ($id2=$id+1; $id2<$antalPersoner; $id2++) {
        if ($x[$id2] == $x[$id] && $y[$id2] == $y[$id]) {
            if (! dubltter) {
                echo "Følgende personer på samme sted som: "
                echo $id . " : (" . $x[$id] . ", " . $y[$id] . ")<br>";
                echo "Dubletter:<br>"
                $dubletter = true;
            }

            echo $id2 . "<br>";
        }
    }

}

ehh kan "array_intersect_assoc" ikke bruges?
http://dk.php.net/manual/da/function.array-intersect-assoc.php

Følgende tager ca. 8-9 sekunder (på min maskine), hvis du har en million værdier i både $x og $y, og dine x- og y-koordinater ligger mellem 0 og 100.000. Det tager dog 500+ mb hukommelse og jeg tør slet ikke at teste med en milliard :-)

<?php

#--Testværdier--#
for ($i = 0; $i < 1000000; $i++) {
$x1[] = mt_rand(0,100000);
$y1[] = mt_rand(0,100000);
}
#--/Testværdier--#

$xy = array();

$len = count($x1);

for ($i = 0; $i < $len; $i++) {
$x2 = $x1[$i];
$y2 = $y1[$i];
$key = 'x'.$x2.'y'.$y2;

$xy[$key][] = $i;

}
$hit = false;
foreach ($xy as $key => $dupes) {

if (count($dupes) > 1) {
$hit = true;
echo '<br />Dubletter fundet på '.$key.':<br />';
foreach ($dupes as $id) {
echo 'ID:'.$id.'<br />';
}
}

}

if (!$hit) {
echo 'Ingen dubletter fundet';
}

?>

Nielle jeg giver dig point :).

Hvis du vil ha' den, så er den rettede kode her:

$antalPersoner = count($x);
for ($id=0; $id<$antalPersoner; $id++) {

    $dubletter = false;
    for ($id2=$id+1; $id2<$antalPersoner; $id2++) {
        if ($x[$id2] == $x[$id] && $y[$id2] == $y[$id]) {
            if (! $dubletter) {
                echo "Følgende personer på samme sted som: ";
                echo $id . " : (" . $x[$id] . ", " . $y[$id] . ")<br>";
                echo "Dubletter:<br>";
                $dubletter = true;
            }

            echo $id2 . "<br>";
        }
    }

}


Din manglede lidt ";" og stavefejl :p. Men virker! Desværre tror jeg at løsningen er for ressource krævende, men lærte da at spørgsmålet. Bare smid et svar, Nielle.

Svar :

thewizard > Har du prøvet mit forslag? Hvis det kommer an på performance, er det nemlig klart at foretrække.

terrak - sjov test :)

Det var bare hypotetisk - men synes det er godt at lave sådan en test. Jeg tænkte lidt over det, inden jeg gik i seng tidligere idag. Og kom op med den konklusion at gruppere menneskene. Er muligt - og vil nedsætte krævet ressourcer. :).

Jeg synes det er sjovt at lave en alternativ løsning, frem for at gå den vej der virker mest ligetil. Sad faktisk og grublede over løsningen længe, men resultatet er egentlig overraskende simpel.

Så tak for en lærerig opgave :-)

Og tak for et lærerigt svar ;).

Nu kommer ressourcer i to varianter: CPU-tid og hukommelsesforbrug. Som regel kan man optimere på den ene, men det vil så gå ud over den anden.

Min løsning er en O(n^2) og terrak's ligger et eller andet sted imellem en O(n) og en O(n^2). Til gengæld går den hårdt ud over CPU'en idet der skal laves streng-sammenlægninger og oprettes array-indgange og -opslag. Den går også ud over hukommelsen da der skal oprettes et nyt array til dublet-tjekket. Det er derfor lidt svært at sige hvilken der vinder i det lange løb.