How to optimize this algorithm?

Question

I have two sets of arrays like this for example.

$Arr1['uid'][]='user 1'; $Arr1['weight'][]=1;
$Arr1['uid'][]='user 2'; $Arr1['weight'][]=10;
$Arr1['uid'][]='user 3'; $Arr1['weight'][]=5;

$Arr2['uid'][]='user 1'; $Arr2['weight'][]=3;
$Arr2['uid'][]='user 4'; $Arr2['weight'][]=20;
$Arr2['uid'][]='user 5'; $Arr2['weight'][]=15;
$Arr2['uid'][]='user 2'; $Arr2['weight'][]=2;

The size of two arrays could be different of course. $Arr1 has coefficient of 0.7 and $Arr2 has coefficient of 0.3. I need to calculate following formula

$result=$Arr1['weight'][$index]*$Arr1Coeff+$Arr2['weight'][$index]*$Arr2Coeff;

where $Arr1['uid']=$Arr2['uid']. So when $Arr1['uid'] doesn't exists in $Arr2 then we need to omit $Arr2 and vice versa.
And, here is an algorithm I am using now.

foreach($Arr1['uid'] as $index=>$arr1_uid){
    $pos=array_search($arr1_uid, $Arr2['uid']);
    if ($pos===false){
        $result=$Arr1['weight'][$index]*$Arr1Coeff;
        echo "<br>$arr1_uid has not found and RES=".$result;
    }else{
        $result=$Arr1['weight'][$index]*$Arr1Coeff+$Arr2['weight'][$pos]*$Arr2Coeff;
        echo "<br>$arr1_uid has found on $pos and RES=".$result;
    }
}

foreach($Arr2['uid'] as $index=>$arr2_uid){
    if (!in_array($arr2_uid, $Arr1['uid'])){
        $result=$Arr2['weight'][$index]*$Arr2Coeff;
        echo "<br>$arr2_uid has not found and RES=".$result;
    }else{
        echo "<br>$arr2_uid has found somewhere";
    }
}

The question is how can I optimize this algorithm? Can you offer other better solution for this problem?
Thank you.

Answer 1

You can impelement binary searching in O(log(n)) complexity insead of your linear O(n) array_search. But you must before create tree from this or sort this array in O(n*log(n)).

More information about binary searching you can find at:

• http://en.wikipedia.org/wiki/Binary_search_algorithm
• http://en.wikipedia.org/wiki/Binary_search_tree

Answer 2

firstly you should intialize the array as the associative array. the calculations would be more easily

Answer 3

Due to the way you have your arrays organized, you can use array_combine($keys, $values) to assemble $Arr1 and $Arr2 into associative arrays using keys from ['uid'] and values from ['weight']. Using the associative arrays simplifies the calculation quite a bit:

$combi1 = array_combine($Arr1['uid'], $Arr1['weight']);
$combi2 = array_combine($Arr2['uid'], $Arr2['weight']);

// loop through the keys from both arrays
foreach (array_keys($combi1+$combi2) as $uid) {
    // use the value from $combi1, or 0 if it isn't set
    $value1 = isset($combi1[$uid]) ? $combi1[$uid] : 0;
    // use the value from $combi2, or 0 if it isn't set
    $value2 = isset($combi2[$uid]) ? $combi2[$uid] : 0;
    // calculate our final weight
    $result = $value1 * $Arr1Coeff + $value2 * $Arr2Coeff;
    echo "<br>$uid final weight: ".$result."\n";
}

Results Compared

Your code:

user 1 has found on 0 and RES=1.6
user 2 has found on 3 and RES=7.6
user 3 has not found and RES=3.5
user 1 has found somewhere
user 4 has not found and RES=6
user 5 has not found and RES=4.5
user 2 has found somewhere

My Code:

user 1 final weight: 1.6
user 2 final weight: 7.6
user 3 final weight: 3.5
user 4 final weight: 6
user 5 final weight: 4.5

Answer 4

It would be easier if you used the user as the array key. Something like this:

$Arr1['user 1'] => array('weight'=>1);
$Arr1['user 2'] => array('weight'=>10);
...

Then you can use array_diff_assoc and array_intersect_assoc to find out what which elements are in and not in the other array.