note 64973 deleted from language.types.array by bjori
| From: | bjori@php.net | Date: | Mon, 24 Apr 2006 06:18:55 +0000 |
| Subject: | note 64973 deleted from language.types.array by bjori | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-109289@lists.php.net to get a copy of this message | ||
Note Submitter: mumyachan at yahoo dot co dot jp
Reason: useless
----
Sophisticated codes have their own cost, the setback in speed.
Suppose you want to find primes to a certain number (10000 in the example below) you just look up
whether each number is divisible by the primes up to (the floor of) the square root of the number,
and examining (if the number is divisible by) all integers from 2 (to the floor of square root of
the number) seems to be a mere wast of time. (Once some number can not be divided by 2, it surely
can not be divided by 4, for example)
So, experienced programmers or mathematicians would code something like:
<?php
$n=10000;
$prime=array(2);
for($i=3;$i<$n;$i++)
{
$uint=sqrt($i);
foreach($prime as $p)
{
if($p>$uint)
{
$prime[]=$i;
break;
}
if($i%$p==0)
break;
}
}
foreach($prime as $p)
echo $p." ";
}
?>
This takes about .87 seconds at my machine.
While the seemingly 'stupid' version of this, looking up every interger up to the floor of
the square root of each number is coded something like:
<?php
$n=10000;
$prime=array(2,3);
for($i=5;$i<$n;$i++)
{
$uint=floor(sqrt($i));
for($j=2;$j<=$uint;$j++)
{
if($i%$j==0)
break;
if($j==$uint)
$prime[]=$i;
}
}
foreach($prime as $p)
echo $p." ";
?>
This takes .08 seconds. Ten times faster than the more sophiscated code!
Bear in mind array manipulation takes much longer than we imagine.
(The use of array for writing down all of them at the end of the program doesn't harm. I also
tried to write down each prime immediately after it is found, it made little difference)