From the data structure analysis: using for each...in is faster than for...in

From the data structure analysis: using for each...in is faster than for...in_Basic knowledge

WBOY

Release： 2016-05-16 17:36:51

Original

922 people have browsed it

I heard that Firefox’s JS engine supports the for each in syntax, such as the following code:

Copy code The code is as follows:

var arr = [10,20,30,40,50];
for each(var k in arr)
 console.log(k); 

can directly traverse the contents of the arr array.

Since only FireFox supports it, almost all JS code does not use this feature.

However, ActionScript inherently supports the for each syntax. Regardless of Array, Vector, or Dictionary, as long as it is an enumerable object, it can be for in and for each in.

I didn’t feel there was much difference before. In order to be too lazy to type the word "each", I always used the familiar for in to traverse.

But after thinking about it carefully today and analyzing it from the perspective of data structure, I feel that there is a fundamental difference in efficiency between for in and for each in, whether it is JS or AS.

The reason is simple: Array is not an array in the true sense!

What is the true meaning of an array? Of course, it is the data type defined by type[] in traditional languages, and all elements are saved continuously.

Although "Array" also means array, those familiar with JS know that it is actually a non-linear pseudo-array, and the subscript can be any number. Writing arr[1000000] does not actually apply for space to accommodate one million elements, but converts 1000000 into the corresponding hash value, which corresponds to a small storage space, thus saving a lot of memory.

For example, there is the following array:

Copy code The code is as follows:

var arr = [ ];
 arr[10] = 1000;
 arr[20] = 2000;
 arr[30] = 5000;
 arr[40] = 8000;
 arr[200] = 9000;

Using for...in to traverse Array is a very cumbersome process:

Every time arr[k] is accessed during traversal, a Hash(k) calculation is performed, modulo is taken according to the capacity of the hash table, and the result is finally found in the conflict linked list.

If the for each...in syntax is supported, its internal data structure determines that it will be much faster:

Array stores a list of keys, and also associates each value as a linked list. Whenever a value is added or deleted, its link relationship is updated.

When for each...in is traversed, it only needs to iterate from the first node backwards without any Hash calculation.

Of course, for linear arrays such as Vector in AS3, there is not much difference between the two; similarly, the same is true for the binary array ArrayBuffer in HTML5. However, from a theoretical point of view, even if arr is a continuous linear array, for each in is still faster:

When traversing for...in, every time arr[k] is accessed, a subscript out-of-bounds check must be performed; while for each in, the iteration variable is directly fed back from the bottom layer based on the internal linked list, saving the process of out-of-bounds checking.