Best method for exact match in array with PHP?

This is an old website post.

New post address:
https://www.pisciottablog.com/2018/03/25/best-method-for-exact-match-in-array/
+++ This wordpress.com domain will not be kept up-to-date anymore+
+++ Please, use the new one (pisciottablog.com) ++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

 

During a job interview one asked me: “how would you search for a word inside a very long array?”. I answered just by using the foreach loop and compare the single content with the searched word. But according to him it would not fit with very big sized arrays, so his suggestion was to flip the array (changing all keys and values) and then to input the word in the key field and see if it’s found. Now, beyond any justifying logic I think it could be interesting to check the reality with some tests.

Let an array being created in three different ways using the following three different functions. The first one creates an array having 1 million different words as values and the last one being literally “word”, which is the string we need to search for. Th second one creates an array of 1 million of the elements, after which “word” is always the last element. The third function uses a mix array, where the first half of all elements is made with different words, and the other half with the same, having also as last element the string “word”.

function array1(){
	for($i=0;$i<1000000;$i++){
		$list[]="wordnumber$i";
	}
	$list[]="word";
	return $list;
}

function array2(){
	for($i=0;$i<1000000;$i++){
		$list[]="wordnumber";
	}
	$list[]="word";
	return $list;
}

function array3(){
	for($i=0;$i<500000;$i++){
		$list[]="wordnumber";
	}
	for($i=500000;$i $value){
		if($value==$match) return true;
	}
		return false;
}

function exact_match2($array,$match){
	$array=array_flip($array);<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>
	return isset($array[$match]);
}

Then I measured the time for each function in each case putting the function to measure between the following two lines one by one:

$start = microtime(true);
//exact_match1($list,"word");
//exact_match2($list,"word");
$time = microtime(true) - $start;

The result? I resumed the relative measurements in the following table:

	All elements different	Half different, half equal	All elements equal
time1 (foreach)	0.063 µs	0.059 µs	0.056 µs
time2 (flip)	0.119 µs	0.068 µs	0.026 µs
(time2/time1)*100	189.38%	114.45%	46.39%

So just in the case most of the array’s values (as strings) are equal to each other it could be convenient to use the flip function. But why should that happen? If we have a words list it’s expected to be different for most of them. After searching for one million of different item the flip method takes around the 189% of the time needed for foreach.

What’s very interesting is what happen if we put numbers instead of words, before the last string value “word” we are searching for. If we build the array with integers using the following function

function array4(){
	for($i=0;$i<1000000;$i++){
		$list[]=$i*2;
	}
	$list[]="word";
	return $list;
}

With such values, the string "word" can be found using the flip function more than 10000 times slower than foreach!

Posterity will judge.