It seems that there has always been a misunderstanding in the front-end circle: the front-end cannot use algorithm knowledge. For a long time, everyone may have been influenced by this statement. Until I encountered a product demand a while ago, I looked back and found that this was not the case.
Front-end sorting
Front-end sorting scenario
The front-end passes the sorting condition to the back-end as a request parameter, and the back-end returns the sorting result as a request response to the front-end, which is a common design. But it is not that suitable for some products.
Imagine a scenario: When you use a food app, do you often switch the sorting method, sort it by price, and then sort by rating.
In actual production, due to factors such as server cost, when a single data query becomes an overall performance bottleneck, it is also considered to optimize performance by sorting it in the front-end.
Sorting algorithm
I feel that there is no need to introduce this. As a basic algorithm in computer science, the description will be copied directly from Wikipedia .
This paragraph exists here purely for the purpose of inheriting the first (man) and the second (shu).
JavaScript sorting
Since we talk about front-end sorting, we will naturally think of JavaScript's native interface Array.prototype.sort .
This interface has existed since ECMAScript 1st Edition . Let's see what the description of it looks like in the latest specification.
Array.prototype.sort specification
Array.prototype.sort(compareFn)
The code copy is as follows:
The elements of this array are sorted. The sort is not necessary stable (that is, elements that compare equal do not necessarily remain in their original order). If compared is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.
Obviously, the specification does not limit what the sort algorithm implemented internally is. Even the implementation of the interface does not need to be stable sorted . This is very important and will be involved many times next.
In this context, the front-end sorting actually depends on the specific implementation of each browser. So, how do mainstream browsers implement sorting? Next, we briefly compare Chrome , Firefox and Microsoft Edge respectively.
Implementation in Chrome
Chrome's JavaScript engine is v8. Since it is open source, you can look at the source code directly.
The entire array.js is implemented in the JavaScript language. The sorting method part is obviously much more complicated than the quick sort I have seen, but obviously the core algorithm is still quick sorting. The reason for the complex algorithm is that v8 has made many optimizations for performance considerations. (I'll talk about it next)
Implementation in Firefox
It is not possible to determine what the array sorting algorithm that Firefox's JavaScript engine will be about to use. [3]
According to the existing information, SpiderMoney implements merge sorting internally.
Implementation in Microsoft Edge
The core part of the code for the JavaScript engine Chakra of Microsoft Edge was opened sourced on Github in early 2016.
By looking at the source code, we can find that Chakra's array sorting algorithm also implements quick sorting. And compared to v8, it only implements purely quick sorting, with no trace of performance optimizations in v8 at all.
Problems with JavaScript array sorting
As we all know, quick sorting is an unstable sorting algorithm, while merge sorting is a stable sorting algorithm. Due to the differences in algorithm selection of different engines, the front-end relies on the JavaScript code implemented by the Array.prototype.sort interface, and the actual sorting effect performed in the browser is inconsistent.
Differences in sort stability need to be triggered by specific scenarios before there is a problem; in many cases, unstable sorting will not have any impact.
If there is no need for stability in the sorting of arrays in actual project development, then you can actually see this, and the implementation differences between browsers are not that important.
But if the project requires that the sort must be stable, then the existence of these differences will not meet the demand. We need to do some extra work for this.
For example:
The final winning rules for the motor vehicle license auction system in a certain city are:
1. Sort by price in reverse;
2. The same price will be positively sorted according to the bidding order (i.e. the price submission time).
If sorting is done on the front end, the winner displayed in the browser using quick sort is likely to be inconsistent with expectations.
Explore the differences
Before finding a solution, it is necessary to explore the reasons for the problem.
Why Chrome uses quick sorting
In fact, this situation existed from the beginning.
Chrome beta was released on September 2, 2008. However, shortly after its release, some developers submitted #90 bug feedback to the Chromium development group. The array sorting implementation of v8 is not stable.
This bug ISSUE discussion spans a lot. Until November 10, 2015, developers still commented on the implementation of array sorting in v8.
At the same time, we also noticed that the ISSUE has been closed. However, it was reopened by development team members in June 2013 as a reference for discussion of the ECMAScript Next specification.
And the final conclusion of es-discuss is
The code copy is as follows:
It does not change. Stable is a subset of unstable. And vice versa, every unstable algorithm returns a stable result for some inputs. Mark's point is that requiring “always unstable” has no meaning, no matter what language you choose.
/Andreas
As described in the finalized ECMAScript 2015 specification cited earlier in this article.
Characteristics of the times
IMHO, this problem was reported at the beginning of Chrome's release, which may have its own special characteristics of the times.
As mentioned above, the first version of Chrome was released in September 2008. According to statistics from statcounter, the two browsers with the highest market share during that period were IE (only IE6 and IE7 at that time) and Firefox, with market share reaching 67.16% and 25.77% respectively. In other words, the combined market share of the two browsers exceeds 90%.
According to another browser sorting algorithm statistics, these two browsers with more than 90% market share adopt stable array sorting. Therefore, it is reasonable to be questioned by developers at the beginning of Chrome's release.
Comply with the specifications
From the Bug ISSUE discussion, we can roughly understand some considerations of development team members in using quick sorting of engine implementation.
One of these is that they believe that the engine must comply with the ECMAScript specification. Since the specification does not require a description of stable sorting, they believe that the implementation of v8 is fully in line with the specification.
Performance considerations
In addition, they believe that an important consideration in v8 design is the performance of the engine.
Quick sorting performs better overall performance than merge sorting:
Higher computing efficiency. Quick sorting is faster in an actual computer execution environment than other sorting algorithms with the same time complexity (in case of not hitting the worst combination)
Lower space costs. The former has only O(n) space complexity, compared with the latter O(n) space complexity, the memory consumption is less during runtime.
Performance optimization of v8 in array sorting algorithm
Since v8 is very interested in engine performance, what does it do in array sorting?
By reading the source code, I still learned some basic knowledge.
Mixed Insert Sort
Quick sorting is the idea of dividing and conquering, decomposing large arrays and recursing them down layer by layer. However, if the recursion depth is too large, the memory resource consumption of the recursive call stack will also be very large. Poor optimization may even cause stack overflow.
The current implementation of v8 is to set a threshold and use insert sorting for small arrays of 10 or less lengths in the lowest layer.
According to code comments and descriptions in Wikipedia, although the average time complexity of insertion sort is O(n²) is worse than that of quick sort O(nn). However, in the running environment, the efficiency of using insert sorting of small arrays is more efficient than fast sorting, so it will not be expanded here.
v8 code example
var QuickSort = function QuickSort(a, from, to) { ...... while (true) { // Insertion sort is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; } ...... } ......};Three numbers are in
As is known, the quick sorting Achilles heel is that the algorithm degenerates in the worst array combination.
The core of the quick sorting algorithm is to select a pivot, and decompose the array that has been compared and exchanged into two number areas according to the reference for subsequent recursion. Imagine if, for an already ordered array, the first or last element is always selected every time the reference element is selected, then there will be a number area that is empty every time, and the recursive number of layers will reach n, which will eventually lead to the algorithm's time complexity degradation to O(n²). Therefore, the choice of pivot is very important.
v8 uses the optimization of median-of-three : in addition to the two elements at the beginning and end, another element is selected to participate in the competition of the benchmark element.
The selection strategy for the third element is roughly:
When the length of the array is less than or equal to 1000, select the element at the half position as the target element.
When the length of the array exceeds 1000, select one element at a distance of 200-215 (non-fixed, changing with the length of the array) to determine a batch of candidate elements first. Then sort the candidate elements in this batch, and use the resulting median value as the target element.
Finally, take the median value of the three elements as pivot.
v8 code example
var GetThirdIndex = function(a, from, to) { var t_array = new InternalArray(); // Use both 'from' and 'to' to determine the pivot candidates. var increment = 200 + ((to - from) & 15); var j = 0; from += 1; to -= 1; for (var i = from; i < to; i += increment) { t_array[j] = [i, a[i]]; j++; } t_array.sort(function(a, b) { return comparefn(a[1], b[1]); }); var third_index = t_array[t_array.length >> 1][0]; return third_index;};var QuickSort = function QuickSort(a, from, to) { ...... while (true) { ...... if (to - from > 1000) { third_index = GetThirdIndex(a, from, to); } else { third_index = from + ((to - from) >> 1); } } ......};Sort in place
While reviewing the quick sorting algorithm, I saw many examples of implementation using JavaScript on the Internet.
But I found that a large part of the code implementation is as follows
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right));};The main problem with the above code is: using the two number areas left and right to store recursive subarrays, so it requires additional storage space of O(n). This is a big difference compared to the theoretical average spatial complexity O(n).
The additional space overhead will also affect the overall speed of the actual runtime. This is also one of the reasons why fast sorting can perform at actual runtimes beyond the same level of time complexity. Therefore, generally speaking, fast sorting with better performance will adopt in-place sorting.
The implementation in v8 source code is to exchange elements on the original array.
Why Firefox uses merge sorting
There is also a story behind it.
In fact, when Firefox was released at the beginning, it did not use a stable sorting algorithm to implement array sorting, which is well documented.
The array sorting algorithm implemented by the original version of Firefox (Firebird) was heap sorting, which is also an unstable sorting algorithm. Therefore, someone later submitted a bug.
The Mozilla development team has conducted a series of discussions on this issue.
From the discussion process, we can draw some points
1. Mozilla's competitor during the same period was IE6. From the statistics above, we can see that IE6 is stable in sorting.
2.Brendan Eich, the father of JavaScript, thinks Stability is good
3. Firefox uses quick sorting before heap sorting
Based on the main premise that development group members tend to implement stable sorting algorithms, Firefox3 takes merge sorting as a new implementation of array sorting.
Solve the differences in sorting stability
I have said so much above mainly to tell the differences in the sorting implementation of each browser, and to explain some of the more superficial reasons why these differences exist.
But after reading this, readers may still have questions: what should I do if my project just needs to rely on stable sorting?
Solution
In fact, the idea of solving this problem is relatively simple.
The browser chooses different sorting algorithms for different considerations. Some may tend to pursue extreme performance, while others tend to provide a good development experience, but there are rules to follow.
Judging from the current known situation, all mainstream browsers (including IE6, 7, 8) can basically enumerate the implementation of array sorting algorithms:
1. Merge sorting/Timsort
2. Quick sort
So, we can just transform the quick sorting into a stable sorting?
Generally speaking, using unstable sorting for object arrays will affect the results. While other types of arrays themselves use stable or unstable sorting results are equal. Therefore, the plan is roughly as follows:
Preprocess the array to be sorted and add natural order attributes to each object to be sorted, so as not to conflict with other attributes of the object.
Custom sorting comparison method compareFn always uses natural order as the second judgment dimension when pre-judgment is equal.
When facing implementations such as merge sorting, since the algorithm itself is stable, the additional natural order comparison will not change the sorting result, so the scheme compatibility is better.
However, it involves modifying the array to be sorted, and additional space is needed to store natural order properties. It is conceivable that engines like v8 should not use similar methods. However, it is feasible as a sorting plan customized by developers.
Scheme code example
'use strict';const INDEX = Symbol('index');function getComparer(compare) { return function (left, right) { let result = compare(left, right); return result === 0 ? left[INDEX] - right[INDEX] : result; };}function sort(array, compare) { array = array.map( (item, index) => { if (typeof item === 'object') { item[INDEX] = index; } return item; } ); return array.sort(getComparer(compare));}The above is just a simple algorithm modification example that satisfies stable sorting.
The reason why it is simple is that the data structures as array inputs in the actual production environment are complex, and it is necessary to judge whether more types of pre-ordering are required based on the actual situation.
Tag
1. The front-end is now a relatively broad concept. The front-end in this article mainly refers to the environment using the browser as the carrier and JavaScript as the programming language.
2. This article does not intend to involve the algorithm as a whole. I would like to use common sorting algorithms as the entry point.
3. When confirming the algorithm implemented by Firefox array sorting, a sort-related bug was found in SpiderMoney. Generally speaking, during the discussion, someone suggested using the Timsort algorithm with better performance in extreme cases to replace the merge sorting, but Mozilla engineers said that due to the License authorization problem of the Timsort algorithm, there is no way to directly use the algorithm in Mozilla's software and wait for the other party's subsequent reply.
Summarize
The above is a summary and solution to the problems encountered in front-end sorting. In recent years, more and more projects are changing towards rich client applications, and the proportion of front-end in projects has increased. With the further improvement of browser computing power in the future, it allows for some more complex calculations. With the change of responsibilities, the front-end form may also undergo some major changes. When walking in the world, you must always have a skill.