On 05-10-2010 19:49, Bertel Lund Hansen wrote:
> Michael Rasmussen skrev:
>
>>> Fordi dit forslag kræver at hele arrayet bearbejdes og et nyt
>>> oprettes. Mit forslag kræver kun søgning i et eksisterende array.
>
>> Nu kræver bearbejdningen ikke andet end blot swap af pointere, så hvis
>> der skal udskrives et helt array, er min løsningen mindre kostbar end
>> din.
>
>> Min løsning har en kompleksitet på O(n), mens din har kompleksiteten
>> O(n²).
>
> Du må gerne forklare hvorfor en søgning har kompleksiteten O(n²).
> En slavisk gennempløjning har så vidt jeg kan se kompleksiteten
> O(n).
>
> Og hvordan undgår du en søgning med din metode når Kim skal slå
> et nummer op ud fra værdien?
array_search
Result: 4881
0.0003509521484375
in_array
Result: 1
0.00036311149597168
array_flip
Result: 4881
0.0037498474121094
<?php
$arraylength = 10000;
function randomchar($max) {
$abc= array("a","b","c","d","e","f","g","h","i","j","k", "l", "m", "n",
"o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z");
$str = '';
$i=0;
while($i < $max) {
$str .= $abc[rand(0,count($abc))];
$i++;
}
return $str;
}
// Lad os starte med at lave vores array
$array = array();
for($i=0;$i<$arraylength;$i++)
{
$array[] = randomchar(10);
}
// Lad os lige gøre det hele unikt
$array = array_unique($array);
// Lad os tage en random key og value ud som vi skal lege med
$key = array_rand($array);
$value = $array[$key];
// Så ryster vi posen et par gange
shuffle($array);
shuffle($array);
shuffle($array);
shuffle($array);
shuffle($array);
// Lad os time array_search
echo '<h3>array_search</h3>';
$start = microtime(true);
echo '<p>Result: ' . array_search($value, $array) . '</p>';
$endtime = microtime(true)-$start;
echo '<h5>' . $endtime . '</h5>';
// Lad os time in_array
echo '<h3>in_array</h3>';
$start = microtime(true);
echo '<p>Result: ' . in_array($value, $array) . '</p>';
$endtime = microtime(true)-$start;
echo '<h5>' . $endtime . '</h5>';
// Lad os time array_search
echo '<h3>array_flip</h3>';
$start = microtime(true);
$array = array_flip($array);
echo '<p>Result: ' . $array[$value] . '</p>';
$endtime = microtime(true)-$start;
echo '<h5>' . $endtime . '</h5>';