Are nested foreach loops to compare two multidimensional arrays efficient in PHP?

Question

I've got the following PHP code, which is taking a search term, and checking if any of the search terms could be or could have a nickname.

$search = $_GET['search-term'];
$indiviudal_terms = explode(" ",$search);
foreach($indiviudal_terms as $term) {
    foreach ($nicknames as $nameset) {//$nicknames is a multidimensional array that contains other arrays featuring sets of names, e.g. array("Abraham","Abe","Abie","Bram")
        foreach ($nameset as $variant_name) {
            if (strtolower($term) == strtolower($variant_name)) { //Checks to see if any of the search terms match any of the variant names in any of the sets of names.
                echo $nameset; //Just prints the set of names for the moment as I'm still writing to code.
            }
        }
    }
}

This works fine, but I worry that all these nested foreach loops may be inefficient. Is there a better way of achieving the same thing?

Answer 1

You call strtolower($term) during each iteration instead of just once. You can preprocess it:

$individual_dumps = array();
foreach (explode(" ", $search) as $term) {
    $individual_dumps[] = strtolower($term);
}

You can also use array_map for this, which may be a little slower, but with a shorter code:

$individual_dumps = array_map('strtolower', explode(" ", $search));

It may be better to change the order of the loops - make the loop going through all the search terms the innermost. In this way you can also call strtolower($variant_name) just once, and not count($individual_dumps) times. (You can also store them in lower case, avoiding this step completely.)

foreach ($nicknames as $nameset) {
    foreach(array_map('strtolower', $nameset) as $variant_name) {
        foreach($individual_dumps as $term) {
            if ($term == $variant_name) {
                echo $nameset;
            }
        }
    }    
}

When you have all the elements in lower case, you can use array_intersect, which should cut complexity for each $nameset from O(m * n) to O(n * log n) of the larger array. (You may be even able to improve it to O(n) using this trick). However different, older source mentions other complexity, so YMMV.

foreach ($nicknames as $nameset) {
    if (array_intersect(array_map('strtolower', $nameset), $individual_dumps)) { //true for non-empty array -> some elements are the same
        echo $nameset;
    }    
}

Now, previous optimizations only optimized the foreach loops. There is another possibility - you can use something like array_flip and then array_key_exists for each search term, which may be very fast (because array_key_exists is close to O(1)). I say may be because it depends on the cost of preprocessing, which may not be actually faster than searching using the foreach loop.

Therefore, if you search for multiple independent queries (to justify the preprocessing) or especially if you can store $nicknames preprocessed, then this should be a clear winner with complexity very close to O(number of terms). This has a hidden assumption of small number of search terms and large number of nicknames.

Preprocessing:

$nicknames_preprocessed_keys = array();
$nicknames_preprocessed_namesets = array();
foreach ($nicknames as $nameset) {
    $nameset_key = array_push($nicknames_preprocessed_namesets, $nameset) - 1;
    foreach(array_map('strtolower', $nameset) as $variant_name) {
        $nicknames_preprocessed_keys[$variant_name] = $nameset_key;
    }
}

(Notice that two arrays are used: that is because you work with the whole $nameset as a result. Storing this as value for each key would result in large array.)

Search:

$individual_dumps = array_map('strtolower', explode(" ", $search));
foreach ($individual_dumps as $term) {
    if (array_key_exists($nicknames_preprocessed_keys, $term)) {
        echo $nicknames_preprocessed_namesets[$nicknames_preprocessed_keys[$term]];
    }
}