Home > Article > Web Front-end > From the perspective of data structure, for each in is much faster than for in_javascript skills
I heard that Firefox’s JS engine supports the for each in syntax, such as the following code:
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 an essential 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:
Using for...in to traverse Array is a very cumbersome process:
Every time arr[k] is accessed during traversal, a Hash(k) calculation must be performed. Modulo is taken based on the capacity of the hash table. If there is a conflict, the final value result must be found.
If the for each...in syntax is supported, its internal data structure determines that it will be much faster:
In Array, each value is directly used as a node and is maintained through linked lists. Whenever a value is added or deleted, its link relationship is updated.
When for each...in is traversed, it only needs to be iterated 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. ; and for each in directly feeds back the iteration variables from the bottom layer based on the internal linked list, saving the process of out-of-bounds checking.