Performance of searching in lists in PHP

This report compares different ways of searching elements in lists.

Searching a string

How much of a difference is there between searching through all elements and accessing it by key?

Explanation of results

Results are measured in operations per second (K = 1000, M = 1,000,000).

The method score is based on the median average. The fastest method always has a base score of 1x and other methods are compared to it. For example a score of 3x means it's 3 times slower than the fastest method.

You can show or hide the source code of any method by clicking on the .

Method First of 1000 Last of 1000 Not found Average Median Score

Check if string key is set

$map = $p['map'];
$needle = $p['needle'];
while ($n--) {
    $found = isset($map[$needle]);
}
 7.1M 7.0M 15.5M 9.9M 7.1M 1.0x

Check for string key in a map

$map = $p['map'];
$needle = $p['needle'];
while ($n--) {
    $found = array_key_exists($needle, $map);
}
 2.1M 2.1M 2.5M 2.2M 2.1M 3.4x

Search for value in list

$list = $p['list'];
$needle = $p['needle'];
while ($n--) {
    $found = array_search($needle, $list);
}
 2.5M 46.2K 45.1K 856.5K 46.2K 153.2x

Strict comparison in a foreach loop

$list = $p['list'];
$needle = $p['needle'];
while ($n--) {
    $found = false;
    foreach ($list as $value) {
        if ($value === $needle) {
            $found = true;
            break;
        }
    }
}
 44.7K 11.5K 12.4K 22.7K 12.4K 573.2x

Simple comparison in a foreach loop

$list = $p['list'];
$needle = $p['needle'];
while ($n--) {
    $found = false;
    foreach ($list as $value) {
        if ($value == $needle) {
            $found = true;
            break;
        }
    }
}
 44.4K 10.2K 10.3K 21.6K 10.3K 686.5x

Searching in a sorted list

If all you have is a sorted list, a binary search will do wonders.

Assocative arrays are still your best friend. Instead of sorting by value, objects are accessed and mapped by value.

A binary search makes use of the fact that the list is sorted by the search needle. The complexity is O(log(n)) with n being the array size.

Iterative searches are acceptable for small lists and the complexity is O(n). Obviously searching in big lists is quite slow unless you're lucky.

Method 1/1000 333/1000 500/1000 1000/1000 1/100k 3333/100k 50k/100k 6666/100k 100k/100k Average Median Score
$map = $p['map'];
$needle = $p['needle'];
while ($n--) {
    $result = null;
    if (isset($map[$needle . '_'])) {
        $result = $map[$needle . '_'];
    }
    if ($result !== $needle) {
        throw new \Exception('');
    }
}
 2.7M 2.7M 2.7M 2.7M 2.9M 2.7M 2.7M 2.6M 2.6M 2.7M 2.7M 1.0x 
$list = $p['list'];
$needle = $p['needle'];
while ($n--) {
    $count = count($list);
    $left = 0;
    $right = $count - 1;
    $result = null;
    while ($left <= $right) {
        $middle = (int) ($left + (($right - $left) / 2));
        if ($list[$middle] === $needle) {
            $result = $middle;
            break;
        }
        if ($list[$middle] > $needle) {
            $right = $middle - 1;
        } else {
            $left = $middle + 1;
        }
    }
    if ($list[$result] !== $needle) {
        throw new \Exception('');
    }
}
 368.4K 368.1K 1.4M 336.0K 227.6K 223.0K 1.4M 212.0K 206.6K 530.6K 336.0K 8.0x 
$list = $p['list'];
$needle = $p['needle'];
while ($n--) {
    $result = null;
    $count = count($list);
    for ($i = 0; $i < $count; $i++) {
        if ($list[$i] === $needle) {
            $result = $i;
            break;
        }
    }
    if ($list[$result] !== $needle) {
        throw new \Exception('');
    }
}
 1.7M 30.2K 20.3K 10.1K 1.7M 301.1 199.5 146.3 98.5 380.3K 10.1K 264.6x
nochso/Benchmark
0.4.0
ran each test
> 1000 ms
on
in
56.4 seconds
using PHP
5.6.14-1+deb.sury.org~trusty+1
with
Zend OPcache
Xdebug
on
Linux 3.16.0-38-genericx86_64