PHP Array_Intersect() Efficiency

php array_intersect() efficiency

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.

PHP: in_array() vs array_intersect() performance

Benchmark

Test Script

<?php
$numbers = range(32, 127);
$numbersLetters = array_map('chr', $numbers);

for (;;) {
    $numbersLetters = array_merge($numbersLetters, $numbersLetters);

    if (count($numbersLetters) > 10000) {
        break;
    }
}

$numbers = range(1, count($numbersLetters));

printf("Sample size: %d elements in 2 arrays (%d total) \n", count($numbers), count($numbers) + count($numbersLetters));
printf("Benchmarking speed in foreach + in_array() scenario... (this might take a while) ");

shuffle($numbers);
shuffle($numbersLetters);

$t1 = microtime(true);

foreach ($numbers as $number) {
    if (in_array($number, $numbersLetters)) {}
}

$t2 = microtime(true);

printf("DONE!\n");
printf("Time elapsed: %.5f \n", $t2 - $t1);

// =============================------------===============================

printf("Benchmarking speed with array_intersect...");

shuffle($numbers);
shuffle($numbersLetters);

$t1 = microtime(true);

array_intersect($numbers, $numbersLetters);

$t2 = microtime(true);

printf("DONE!\n");
printf("Time elapsed: %.5f \n", $t2 - $t1);

Output

Sample size: 12288 elements in 2 arrays (24576 total) 
Benchmarking speed in foreach + in_array() scenario... (this might take a while) DONE!
Time elapsed: 3.79213 
Benchmarking speed with array_intersect...DONE!
Time elapsed: 0.05765 

Fiddle: http://ideone.com/OZ2Idf

Conclusion

array_intersect is much faster than foreach + in_array.

Why is array_intersect faster?

• The intersection is computed in C code, as opposed to PHP
• Internally, Zend engine sorts the array prior to computing the intersection (why is processing a sorted array faster?)

Which is more efficent PHP: array_intersect() OR array_intersect_key()

From another post: I have two unordered integer arrays, and i need to know how many integers these arrays have in common

Depending on your data (size) you
might want to use
array_intersect_key() instead of
array_intersect(). Apparently the
implementation of array_intersect
(testing php 5.3) does not use any
optimization/caching/whatsoever but
loops through the array and compares
the values one by one for each element
in array A. The hashtable lookup is
incredibly faster than that.

PHP : Obtain common values in 2 huge arrays

Result based on my own test, array_intersect() is the choice. It can produce the result in less than 1 second, as its efficiency is O(n·log n).

Reference: https://stackoverflow.com/a/6329494/188331

PHP array_intersect() - how does it handle different types?

$ cat > test.php

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

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

print_r($intersect );

?>

$ php test.php

Array
(
)

$

So no, it will not. But if you add

foreach($arrayOne as $key => $value)
{
   $arrayOne[$key] = intval($value);
}

you will get

$ php test.php

Array
(
[1] => 4
[2] => 5
)

PHP array_intersect() till the first match

How about this?

foreach ($arr1 as $key => $val) {
    if (in_array($val, $arr2)){
        // do something, maybe return so you wouldn't need break
        break;
    }
}

How to match array_intersect() values to corresponding key in another array?

Combine the two arrays from the database into an associative array. Then use the user input to select only a subset of keys.

$filteredData = array_intersect_key(
    array_combine($result, $reference), 
    array_flip($inputValue)
);

---

Related Topics