Binary search vs in_array

Enfernikus · 08-14-2009, 06:54 PM

I was working with some arrays and found the in_array function a bit slow so I decided to try an iterative binary search and found that when it's doing it's own sorting it's about as fast or faster some of the time and when sorting is taken out and done right after the array declaration the iterative binary search is much much faster so the point I guess I'm trying to make is...

Anyone know the algorithm PHP uses?

In benchmarks is ended up something like this

Quote:

in_array: 0.464353
binary search: 0.048116
Key: 9j35igizdslija

With sorting abstracted

Quote:

in_array: 0.080093
binary search: 0.00022699999999998
Key: zdslijaeg04hj0fjser;kj305hpoerjgj405hrgiuho w54htf[]

This is the benchmark code to try it out

php Code:

<?php


$longassString = 'asdjbavlzkjsbdflin 39ho34j03u-4tpejuurjg9j35igizdslijaeg04hj0fjser;kj305hpoerjgj405hrgiuho w54htf[]';
$strlen = strlen($longassString);
for($i = 0; $i < 2000; ++$i){
    $array[] = substr($longassString, rand(0, $strlen), rand(0, $strlen));
}
$array[] = '9j35igizdslija';

uasort($array, function($a, $b){
    return  strlen($a) > strlen($b) ? -1 : 1;
});
$e = $array[rand(0, count($array))];

$d = microtime();
for($i = 0; $i < 2000; ++$i)
    in_array($e, $array);
echo 'in_array: ', microtime() - $d;

echo '<br />';

$d = microtime();

$found = null;
for($i = 0; $i < 2000; ++$i)
{
    $sizeOfArray = count($array);
    $middle = floor(($sizeOfArray) / 2);
    $element = $array[$middle];
    if( $element == $e )
        return true;
        
    //If we're out here it didn't work
    if( strlen($element) > $e )
    {
        for($i = $middle; $i < $sizeOfArray; ++$i)
            if( $array[$i] == $e ) $found = $array[$i]; break;
    }else{
        for($i = 0; $i < $middle; ++$i)
            if( $array[$i] == $e ) $found = $array[$i]; break;
    }
    
    $found = false;
}
echo 'binary search: ', microtime() - $d, '<br />';
echo 'Key: ' . $found;