Sometime I need to test whether a given value is in a list. In PHP there is a built in function in_array() which does this test. But under the hood it might make use of an iteration, comparision of each list element, and the original value. This iteration might take some time. There is another method which takes two steps. The first step is to convert the original list (array) into an associative array, where the keys will be the elements of the list, and their values will be 1. Then in the second step we simply check the existence of the key with the familiar isset().
// the list
$list_of_values = array('one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten');
// some values to test whether they are in the list
$values_to_test = array('one', 'blue', 'green', 'two', 'fourty', 'six');
$testables_count = count($values_to_test);
$test_count = 100000;
// first method: in_array()
$t0 = microtime(TRUE);
$found = $not_found = 0;
for($i=0; $i < $test_count; $i++) {
$test_value = $values_to_test[$i % $testables_count];
if (in_array($test_value, $list_of_values)) {
$found++;
}
else {
$not_found++;
}
}
$t1 = microtime(TRUE);
printf("Found %d, not found %d in %.3f\n", $found, $not_found, ($t1-$t0));
// second method
// step one: creating an associative array
$tassoc0 = microtime(TRUE);
$list_of_values_as_assoc = array_flip($list_of_values);
$tassoc1 = microtime(TRUE);
// step two: testing the values
$t0 = microtime(TRUE);
$found = $not_found = 0;
for($i=0; $i < $test_count; $i++) {
$test_value = $values_to_test[$i % $testables_count];
if (isset($list_of_values_as_assoc[$test_value])) {
$found++;
}
else {
$not_found++;
}
}
$t1 = microtime(TRUE);
printf("Found %d, not found %d in %.6f + %.3f\n", $found, $not_found, ($tassoc1-$tassoc0), ($t1-$t0));
The result is that our original preconception was true, the in_array simply iterates over the list, so it is 10-20 times slower, than the second algorithm. Moreover, the in_array method speed is depending on the order or items in the list, while the second approach is pretty constant. So if the code has a lots of such tests, it is worth to transform the list to an associative array.
Update: I would like to say a thank to Szabó Dénes (@szabodenes) that he called my attention to the array_flip() method, which makes it easy to create an associative array from a simple list-type array.
