PHP, in_array and fast searches (by the end) in arrays
I assume that in_array
is a linear search from 0 to n-1.
The fastest search will be to store the values as the keys and use array_key_exists
.
$a['foo'] = true;
$a['bar'] = true;
if (array_key_exists('foo', $a)) ...
But if that's not an option, you can make your own for indexed arrays quite easily:
function in_array_i($needle, array $a, $i = 0);
{
$c = count($a);
for (;$i < $c; ++$i)
if ($a[$i] == $needle) return true;
return false;
}
It will start at $i
, which you can keep track of yourself in order to skip the first elements.
Or alternatively...
function in_array_i($needle, array $a, $i = 0);
{
return in_array($needle, $i ? array_slice($a, $i) : $a);
}
You can benchmark to see which is faster.
How works internally the in_array function?
Internally the in_array()
searches from the beginning to the end of the array. So in your case this is slow.
Depending of the nature of your data you can change the search strategy. If you only have non-duplicate values and all values are either string or integer (not NULL
), a common trick is to array_flip()
the array which works pretty fast and then check if there is an entry for your value as key in the array hash via isset()
:
$array = array( ... non-duplicate string and integer values ... );
$needle = 'find me!';
$lookup = array_flip($array);
$found = isset($lookup[$needle]) ? $lookup[$needle] : false;
if (false === $found) {
echo "Not found!\n";
} else {
echo "Found at {$found}!\n";
}
If these pre-conditions are not met, you can do that what konforce suggested.
If you have really much data and it's not only that you're looking at either from the beginning or end, you might want to implement one search algorithm on your own, like neither starting from the beginning nor end, but wrapping and/or starting at a random position to distribute the search time.
Additionally you can keep elements sorted while adding to the array probably which can then be searched much faster with a fitting algorithm.