Как оптимизировать этот алгоритм?

Question

Например, у меня есть два набора таких массивов.

$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;

Размер двух массивов, конечно, может быть разным. $ Arr1 имеет коэффициент 0,7, а $ Arr2 имеет коэффициент 0,3.Мне нужно рассчитать следующую формулу

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

, где $Arr1['uid']=$Arr2['uid'].Поэтому, когда $Arr1['uid'] не существует в $Arr2, нам нужно пропустить $Arr2 и наоборот.
И вот алгоритм, который я сейчас использую.

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";
    }
}

ВопросКак я могу оптимизировать этот алгоритм?Можете ли вы предложить другое лучшее решение для этой проблемы?
Спасибо.

Answer 1

Благодаря организации ваших массивов вы можете использовать array_combine ($ keys, $ values) для сборки $Arr1 и $Arr2 в ассоциативные массивы с использованием ключей от ['uid'] и значений от ['weight']. Использование ассоциативных массивов значительно упрощает вычисления:

$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";
}

Сравнение результатов

Ваш код:

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

Мой код:

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 2

Было бы проще, если бы вы использовали пользователя в качестве ключа массива. Примерно так:

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

Затем вы можете использовать array_diff_assoc и array_intersect_assoc, чтобы узнать, какие элементы находятся, а какие нет в другом массиве.

Answer 3

Во-первых, вы должны инициализировать массив как ассоциативный массив. Расчеты были бы проще.

Answer 4

Вы можете выполнить бинарный поиск в O(log(n)) сложности внутри вашей линейной O(n) array_search. Но перед этим вы должны создать дерево или отсортировать этот массив в O(n*log(n)).

Более подробную информацию о бинарном поиске вы можете найти по адресу:

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