Are loops really faster in reverse?
I've heard this quite a few times. Are JavaScript loops really faster when counting backward? If so, why? I've seen a few test suite examples showing that reversed loops are quicker, but I can't find any explanation as to why!
I'm assuming it's because the loop no longer has to evaluate a property each time it checks to see if it's finished and it just checks against the final numeric value.
Ie
for (var i = count - 1; i >= 0; i--)
{
// count is only evaluated once and then the comparison is always on 0.
}
It's not that i-- is faster than i++ . Actually, they're both equally fast.
What takes time in ascending loops is evaluating, for each i , the size of your array. In this loop:
for(var i = array.length; i--;)
You evaluate .length only once, when you declare i , whereas for this loop
for(var i = 1; i <= array.length; i++)
you evaluate .length each time you increment i , when you check if i <= array.length .
In most cases you shouldn't even worry about this kind of optimization .
This guy compared a lot of loops in javascript, in a lot of browsers. He also has a test suite so you can run them yourself.
In all cases (unless I missed one in my read) the fastest loop was:
var i = arr.length; //or 10
while(i--)
{
//...
}
I try to give a broad picture with this answer.
The following thoughts in brackets was my belief until I have just recently tested the issue:
[[In terms of low level languages like C/C++, the code is compiled so that the processor has a special conditional jump command when a variable is zero (or non-zero).
Also, if you care about this much optimization, you could go ++i instead of i++ , because ++i is a single processor command whereas i++ means j=i+1, i=j .]]
Really fast loops can be done by unrolling them:
for(i=800000;i>0;--i)
do_it(i);
It can be way slower than
for(i=800000;i>0;i-=8)
{
do_it(i); do_it(i-1); do_it(i-2); ... do_it(i-7);
}
but the reasons for this can be quite complicated (just to mention, there are the issues of processor command preprocessing and cache handling in the game).
In terms of high level languages , like JavaScript as you asked, you can optimize things if you rely on libraries, built-in functions for looping. Let them decide how it is best done.
Consequently, in JavaScript, I would suggest using something like
array.forEach(function(i) {
do_it(i);
});
It is also less error-prone and browsers have a chance to optimize your code.
[REMARK: not only the browsers, but you too have a space to optimize easily, just redefine the forEach function (browser dependently) so that it uses the latest best trickery! :) @AMK says in special cases it is worth rather using array.pop or array.shift . If you do that, put it behind the curtain. The utmost overkill is to add options to forEach to select the looping algorithm.]
Moreover, also for low level languages, the best practice is to use some smart library function for complex, looped operations if it is possible.
Those libraries can also put things (multi-threaded) behind your back and also specialized programmers keep them up-to-date.
I did a bit more scrutiny and it turns out that in C/C++, even for 5e9 = (50,000x100,000) operations, there is no difference between going up and down if the testing is done against a constant like @alestanis says. (JsPerf results are sometimes inconsistent but by and large say the same: you can't make a big difference.)
So --i happens to be rather a "posh" thing. It only makes you look like a better programmer. :)
On the other hand, for-unrolling in this 5e9 situation, it has brought me down from 12 sec to 2.5 sec when I went by 10s, and to 2.1 sec when I went by 20s. It was without optimization, and optimization has brought things down to unmeasureable little time. :) (Unrolling can be done in my way above or using i++ , but that does not bring things ahead in JavaScript. )
All in all: keep i-- / i++ and ++i / i++ differences to the job interviews, stick to array.forEach or other complex library functions when available. ;)
上一篇: 确定整数的平方根是否为整数的最快方法
下一篇: 循环是否真的更快？