preface

Today we are going to tear the front two functions – > “sort” and “splice”, to understand the underlying logic function allows you to see nature through function, increase the programmer’s accomplishment, if you think these underlying function for the front end is far away from the, then please go out then make a left turn, this article will be on hand to tear with knowledge in the process, expanding knowledge scope.

Hand sort

A preliminary understanding

Function is the first citizen of JS. The function passed as a parameter is called a higher-order function. And when the parameter is null or invalid, the parameter will be initialized.

2. When the default function is used for sorting, the characters are sorted in Unicode order

3, if you do not have the basic of insert sort or three-way sharding, then you can first look at the related algorithm link: – Insert sort – three-way sharding quicksort

Hand link

Our hand-ripped Sort is implemented as standard with the Google Chorme V8 engine. The V8 engine is implemented by insertion sort + three – way segmentation quicksort

1. V8 engine sorting mechanism

When the array length is less than or equal to 10, insert sort is used. Why not use nlogn quicksort rather than insert sort with n^2 time complexity, because n^2 > nlogn only works if n is large enough, so large that the coefficients are ignored, but as n gets smaller and smaller, the advantage of nlogn gets worse and worse.

// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
Copy the code

2. Standardize incoming parameters.

var array = Object(this); var length = array.length >>> 0; if(Object.prototype.toString(compareFn) ! == '[Object function]' { compareFn = function (x, y) { if(x === y) return 0; x = String(x); y = String(y); if(x === y) return 0; else return x < y ? 1:1; }}Copy the code

2.1, here we can see our converts this object, the goal is to intercept using Array. The prototype. Sort. Make incoming call () way “this” for the primitive type that cause errors.

2.2, we also use the >>> unsigned right shift operator, its function is to move the number to the right n bits, and the sign bit with 0 complement, in order to ensure that length is non-negative.

3. Insert sort

function InsertSort(a, from, to) { for(var i = from; i < to; i++) { let ele = a[i]; for(var j = i-1; j >= from && compareFn(ele, a[j]) > 0; j--) a[j+1] = a[j]; a[j+1] = ele; }}Copy the code

3.1. The traditional insertion sort is optimized here, with the least number of comparisons and pit filling instead of swapping.

3.2. Note that we compare the array value as the “second parameter” with the parameter before the second parameter in compareFn. When the return value is less than 0, determine the position of the value and stop the exchange

Image: blog.csdn.net/xiaoxiaojie…

quicksort

getThirdIndex(a, from , to) { var increment = 200 + ((to - from) & 15); // random increment from++; to--; var tmpArr = []; var index = 0; for(var i = from; i < to; i += increment) { tmpArr[index++]= [i,a[i]]; // enter key-value,value for sorting again,key for ThirdIndex; } tmpArr.sort(function (a,b) { return compareFn(a[1],b[1]); }); return tmpArr[tmpArr.length >> 1][0]; }Copy the code

4.1 When the array length is greater than 1000, this function randomly obtains the intermediate T value of the three-way shard sort.

4.2 the purpose of V8 is to make t value as median as possible to ensure the time complexity of Nlogn, because if the sorting is the worst time complexity every time, it will degenerate to N ^2

4.3 The operation of from and to here is to give up the two ends and prevent the two ends of and three-way segmentation from overlapping.

4.4 recursively calling intermediate arrays is also to ensure randomness of intermediate values, and we can see that our increment is very large, which means that the probability of browser stack overflow due to recursion is very low.

5, officially enter the fast queue

  var v0 = a[from];
   var v1 = a[to-1];
   var v2 = a[third_index];
   var temArr = [v0,v1,v2];
   tmpArr.sort(compareFn);
   [v0,v1,v2] = tmpArr;
   
Copy the code

5.1, here we use the structure assignment method, but v8 source code to ensure compatibility, does not use such a way, but “by sequential comparison of three random numbers comparenFn sort assignment”,

partition: for (var i = low_end + 1; i < high_start; i++) { var element = a[i]; var order = comparefn(element, pivot); if (order < 0) { [a[i],a[low_end]] = [a[low_end++],a[i]]; } else if (order > 0) { do { high_start--; if (high_start == i) break partition; var top_elem = a[high_start]; order = comparefn(top_elem, pivot); } while (order > 0); a[i] = a[high_start]; a[high_start] = element; if (order < 0) { [a[i],a[low_end]] = [a[low_end++],a[i]]; } } } if (to - high_start < low_end - from) { QuickSort(a, high_start, to); to = low_end; } else { QuickSort(a, from, low_end); from = high_start; }}Copy the code

5.2. First, we give up the values at both ends again in quicksort. Since we have determined the relationship between the values of from and to and the target value of quicksort in the previous step, there is no need to sort. Then we do the normal three-way quicksort, and finally we can see that it only splits cells each time. Here we think about 🤔, guess the purpose is to reduce function calls and prevent stack overflow.

With hand tear:

Array.prototype.sort = function(compareFn) { let arr = Object(this); let length = this.length >>> 0; return _InnerArray(arr,length, compareFn); / / main function entry function _InnerArray (arr, length, compareFn) {if (Object. The prototype. ToString. Call (compareFn)! == '[Object function]') { compareFn = function(x, y) { if(x === y) return 0; x = String(x); y = String(y); if(x === y) return 0; else return x < y ? 1:1; } } QuickSort(arr,0,length); Function InsertionSort(a, from, to) {for(var I = from+1; i < to; i++) { let ele = a[i]; for(var j = i-1; j >= from && compareFn(a[j],ele) > 0; j--) a[j+1] = a[j]; a[j+1] = ele; } } function getThirdIndex(a, from , to) { var increment = 200 + ((to - from) & 15); // random increment from++; to--; var tmpArr = []; var index = 0; for(var i = from; i < to; i += increment) { tmpArr[index++]= [i,a[i]]; // enter key-value,value for sorting again,key for ThirdIndex; } tmpArr.sort(function (a,b) { return compareFn(a[1],b[1]); }); return tmpArr[tmpArr.length >> 1][0]; } function QuickSort(a, from, to) { var third_index = 0; while(true) { if(to - from <= 10) { InsertionSort(a, from, to); return; } else if(to - from > 1000) { third_index = getThirdIndex(a, from , to); } else { third_index = from + ((to - from) >> 1); } var tmpArr = [a[from], a[to-1], a[third_index]]; tmpArr.sort(compareFn); var [v0,v1,v2] = tmpArr; a[from] = v0; a[to - 1] = v2; var pivot = v1; var low_end = from + 1; var high_start = to - 1; a[third_index] = a[low_end]; a[low_end] = pivot; partition: for(var i = low_end+1; i < high_start; i++) { var element = a[i]; var order = compareFn(element, pivot); if(order < 0) { [a[i],a[low_end++]] = [a[low_end],a[i]]; } else if(order > 0) { do { high_start--; if(high_start == i) break partition; var top_element = a[high_start]; order = compareFn(top_element, pivot); } while (order > 0); a[i] = a[high_start]; a[high_start] = element; if(order < 0) { [a[i],a[low_end++]] = [a[low_end],a[i]]; } } } if (to - high_start < low_end - from) { QuickSort(a, high_start, to); to = low_end; } else { QuickSort(a, from, low_end); from = high_start; } } } } }Copy the code

6. Summary.

If you look at sort’s source code, you can see that V8 sort actually cuts the array size recursively and uses the efficient insertion sort directly when the array size is less than 10. This not only reduces the number of data exchanges, but also avoids the complexity and inefficiency of three-way sharding to obtain Third_value for n^logn.

Source code: (V8 — sort).

Hand splice

Splice is much friendlier to novices than Sort, and it is more difficult to consider its boundaries than sort, which requires knowledge of data structures and algorithms.

1. Basic understanding

1.1 splice is a method that alters an array and returns not the array itself, but an array of deleted elements.

1.2 splice has two + N parameters, corresponding to the starting position of the index of the deleted element, the number of deleted elements, and the n data to be filled in after deletion respectively.

2. Hand tearing link.

Initialize the

  let O = Object(this);
   let len = this.length >>> 0;
   if(len - deleteCount + items.length > 2 ** 32 - 1)
       throw RangeError('Invalid array length')
       
Copy the code

According to the ECMA-262 specification, the length of an array is bound to an unsigned integer, and an unsigned integer represents 4 bytes, or 32 bits, so the length of an array cannot exceed 2^ 32-1.

Multi-case consideration

1. If the initial index is negative, it is calculated from the tail.
 if(start < 0)
      start = start+len >= 0 ? start+len : 0;
  else {
      start = start >= len ? len : start;
  }
  
Copy the code

The multi-line judgment here is for code readability, which is part of programmer literacy.

2. Initialize the length of the deleted data.
 if(arguments.length == 1) deleteCount = len-start;
  else if(deleteCount < 0) deleteCount = 0;
  else if(deleteCount+start > len) deleteCount = len-start;
  
Copy the code
Check array property.
if(Object.isSealed(O) && items.length ! == deleteCount) { if(item.length > deleteCount) throw new TypeError('Cannot add property, object is not extensible'); else throw new TypeError('Cannot delete property of [object Array]'); } else if(Object.isFrozen(O) && (items.length > 0 || deleteCount > 0)) throw new TypeError('... '); // I'm lazy ~~~Copy the code

  • DefineProperty provides a writable, 64x, and enumerable, which is different from any other Object. An array, as a special Object, can be specified by Object.defineProperty, and any additional Object can be specified as writable, “64x”, and enumerable Discuss writable and 64x.

  • Writable is used to define whether an object’s properties can be overridden

  • The implementation of the delete freely works without any additional control system, which works without any additional control system.

  • Object. Seal (obj) indicates that all attributes of the Object cannot be detached. The names of the attributes in the array are strings.

4. Data filling

Judge in three cases.

1. Number of fillings === Number of deletions

2. Fill number > delete number

3. Fill number < delete number

if(deleteCount <= items.length) { for(let i = start; i < start+deleteCount; i++) { retArr.push(O[i]); O[i] = items[i-start]; If (deleteCount < items.length) {let add = items.length-deleteCount; this.length += add; for(let i = len-1; i >=start+deleteCount; i--) { O[i+add] = O[i]; } for(let i = 0; i < add; i++) { O[start+deleteCount+i] = items[i+deleteCount]; }}Copy the code
  • When the insertion length of data is larger than the deletion length, it indicates that the following part of data needs to be deleted later, leaving space for the insertion length and increasing the array length. So you can fill it.
else if(deleteCount > items.length) { for(let i = 0; i < deleteCount; i++) { retArr.push(O[i+start]); } for(let i = 0; i < items.length; i++) { O[i+start] = items[i]; } for(let i = 0; i < len - start - deleteCount; i++) { O[start+items.length+i] = O[i+start+deleteCount]; } this.length -= deleteCount-items.length; }Copy the code
  • When the data insert length is less than the delete length, the back part should be moved forward and the array length should be reduced.

With hand tear:

Array.prototype.splice = function(start,deleteCount,... items) { let O = Object(this); let len = this.length >>> 0; if(len - deleteCount + items.length > 2 ** 32 - 1) { throw new TypeError('... '); } let retArr = []; Start if(start < 0) {start = start+len >= 0? start+len : 0; } else { start = start >= len ? len : start; } if(arguments.length == 1) deleteCount = len-start; else if(deleteCount < 0) deleteCount = 0; else if(deleteCount+start > len) deleteCount = len-start; // If (object.issealed (O) &&items. Length) {// If (object.issealed (O) &&items ! == deleteCount) throw new TypeError('... '); else if(Object.isFrozen(O) && (items.length > 0 || deleteCount > 0)) throw new TypeError('... '); If (deleteCount <= items. Length) {for(let I = start; i < start+deleteCount; i++) { retArr.push(O[i]); O[i] = items[i-start]; If (deleteCount < items.length) {let add = items.length-deleteCount; this.length += add; for(let i = len-1; i >=start+deleteCount; i--) { O[i+add] = O[i]; } for(let i = 0; i < add; i++) { O[start+deleteCount+i] = items[i+deleteCount]; Else if(deleteCount > items. Length) {for(let I = 0; i < deleteCount; i++) { retArr.push(O[i+start]); } for(let i = 0; i < items.length; i++) { O[i+start] = items[i]; } for(let i = 0; i < len - start - deleteCount; i++) { O[start+items.length+i] = O[i+start+deleteCount]; } this.length -= deleteCount-items.length; } return retArr; }Copy the code

The source code is placed in the source code address above, but splice’s source code is less readable.

Summary.

Splice is difficult to move array lengths and handle boundary cases, and it is also a very in-depth problem.

Summary: Tearing such a question is very test programmer literacy, but if you can understand these questions clearly, so is also very open programmer gap. I hope all readers can understand these two topics in depth

, recruiting

There are a hundred ways to be sweet, and one of the most important is to see you at work every day. Murui front end team, affiliated to Hangzhou Murui Science and technology R&D Department, has a front-line river view. The technical team has more than 40 members, who come from zhejiang University, Peking University, Carleton, NUS, The George Washington University and many other well-known universities. At the same time, the company also has deep cooperation with China Academy of Art, Zhejiang University in business. Team has a perfect system of research and development process of the closed loop and standard specification and document service, in addition to the daily business docking, in visualization, library materials, engineering systems, buried together, the data point before and after, test automation, Web performance, compliance testing, build capacity and build practical deployment direction of exploration and innovation, implement a series of internal product technology.

If you are worried about the lack of talent, it just so happens that our boss has the lack of money. If you are struggling with your inability to break through, we have plenty of opportunities for you to do so. The telescope can see up to 13.7 billion light years, and your potential is limitless. Any time, let’s talk about [email protected]