Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is using a loop to iterate from start of array to end faster than iterating both start to end and end to start?

Tags:

Given an array having .length 100 containing elements having values 0 to 99 at the respective indexes, where the requirement is to find element of of array equal to n : 51.

Why is using a loop to iterate from start of array to end faster than iterating both start to end and end to start?

const arr = Array.from({length: 100}, (_, i) => i);  const n = 51;  const len = arr.length;    console.time("iterate from start");  for (let i = 0; i < len; i++) {    if (arr[i] === n) break;  }  console.timeEnd("iterate from start");

const arr = Array.from({length: 100}, (_, i) => i);  const n = 51;  const len = arr.length;    console.time("iterate from start and end");  for (let i = 0, k = len - 1; i < len && k >= 0; i++, k--) {    if (arr[i] === n || arr[k] === n) break;  }  console.timeEnd("iterate from start and end");

jsperf https://jsperf.com/iterate-from-start-iterate-from-start-and-end/1

like image 378
guest271314 Avatar asked Nov 01 '17 05:11

guest271314


People also ask

What type of loop would be best for iterating over an array?

The for loop is probably the most common and well known type of loop in any programming language. For can be used to iterate through the elements of an array: For can also be used to perform a fixed number of iterations: By default the increment is one.

Why for loop is faster than forEach?

Deductions. This foreach loop is faster because the local variable that stores the value of the element in the array is faster to access than an element in the array. The forloop is faster than the foreach loop if the array must only be accessed once per iteration.

Why for loop is faster than forEach in JavaScript?

ForEach is 96% slower than for loop. Thanks in advance. It's probably because forEach requires a function call for each element. That doesn't quite explain why it's 96% faster though, you'd expect 50% since you make 1 function call instead of 2 for each element.

Which is faster method to traverse an array?

In case of multiple iterations of the loop, and where the size of array is too large, for loop is the preference as the fastest method of elements' iteration. While loops perform efficient scaling in case of large arrays. In case of functional codes, for each loop performs better with a much optimized time.


1 Answers

The answer is pretty obvious:

More operations take more time.

When judging the speed of code, you look at how many operations it will perform. Just step through and count them. Every instruction will take one or more CPU cycles, and the more there are the longer it will take to run. That different instructions take a different amount of cycles mostly does not matter - while an array lookup might be more costly than integer arithmetic, both of them basically take constant time and if there are too many, it dominates the cost of our algorithm.

In your example, there are few different types of operations that you might want to count individually:

  • comparisons
  • increments/decrements
  • array lookup
  • conditional jumps

(we could be more granular, such as counting variable fetch and store operations, but those hardly matter - everything is in registers anyway - and their number basically is linear to the others).

Now both of your codes iterate about 50 times - they element on which they break the loop is in the middle of the array. Ignoring off-by-a-few errors, those are the counts:

               |  forwards  | forwards and backwards ---------------+------------+------------------------ >=/===/<       |       100  |                   200 ++/--          |        50  |                   100 a[b]           |        50  |                   100 &&/||/if/for   |       100  |                   200 

Given that, it's not unexpected that doing twice the works takes considerably longer.

I'll also answer a few questions from your comments:

Is additional time needed for the second object lookup?

Yes, every individual lookup counts. It's not like they could be performed at once, or optimised into a single lookup (imaginable if they had looked up the same index).

Should there be two separate loops for each start to end and end to start?

Doesn't matter for the number of operations, just for their order.

Or, put differently still, what is the fastest approach to find an element in an array?

There is no "fastest" regarding the order, if you don't know where the element is (and they are evenly distributed) you have to try every index. Any order - even random ones - would work the same. Notice however that your code is strictly worse, as it looks at each index twice when the element is not found - it does not stop in the middle.

But still, there are a few different approaches at micro-optimising such a loop - check these benchmarks.

  • let is (still?) slower than var, see Why is using `let` inside a `for` loop so slow on Chrome? and Why is let slower than var in a for loop in nodejs?. This tear-up and tear-down (about 50 times) of the loop body scope in fact does dominate your runtime - that's why your inefficient code isn't completely twice as slow.
  • comparing against 0 is marginally faster than comparing against the length, which puts looping backwards at an advantage. See Why is iterating through an array backwards faster then forwards, JavaScript loop performance - Why is to decrement the iterator toward 0 faster than incrementing and Are loops really faster in reverse?
  • in general, see What's the fastest way to loop through an array in JavaScript?: it changes from engine update to engine update. Don't do anything weird, write idiomatic code, that's what will get optimised better.
like image 131
Bergi Avatar answered Sep 18 '22 11:09

Bergi