Databases
StackOverflow2013
Postsdbo
POList of Big-O for PHP functions
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POList of Big-O for PHP functions
    text
    copied!<p>After using PHP for a while now, I've noticed that not all PHP built in functions as fast as expected. Consider the below two possible implementations of a function that finds if a number is prime using a cached array of primes.</p> <pre><code>//very slow for large $prime_array $prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... ); $result_array = array(); foreach( $prime_array =&gt; $number ) { $result_array[$number] = in_array( $number, $large_prime_array ); } //speed is much less dependent on size of $prime_array, and runs much faster. $prime_array =&gt; array( 2 =&gt; NULL, 3 =&gt; NULL, 5 =&gt; NULL, 7 =&gt; NULL, 11 =&gt; NULL, 13 =&gt; NULL, .... 104729 =&gt; NULL, ... ); foreach( $prime_array =&gt; $number ) { $result_array[$number] = array_key_exists( $number, $large_prime_array ); } </code></pre> <p>This is because in_array is implemented with a linear search O(n) which will linearly slow down as <code>$prime_array</code> grows. Where the <code>array_key_exists</code> function is implemented with a hash lookup O(1) which will not slow down unless the hash table gets extremely populated (in which case it's only O(n)).</p> <p>So far I've had to discover the big-O's via trial and error, and occasionally <a href="https://stackoverflow.com/questions/2350361/how-is-the-php-array-implemented-on-the-c-level">looking at the source code</a>. Now for the question...</p> <p><strong>Is there was a list of the theoretical (or practical) big O times for all* the PHP built in functions?</strong></p> <p>*or at least the interesting ones</p> <p>For example find it very hard to predict what the big O of functions listed because the possible implementation depends on unknown core data structures of PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace (with array inputs), etc.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload