Search array for similar objects

Question

Given an array of arrays like this:

$array = array( 
            0 => array (
               0 => 35,
               1 => 30, 
               2 => 39
            ),
            1 => array (
               0 => 20,
               1 => 12, 
               2 => 5
            ),
            ...

            n => array (
               0 => 10,
               1 => 15, 
               2 => 7
            ),
         );

I have the need to find the entry in the array which is closer to given parameters

find($a, $b, $c) {
  //return the closer entry to the input
}

For closer entry I mean the entry which has closer values to the ones gave in input, e.g. passing (19, 13, 3) it should return $array[1]

The way in which I do the calculation at the moment is looping through the whole array, keeping a variable $distance which starts from -1, and a temporary $result variable. For each element I calculate the distance

$dist = abs( subarray[0] - $a ) + abs ( subarray[1] - $b ) + abs( subarray[2] - $c ) 

and if the calculated distance is equal to -1 or lower than the variable $distance which is out of the loop, I assign the new distance to the varaible and I save the corresponding array in the $result variable. At the end of the loop I end up having the value I need.

Also, one of the values can be empty: e.g. (19, 13, false) should still return $array[1] and the calculation should then ignore the missing parameter - in this case the distance is calculated as

$dist = abs( subarray[0] - $a ) + abs ( subarray[1] - $b );

ignoring the values of subarray[2] and $c.

The problem is, even if my code is working, it took too much time to execute as the size of the array can easily go up to many hundred thousands elements. We are still talking about milliseconds, but for various reasons this is still unacceptable. Is there a more effective way to do this search in order to save some time?

Answer 1

I basically used a concept of proximity (lesser distance total for each array) and returned that. The code was made in a way that can improve very well in so many routines.

PS: I didn't used advanced functions or other things because you are concerned about performance issues. It's most simplest routine I could did in a short period of time.

$array = array(
    0 => array (
        0 => 35,
        1 => 30,
        2 => 39
    ),
    1 => array (
        0 => 20,
        1 => 12,
        2 => 5
    ),
);

$user = array(19,13,3);

function find($referencial, $input){
    $totalRef = count($referencial);
    if (is_array($referencial)){
        for ($i = 0; $i < $totalRef; $i++) {
            if (is_array($referencial[$i])){
                $totalSubRef = count($referencial[$i]);
                $proximity = array();
                for ($j = 0; $j < $totalSubRef; $j++) {
                    $proximity[$i] += abs($referencial[$i][$j] - $input[$j]);
                }
                if ($i > 0){
                    if ($maxProximity['distance'] > $proximity[$i]) {
                        $maxProximity['distance'] = $proximity[$i];
                        $maxProximity['index'] = $i;
                    }
                } else {
                    $maxProximity['distance'] = $proximity[$i];
                    $maxProximity['index'] = $i;
                }
            }
        }
        return $maxProximity;
    } else {
        exit('Unexpected referencial. Must be an array.');
    }
}

$found = find($array, $user);
print_r($found);
//Array ( [distance] => 4 [index] => 1 )
print_r($array[$found['index']]);
// Array ( [0] => 20 [1] => 12 [2] => 5 )

Answer 2

A custom function - maybe there is a better way but check it out :

In a few words :

Search all the items and find in percentage the difference between the number it checks($mArray[0...3]) and the number you gave($mNumbersToFind[0...3]. Add all the three number's (of each element) possibilities - find the max - keep the position and return the array.

$array = array( 
            array (
               0 => 13,
               1 => 15, 
               2 => 4
            ),
            array (
               0 => 20,
               1 => 12, 
               2 => 5
            ),

            array (
               0 => 13,
               1 => 3, 
               2 => 15
            ),
         );


$mNumbersToFind = array(13,3,3);

$mFoundArray = find($mNumbersToFind, $array);

echo "mFinalArray : <pre>";
print_r($mFoundArray);


function find($mNumbersToFind, $mArray){

    $mPossibilityMax = count($mNumbersToFind);
    $mBiggestPossibilityElementPosition = 0;
    $mBiggestPossibilityUntilNow = 0;


    foreach($mArray as $index => $current){

        $maxPossibility = 0;

        foreach($current as $subindex => $subcurrent){



            $mTempArray[$index][$subindex]['value'] = $subcurrent - $mNumbersToFind[$subindex];

            $percentChange = (1 - $mTempArray[$index][$subindex]['value'] / $subcurrent) * 100;
            $mTempArray[$index][$subindex]['possibility'] = $percentChange;
            $maxPossibility += $percentChange/$mPossibilityMax;


        }


        $mTempArray[$index]['final_possibility'] = $maxPossibility;

        if($maxPossibility > $mBiggestPossibilityUntilNow){
            $mBiggestPossibilityUntilNow = $maxPossibility;
            $mBiggestPossibilityElementPosition = $index;
        }



    }

    echo "mTempArray : <pre>"; // Remove this - it's just for debug
    print_r($mTempArray); // Remove this - it's just for debug

    return $mArray[$mBiggestPossibilityElementPosition];
}

Debug Output ($mTempArray) :

mTempArray :
Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [value] => 0
                    [possibility] => 100
                )

            [1] => Array
                (
                    [value] => 12
                    [possibility] => 20
                )

            [2] => Array
                (
                    [value] => 1
                    [possibility] => 75
                )

            [final_possibility] => 65
        )

    [1] => Array
        (
            [0] => Array
                (
                    [value] => 7
                    [possibility] => 65
                )

            [1] => Array
                (
                    [value] => 9
                    [possibility] => 25
                )

            [2] => Array
                (
                    [value] => 2
                    [possibility] => 60
                )

            [final_possibility] => 50
        )

    [2] => Array
        (
            [0] => Array
                (
                    [value] => 0
                    [possibility] => 100
                )

            [1] => Array
                (
                    [value] => 0
                    [possibility] => 100
                )

            [2] => Array
                (
                    [value] => 12
                    [possibility] => 20
                )

            [final_possibility] => 73.333333333333
        )

)

Final Output :

mFinalArray : 
Array
(
    [0] => 13
    [1] => 3
    [2] => 15
)