Re: Efficiency questions: combined ifs and looping 4 times
- From: Csaba Gabor <danswer@xxxxxxxxx>
- Date: Wed, 15 Apr 2009 04:29:46 -0700 (PDT)
On Apr 15, 12:44 am, Gordon <gordon.mc...@xxxxxxxxxxxx> wrote:
On Apr 14, 11:51 am, Csaba Gabor <dans...@xxxxxxxxx> wrote:....
I have a PHP Script which takes approximately 12 hours
to run on my Win XP Pro machine, spending the vast
majority of its time in the function below, to compute some
combinatorial properties, so I would like to squeeze
every bit of efficiency from it.
Respondents should probably know why ++$var (pre
increment and decrement) is more efficient than $var++
(post increment and decrement)
The kinds of optimizations you're talking about here are
microoptimizations, they'll buy you microseconds if anything at all.
Choice of algorithm always has a far bigger impact in performance than
any one implementation detail, unless you inadvertently pick an
implementation detail that happens to be very expensive. Other than
using sizeof () within a loop there's nothing that obviously jumps
out. Use sizeof () before the loop, store the result in a var and use
the var inside your loop instead.
The simple fact is, however, that the problem you've chosen to solve
is a computationally expensive one, the algorithm you've chosen to use
to solve said problem is brute-force, and you're doing it in an
interperated language which means you have the interperater's overhead
to take account of as well.
Thanks for your comments Iván and Gordon.
I agree with your comments Gordon, in particular that
the algorithm effects dominate, and any variations
in specific coding have not led to a measurable difference.
A note about sizeof(). sizeof()=count() is not
an inefficient function - the reason not to include it
in a loop is because of the overhead that it incurs as
a function call. Nevertheless, I recoded everything
so that the subarrays always toted around their size
(as their 0th element) and did not find any significant
time difference.
There's probably a better solution to this problem out
there, try googling for it.
Not likely, but I did try (though no doubt there are
faster implementations). In fact there is a reference
to what I was working on here:
http://www.research.att.com/~njas/sequences/A001214
Note that only 10 terms of the sequence are listed:
4, 10, 26, 44, 70, 108, 162, 228, 310, 422
the final term being added in 2006. That PHP only
bogs down at the 8th term (228) for me I thinks
speaks well of PHP.
It's clear that a compiled language will be faster
than an interpreted one, but PHP does pretty well
for itself, and development overhead is generally
far less.
Iván, your order of complexity analysis is off.
utilize() computes all possible 4-sums of a given
set, S, of n numbers. The maximum sum
can be 4*max(S). The algorithm works by first
taking one number, call it j=min(S), and
generating all 4-sums with that number (which
would be j, 2j, 3j, 4j). At each subsequent
step, it plops in the next number, k, and tries to
generate all 4-sums (from all the previous 4-sums)
which it would do by adding k, 2k, and 3k to each
of the existing sums. On any pass, this means at
most (3/4)max(S) entries to analyze. Since there
are n passes, this means that the complexity is
O(n*max(S)). The recursion is just the means to
the end and does not, of itself, represent
additional complexity. In addition, the
sizeof(...) does not affect the order of
complexity; at most it would be a constant factor.
The reason this bogs down is that it is getting
called repeatedly. In essence it's being called
with all sorts of variations of 8 numbers.
One thing I'd suggest right off is using a balanced
binary tree instead of an array. Trees tend to be
much faster than sequential data structures for
tasks like this, but implementing the
algorithm will be harder and require some thought.
I don't see that this problem is amenable to the
form that you are suggesting. In order for it to
be a workable idea, there has to be a way to combine
the subtree results, and these types of problems
(integer sums) are notorious for their intrasigence.
And PHP is quite simply the wrong language for this
job. PHP was intended to spit out web pages, not do
heavy duty mathematics. A compiled language like C
is bound to be faster simply because there's no
interperater overhead, at the very least you should
be using Java which is also going to be faster in
this application than PHP.
Yes, if I wanted to go further with this, then I'd
be obliged to switch. As it was, it was a diversion.
However, I did find a 25% speedup by realizing that
I was looping once too oft in the outer (now inner)
loop. I recoded it to be:
function utilize($strBoxes, $aRes = array()) {
// See thread start for doc:
// http://groups.google.com/group/comp.lang.php/browse_frm/thread/25d55fcda8bbdd5c/
$pos = strrpos(" $strBoxes", " ");
// Last number in $strBoxes,
// 0+ to avoid repeated coersion
$box = 0+substr($strBoxes,$pos);
// Everything but the last number:
$strRest = substr($strBoxes,0,--$pos<0 ? 0 : $pos);
if ($strRest) $aRes = utilize($strRest, $aRes);
$aRes[$box] = array($box);
foreach ($aRes as $amt => $aBox)
for ($i=0,$size = sizeof($aBox);++$i<=4-$size;) {
if (!$aRes[$amt+=$aBox[]=$box] ||
sizeof($aRes[$amt])>$size+$i)
$aRes[$amt] = $aBox;
else break; }
return $aRes; }
.
- References:
- Efficiency questions: combined ifs and looping 4 times
- From: Csaba Gabor
- Re: Efficiency questions: combined ifs and looping 4 times
- From: Gordon
- Efficiency questions: combined ifs and looping 4 times
- Prev by Date: Re: Best OpenSource PHP Editor and Debugger on Linux
- Next by Date: Error in exec function in php
- Previous by thread: Re: Efficiency questions: combined ifs and looping 4 times
- Next by thread: Re: Efficiency questions: combined ifs and looping 4 times
- Index(es):
Relevant Pages
|
Loading
