php array_intersect() efficiency

by

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:

Performance of 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.

More Related Contents:

  1. Just using mysql real escape string [closed]
  2. Bug unserialize data PHP doesnt work
  3. URL rewriting with PHP
  4. Object of class mysqli_result could not be converted to string
  5. Why does PHP consider 0 to be equal to a string?
  6. Many-to-many relationships examples
  7. including a remote file in PHP
  8. On delete cascade with doctrine2
  9. php date validation
  10. How to alias a table in Laravel Eloquent queries (or using Query Builder)?
  11. Do login forms need tokens against CSRF attacks?
  12. Iterate over each line in a string in PHP
  13. Fastest way to add prefix to array keys?
  14. How to get int instead string from form?
  15. how to bind multiple parameters to MySQLi query [closed]
  16. mySQLi prepared statement unable to get_result()
  17. Check if specific input file is empty
  18. MySQL Performance – “IN” Clause vs. Equals (=) for a Single Value [duplicate]
  19. PHP: Split string into array, like explode with no delimiter
  20. MySQL skipping first row
  21. PHP: $_GET and $_POST in functions?
  22. Creating anonymous objects in php
  23. imagecreatefromjpeg and similar functions are not working in PHP
  24. Group array values based on key in php? [duplicate]
  25. Mailgun Sent mail With attachment
  26. Display Php Array result in an Html table
  27. How do you create a .gz file using PHP?
  28. How to check if a value already exists to avoid duplicates?
  29. PhpStorm 2020.2 – PHP Built-in functions are not recognized
  30. How do I apply URL normalization rules in PHP?

Leave a Comment