AMC Registration in 24 days
Mon December 15, 2008

Suffolk County Math Tournament in 49 days
Fri January 9, 2009

PUMaC in 71 days
Sat January 31, 2009

AMC 12A in 81 days
Tue February 10, 2009

HMMT in 92 days
Sat February 21, 2009

World Math Day in 103 days
Wed March 4, 2009

AIME I in 129 days
Mon March 30, 2009

PLUS! magazine deadline in 130 days
Tue March 31, 2009

USAMO in 158 days
Tue April 28, 2009

ARML in 189 days
Fri May 29, 2009

21st Birthday in 660 days
Sun September 12, 2010

Turning 40 in 7600 days
Wed September 12, 2029

tags in Topics

more tags

Feeds

Navigation

Links

If you liked this post, buy me a beer... I mean cookie.

Array_shift() is slower than I thought

Posted May 11th, 2007 by Mgccl

in

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 script 1, 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.

Bookmark/Search this post with:

"I can't think of any time

On May/12/2007 04:44:16 Jeff Standen (not verified) says:

"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

reply

I would try to create some

On May/12/2007 11:50:35 Mgccl says:

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.

reply

Prime Spiral Correction

On Nov/01/2008 17:32:52 Howting (not verified) says:

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){

reply

Cool thx, I just fixed it

On Nov/01/2008 19:01:44 Mgccl says:

Cool thx, I just fixed it

reply

And... one more little thing.

On Nov/01/2008 21:16:12 Howting (not verified) says:

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.

$size  = 500;
$x_adj = ~ $size & 1;

Then, apply that factor to shift the "prime pixels" to the left.

imagesetpixel($image,$x+$size2-$x_adj,$y+$size2,$color);

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.

reply

haha, thx. It would be even

On Nov/01/2008 22:59:48 Mgccl says:

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.

reply

All together now...

On Nov/02/2008 17:00:03 Howting (not verified) says:

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=160

I 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.