Archive - May 11, 2007

Date

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 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. 1. in theory, much slower than prime spiral
  2. 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.

Simple diffusion limited aggregation image PHP

Posted May 11th, 2007 by Mgccl
in

Diffusion-Limited Aggregation creates great looking fractals, I made a fast(but not the fastest) Diffusion-Limited Aggregation simulator. You define how many molecules will be released and the size of the board. A more accurate Brownian motion system will make the image look better, but it is going to be a lot slower.
Don't assign numbers larger than 700 for step, it is going to consume a huge amount of time to generate. A size 100 step 700 image cost around 60 seconds.
A faster version can be implemented by change the random movement of molecules into linear movement.
Diffusion-Limited Aggregation Simulation result

	set_time_limit(0);
	//Very fast Diffusion-Limited Aggregation
 
 
$s = 100;
$step = 700;
$area = 2;//smaller = faster, larger = more accurate(random)
 
$image = imagecreate($s,$s);
imagecolorallocate($image,255,255,255);
$color = imagecolorallocate($image,0,0,0);
$s2 = $s/2;
$grid[$s2][$s2] = 1;
imagesetpixel($image,$s2,$s2,$color);
 
while($i<$step){
	//calculate releasing area
	$n = max($max_x - $min_x, $max_y - $min_y) + $area;
	$s2mn = $s2-$n;
	$s2an = $s2+$n;
	//release a molecule
	do{
		$x = rand($s2mn,$s2an);
		$y = rand($s2mn,$s2an);
	}while($grid[$x][$y]);
	//move the molecule randomly
while(!($grid[$x-1][$y-1]+$grid[$x-1][$y]+$grid[$x-1][$y+1]+
$grid[$x][$y-1]+$grid[$x][$y+1]+$grid[$x+1][$y-1]+
$grid[$x+1][$y]+$grid[$x+1][$y+1])){
		$x += rand(-1,1);
		$y += rand(-1,1);
		if($x<$s2mn||$x>$s2an||$y<$s2mn||$y>$s2an){
			continue 2;
		}
	}
	$grid[$x][$y] = 1;
	if($max_x<$x){
		$max_x = $x;
	}elseif($min_x>$x){
		$min_x = $x;
	}
	if($max_y<$y){
		$max_y = $y;
	}elseif($min_y>$y){
		$min_y = $y;
	}
	imagesetpixel($image,$x,$y,$color);
 
++$i;
}
 
	header("Content-type: image/png");
	imagepng($image);

Note for May 11

Posted May 11th, 2007 by Mgccl
in

If I'm a psychic, then I can cheat on any test I want without been find out.

Sneeze morse code.... yeeeah.... Practicing for the AP bio test..
AP bio killed my family, I'm going to make it pay.

AP bio test is going to be loads with metaphor and symbolism, how can the graders give me a 0 when I made them cry.

"When the task is to write one of the 2 subject, only write one. If you write 2, no matter how fabulous the 2nd one is, no one is going to grade it"
"Because the graders are not gay..."

Honey Pot that kill bots