Fast Array Membership in PHP
PHP provides two different functions for checking array membership: in_array and array_search.
$array = array('abc', 'def', 'ghi');
in_array('abc', $array); // true
in_array('123', $array); // false
I present a faster technique for checking array membership. PHP’s array type is an associative array; that is, keys can be strings or arbitrary integers, rather than strictly ordered indices. Plus, it’s optimized for fast key lookups. PHP’s library provides a function that transposes keys and values in an array, array_flip . With this function, we can convert our array search for values into a key lookup:
$array = array('abc', 'def', 'ghi');
$flip = array_flip($array);
isset($flip['abc']); // true
isset($flip['123']); // false
A benchmark of 10,000 iterations of finding a value in a 1,000 element array:
| Technique | Time (s) | % Time | Notes |
|---|---|---|---|
| array_search (Strict) | 0.0936079025269 | 2.97% | |
| array_search (Loose) | 0.187884092331 | 5.96% | |
| in_array (Strict) | 0.0828459262848 | 2.63% | |
| in_array (Loose) | 0.183130979538 | 5.81% | |
| array_flip (naive) | 1.13642597198 | 36.05% | See below |
| array_flip (smart) | 0.0022439956665 | 0.07% | |
| foreach | 1.46642112732 | 46.51% |
Download sample code and benchmark (requires PEAR::Benchmark)
A few caveats:
- Array keys can only be strings or integers, so arrays of other types cannot take advantage of this technique.
- If you’re only going to be checking for a small number of values, the cost of flipping the array will probably outweigh the benefits (see the “naive” case for array_flip).
- Comparison is not strict ; i.e. it’s equivalent to “==” not “===”.