1
\$\begingroup\$

I need to match values in Needle & Haystack arrays, using alternate Ontology values when relevant.

This syntax works, however I would like to know if there is a more efficient way to do this as I will be using it for several corresponding $AltNeedle arrays for each of 1000+ $needles and $haystack arrays.

In my use case, the Needle & Haystack correspond with Product and Customer attributes respectively, and matches are made and ranked by assessing thousands of attributes for each, and attributes often have an array of values. One way in which Alt. Values are used are to incorporate closely related values into certain match results.

<?php
$needles = ['John', 'Alex', 'Pam'];
$haystack = ['John','Alexander','Kim', 'Michael'];
$AltNeedle = ['Alexander', 'Alex', 'Alexi'];

foreach ($needles as $current_needle) {
    if (in_array($current_needle, $AltNeedle) ) { // Exists in $AltNeedle
        foreach ($AltNeedle as $current_AltNeedle) {
                if (in_array($current_AltNeedle, $haystack) ) { // Compares $current_AltNeedle to $haystack
                    echo $current_AltNeedle." True; ";
                } 
        } // Ends $AltNeedle foreach
    }
    elseif (in_array($current_needle, $haystack) ) {
        echo $current_needle.": True; ";
    }
    else {
        echo $current_needle.": False; ";
    }                  
} // End foreach
?>

RESULT:

John: True; Alexander True; Pam: False;

\$\endgroup\$
1
\$\begingroup\$

The whole thing needs restructuring if you are worried about performance. First, you probably shouldn't be using an array for your haystack. Considering that you will know with certainty what you are looking for in the haystack, it should not be an array which must be iterated in \$O(n)\$ to determine presence of an item. An associative array with haystack values as keys or even a stdClass item with haystack values as properties would allow for \$O(1)\$ lookup to determine if a value is present. That might look something like this (perhaps you have more meaningful full data that true to put at each key):

[
    'John' => true,
    'Alexander' => true,
    'Kim' => true,
    'Michael' => true,
    ...
]

The same can be said for the data structure around the alternative needles. There is no reason to perform an \$O(n)$\ iteration on the alt needle array to see if an item has a lookup value. Imagine an associative array like:

[
    'Alex' => [
        'Alexander',
        'Alexi'
    ],
    'Alexi' => [
        'Alex',
        'Alexander'
    ],
    'Alexander' => [
        'Alex',
        'Alexi,
    ],
    ...
]

This could give you \$O(1)\$ access to an array of alternate names.

So you code might be changes to look like:

$results = [];
foreach($needles as $needle) {
   $names = [$needle];
   if(array_key_exists($needle, $altNeedles)) {
       $names = array_merge($searches, $altNeedles[$needle]);
   }
   foreach($names as $name) {
       if(array_key_exists($name, $haystack)) {
           $results[$name] = true;
       }
   }
}

Given: m = needles array size n = number of alt needles per given name p = haystack size

This reduces overall worst case complexity from \$O(m*n^2*p)\$ to \$O(m * n)\$

In best cases (single needles, no alternate names) this solution degenerates to \$O(1)\$ complexity, whereas, yours still always requires at least \$O(p)\$.

Now, if you have the opportunity to really rethink you data structures, this can be improved even further. For example, are what you really calling "alternate needles" really simply alternates on the haystack? In other words, can the alternate names simply become a part of the haystack such that you can get \$O(1)\$ look up for each needle?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I am definitely open to thinking about it differently:) For obvious reasons I used a highly simplified version of what I'm trying to do, & it hadn't occurred to me that (unlike on StackOverflow) I might need some help connecting the dots... In my use case, the Needle & Haystack correspond with Product & Customer attributes respectively, and matches are made & ranked by assessing thousands of attributes for each, & attributes often have an array of values (ie. Neckline Silhouette). One example of how Alt. Values are used are to incorporate closely related Silhouettes into certain match results. \$\endgroup\$ – Chaya Cooper May 15 '17 at 23:24
  • 1
    \$\begingroup\$ @ChayaCooper I would suggest that you open new question with your actual real-world code and use case information, as making your code generic for the review is actually exactly what we don't want posters doing on codereview, as you are not likely to get feedback that is meaningful to you. At any rate, iterating through arrays as you are doing is not likely to be performant at all, especially when you are talking about making comparisons against thousands of attributes at a time (think of how many operations this will cause when you have exponential complexity). \$\endgroup\$ – Mike Brant May 16 '17 at 15:22
  • \$\begingroup\$ You're absolutely right, and now I understand why CodeReview is going to be just as important to my learning curve as StackOverflow has been :) \$\endgroup\$ – Chaya Cooper May 16 '17 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.