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.