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