quickest scan for match in an array 1

[thedaver]

Knowing that the most efficient or quickest method is not always obvious... I ask:

with an array of

$array=array("a","b","c","d");

How do I efficiently/quickly determine if the string "c" is an exact member of an array of strings or not?

Current contender is:

$found=0;
$array=array("a","b","c","d");
$matchme="c";
foreach ($array as $a) {
  if ($a == $matchme) { $found=1; break; }
}
if ($found) {.......}

Thoughts on doing better? Obvious penalty now is matching at the end of the array takes "longer".


D.E.R. Management - IT Project Management Consulting

http://www.dermanagement.com/

 

[sleipnir214]

How about in_array()?



Want the best answers? Ask the best questions! TANSTAAFL!

 

[thedaver]

There ya go! Thx

D.E.R. Management - IT Project Management Consulting

http://www.dermanagement.com/

 

[Miros]

If your array elements are in order, you want to write your own loop and add:

if ($a < $matchme) { $found=1; break; }

This really speeds up when $a would be close to the beginning of the array.

You can also reduce the number of checks against an array in order (of size n) by checking against the center element (n/2), then against n/4 or 3n/4 depending on if the new element is larger or smaller than the n/2 element. And so on until you've found your element or your search range has basically vanished and not found it. Pseudocode:

boolean findArray( Array<Object> myarray, Object find, int low, int high )
{
   center = (high + low) / 2
   if find = myarray[center]
      return true ;
   if find < myarray[center]
      if low = find
         return false ;
      return findArray( myarray, find, low, center - 1 )
   if find > myarray[center]
      if high = find
         return false ;
      return findArray( myarray, find, center + 1, high )
}

 

[sleipnir214]

I'm pretty certain that interpreted PHP code is not going to be faster than a compiled builtin PHP function. More efficient, possibly, but I strongly doubt faster.

From a somewhat cursory look at the PHP source code, it appears to me that PHP generates hashes of the contents of the elements of arrays and performs searches against those hashes. That would improve the efficiency of the builtin function.



Want the best answers? Ask the best questions! TANSTAAFL!

 

[Miros]

Especially if your data is not in order...