php array_intersect() efficiency

Question

consider the below script. two arrays with only three values.when i compare these two arrays using array_intersect(). the result is fast.

    <?php
$arrayOne = array('3', '4', '5');
$arrayTwo = array('4', '5', '6');

$intersect = array_intersect($arrayOne, $arrayTwo);

print_r($intersect );

?>

my question is what is the efficiency of the array_intersect(). whether if we compare two arrays both having 1000 values each. would produce better result..... r we need to use some hash function to deal with finding common values quickly which will be effective???.. i need ur suggestion for this...

i am doing an application.if an person comes and login using facebook login.then the application will get his friends list and find whether any friends as commented in my app before and show it to him. roughly a friends may have 200 to300 friends in facebook and db has more than 1000 records. i need to find that efficiently how can i do that.......

Answer 1

Intersection can be implemented by constructing a set of the searched values in the second array, and looking up in a set can be made so fast that it takes essentially constant time on average. Therefore, the runtime of the whole algorithm can be in O(n).

Alternatively, one can sort the second array (in O(n log n)). Since looking up in a sorted array has a runtime in O(log n), the whole algorithm should then have a runtime in O(n log n).

According to a (short, unscientific) test I just ran, this seems to be the case for php's array_intersect:

Here's the code I used to test it. As you can see, for an input size as small as 1000, you don't need to worry.

Answer 2

array_intersect sorts the arrays before comparing their values in parallel (see the use of zend_qsort in the source file array.c). This alone takes O(n·log n) for each array. Then the actual intersection does only take linear time.

Depending on the values in your arrays, you could implement this intersection in linear time without the sorting, for example:

$index = array_flip($arrayOne);
foreach ($arrayTwo as $value) {
    if (isset($index[$value])) unset($index[$value]);
}
foreach ($index as $value => $key) {
    unset($arrayOne[$key]);
}
var_dump($arrayOne);

Answer 3

The fastest solution I found:

function arrayIntersect($arrayOne, $arrayTwo) {
        $index = array_flip($arrayOne);
        $second = array_flip($arrayTwo);

        $x = array_intersect_key($index, $second);

        return array_flip($x);
}

Tests I have made looks like below:

function intersect($arrayOne, $arrayTwo)
{
    $index = array_flip($arrayOne);
    foreach ($arrayTwo as $value) {
        if (isset($index[$value])) unset($index[$value]);
    }
    foreach ($index as $value => $key) {
        unset($arrayOne[$key]);
    }

    return $arrayOne;
}

function intersect2($arrayOne, $arrayTwo)
{
    $index = array_flip($arrayOne);
    $second = array_flip($arrayTwo);

    $x = array_intersect_key($index, $second);

    return array_flip($x);

}

for($i =0; $i < 1000000; $i++) {
    $one[] = rand(0,1000000);
    $two[] = rand(0,100000);
    $two[] = rand(0,10000);
}

$one = array_unique($one);
$two = array_unique($two);

$time_start = microtime(true);
$res = intersect($one, $two);
$time = microtime(true) - $time_start;

echo "Sort time $time seconds 'intersect' \n";


$time_start = microtime(true);
$res2 = array_intersect($one, $two);
$time = microtime(true) - $time_start;

echo "Sort time $time seconds 'array_intersect' \n";


$time_start = microtime(true);
$res3 = intersect2($one, $two);
$time = microtime(true) - $time_start;

echo "Sort time $time seconds 'intersect2' \n";

Results from php 5.6 :

Sort time 0.77021193504333 seconds 'intersect' 
Sort time 6.9765028953552 seconds 'array_intersect' 
Sort time 0.4631941318512 seconds 'intersect2'

Answer 4

From what you state above, I would recommend you to implement a caching mechanism. That way you would of load the DB and speed up your application. I would also recommend you to profile the speed of array_intersect with increasing amount of data to see how performance scale. You could do this by simply wrapping the call in calls for the system time and calculate the difference. But I would recommend you to use a real profiler to get good data.

Answer 5

I implementing this simple code of comparing array_intersect and array_intersect_key,

$array = array();
    for( $i=0; $i<130000; $i++)
        $array[$i] = $i;
    for( $i=200000; $i<230000; $i++)
        $array[$i] = $i;
    for( $i=300000; $i<340000; $i++)
        $array[$i] = $i;

    $array2 = array();
    for( $i=100000; $i<110000; $i++)
        $array2[$i] = $i;
    for( $i=90000; $i<100000; $i++)
        $array2[$i] = $i;
    for( $i=110000; $i<290000; $i++)
        $array2[$i] = $i;

    echo 'Intersect to arrays -> array1[' . count($array) . '] : array2[' . count($array2) . '] ' . '<br>';
    echo date('Y-m-d H:i:s') . '<br>';
    $time = time();
    $array_r2 = array_intersect_key($array,$array2);
    echo 'Intercept key: ' . (time()-$time) . ' segs<br>';
    $time = time();
    $array_r = array_intersect($array,$array2);
    echo 'Intercept: ' . (time()-$time) . ' segs<br>';

the result....

Intersect to arrays -> array1[200000] : array2[200000] 
2014-10-30 08:52:52
Intercept key: 0 segs
Intercept: 4 segs

In this comparing of the efficency between array_intersect and array_intersect_key, we can see the interception with keys it is much faster.