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:

-- Kevin Gessner
August 24, 2008

This is part of Nihilartikel, my collected writings.
Back to the home page