tags in Topics
Feeds
Navigation
Most Popular
- (Simple version)Matrix like animated dropping character effect in PHP
- Wordpress and phpbb seems like the center of spambot's attention
- Multiracial are superior
- F-U-C-K YOU CHINA
- phpBB--the world's most popular Bulletin board system
- How to win a jelly bean counting contest
- Guest Book
- A mathematical look into study = fail
- Believe in coke
- About
Misc
Array_shift() is slower than I thought
Fri, 05/11/2007 - 22:59 | by Mgccl
to
The 2000*2000 prime spiral is generated in 12 seconds!
This script will make everything more clear:
If you remember my prime spiral generator, you would remember it cost over 1 hour to generate a 2000*2000 prime spiral.
But after I did the simple diffusion limited aggregation script1, prime spirals' speed seems impossibly long.
Thx to Edd for pointing out array_shift() is über slow, after I slightly changed the code from
while($n<=$size){ if($prime[0]<=$sn){ $p = array_shift($prime);
to
$i = 0; while($n<=$size){ if($prime[$i]<=$sn){ $p = $prime[$i++];
The 2000*2000 prime spiral is generated in 12 seconds!
This script will make everything more clear:
$array= range(1,10000); $timeparts = explode(' ',microtime()); $starttime = $timeparts[1].substr($timeparts[0],1); while($i<10000){ $array[$i]; ++$i; } $timeparts = explode(' ',microtime()); $endtime = $timeparts[1].substr($timeparts[0],1); echo 'Native array loop:',bcsub($endtime,$starttime,6),'<br />'; $timeparts = explode(' ',microtime()); $starttime = $timeparts[1].substr($timeparts[0],1); $i= 0; while($i<10000){ array_shift($array); ++$i; } $timeparts = explode(' ',microtime()); $endtime = $timeparts[1].substr($timeparts[0],1); echo 'array_shift():',bcsub($endtime,$starttime,6);
The result:
Native array loop:0.003198 array_shift():2.128530
The native loop is over 650 times faster, don't you think it's too much? What could possibly turn array_shift so inefficient? array_splice($array,0,1) is 7 times slower than array_shift(). 
So, don't use those functions unless you absolutely have to2.
- 1. in theory, much slower than prime spiral
- 2. I can't think of any time that you need to use array_shift(). Because it can always be simulated by a native array loop.
M: 13.9865264893MB, T: 0.305600166321s, QC: 158, QT: 0.123905420303s, RT: 0.181694746017s
.
Comments
"I can't think of any time
"I can't think of any time that you need to use array_shift(). Because it can always be simulated by a native array loop."
Well,
When you aren't doing 10,000 iterations, and you simply need to implement a queue or stack, then array_shift() and array_pop() are genuinely useful and fairly inexpensive.
The real food for thought here, to myself anyway, is always considering PHP is a high level language when doing short, highly-repetitious algorithms. Even though array_shift() is one function call to you, there is a lot of re-hash work going on in the C source code to re-dimension an array. It's important to consider when you actually need to re-dimension the array versus just reading it as a buffer and then clearing it a single time.
-Jeff
I would try to create some
I would try to create some faster queue or stack that don't use array_shift() and array_pop(). it's possible to use more memory in return for the benefit of faster speed. If I just keep track of the array's pointer, each time adding something new to the array, the pointer changes. So when something is taken out, it only changes the pointer.
Prime Spiral Correction
The speedy new code fails to highlight primes on the last two sides (when $n==$size). These changes will remedy this. An out of range value is appended to the $prime array to force an exit upon completion.
Change these lines...
$i = 0; while($n<$size){...to this...
$prime[] = $size * $size +1; $i = 0; while($n<=$size){Cool thx, I just fixed it
Cool thx, I just fixed it
And... one more little thing.
I was sloppy in my testing (mea culpa). The above fix works fine if $size is an odd integer.
If $size is even, then the "prime pixels" are shifted one column to the right. The result is an empty far left column and a far right column which is beyond the bounds of the image.
The remedy is pretty simple. A bitwise parity check is used to determine odd or even.
Calculate an adjustment factor of 1 if $size is even or 0 if odd.
Then, apply that factor to shift the "prime pixels" to the left.
Not particularly elegant fixes. But, they have a negligible impact on performance and add just two lines.
BTW... A HUGE success from Mgccl the great indeed. The dang thing is just flat fast. I'm looking forward to the rest of the site.
haha, thx. It would be even
haha, thx.
It would be even faster if it's done with C.
There might be even faster ways to do it, I just don't have time to look into it these days.
Have fun looking around my website.
All together now...
For my purposes, I pulled together the pieces of your code and did some optimizing. It will return an irregular rectangle based on 'height' and 'width' in the query string. For example:
http://www.tahoeweb.com/ulam.php?height=120&width=160I didn't want to post 100+ lines of code here, so you can nab the source here. Ulam Spiral PHP Source Code
Since it's mostly your work anyway, feel free to use as you choose :-).
Enjoy.
Post new comment