Table of Contents
Foreword
Insertion sort
Principle
Illustration
Implementation
Time complexity
Stability
Advantages
Quick sort
Example
in-place implementation
stability
时间复杂度
v8 基准选择
v8 源码
Comparison
Special Series
Home Web Front-end JS Tutorial Issues about v8 sorting source code in JavaScript

Issues about v8 sorting source code in JavaScript

Oct 24, 2017 am 09:57 AM
javascript js question

The twentieth and final article in the JavaScript special series, interpreting the v8 sorting source code

Foreword

v8 is Chrome's JavaScript engine, in which there are some details about arrays Sorting is entirely implemented in JavaScript.

The algorithm used for sorting is related to the length of the array. When the array length is less than or equal to 10, insertion sort is used. When the array length is greater than 10, quick sort is used. (Of course, this statement is not rigorous).

Let’s take a look at insertion sort and quick sort first.

Insertion sort

Principle

Treat the first element as an ordered sequence, traverse the array, and insert subsequent elements into the constructed ordered sequence in sequence.

Illustration

Issues about v8 sorting source code in JavaScript

Implementation

function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var element = arr[i];
        for (var j = i - 1; j >= 0; j--) {
            var tmp = arr[j];
            var order = tmp - element;
            if (order > 0) {
                arr[j + 1] = tmp;
            } else {
                break;
            }
        }
        arr[j + 1] = element;
    }
    return arr;
}

var arr = [6, 5, 4, 3, 2, 1];
console.log(insertionSort(arr));
Copy after login

Time complexity

The time complexity is It refers to the computational workload required to execute the algorithm. It examines the situation when the size of the input value approaches infinity. Generally, the number of times the basic operations in the algorithm are repeated is a function of the problem size n.

The best case: the array is arranged in ascending order, the time complexity is: O(n)

The worst case: the array is arranged in descending order, the time complexity is: O(n²)

Stability

Stability refers to whether the same elements maintain their relative positions after sorting.

It should be noted that for unstable sorting algorithms, just give an example to illustrate its instability; while for stable sorting algorithms, the algorithm must be analyzed to obtain stable characteristics.

For example, [3, 3, 1], after sorting, is still [3, 3, 1], but in fact the second 3 is before the first 3, then this is an unstable sorting algorithm.

Insertion sort is a stable algorithm.

Advantages

When the array is about to be sorted or the problem size is relatively small, insertion sorting is more efficient. This is why v8 uses insertion sort when the array length is less than or equal to 10.

Quick sort

Principle

  1. Select an element as "baseline"

  2. is less than "baseline" Elements that are larger than "base" are moved to the left of "base"; elements that are larger than "base" are moved to the right of "base".

  3. Repeat the first and second steps for the two subsets on the left and right of the "baseline" until only one element remains in all subsets.

Example

The example and the following implementation method come from Teacher Ruan Yifeng's "Javascript Implementation of Quick Sort"

With array[ 85, 24, 63, 45, 17, 31, 96, 50] For example:

In the first step, select the middle element 45 as the "baseline". (The base value can be chosen arbitrarily, but it is easier to understand to choose the middle value.)

Issues about v8 sorting source code in JavaScript

The second step, in order, combine each element with The "baseline" is compared, forming two subsets, one "less than 45" and the other "greater than or equal to 45".

Issues about v8 sorting source code in JavaScript

The third step is to repeat the first and second steps for the two subsets until only one element remains in all subsets.

Issues about v8 sorting source code in JavaScript

Implementation

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));
};
Copy after login

However, this implementation requires additional space to store the left and right subsets, so there is another original Implementation of in-place sorting.

Illustration

Let’s take a look at the implementation diagram of in-place sorting:

Issues about v8 sorting source code in JavaScript

In order to let everyone After understanding the principle of quick sort, I slowed down the execution speed.

In this diagram, the value rule for the benchmark is to take the leftmost element. Yellow represents the current benchmark, green represents elements that are smaller than the benchmark, and purple represents elements that are greater than the benchmark.

We will find that the green element will be immediately to the right of the benchmark, the purple element will be moved to the back, and then the benchmark and the last green element will be exchanged. At this time, the benchmark is in the correct position, that is The previous elements are all less than the base value, and the following elements are all greater than the base value. Then take the basis of the previous and following multiple elements and sort them.

in-place implementation

function quickSort(arr) {
    // 交换元素
    function swap(arr, a, b) {
        var temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    function partition(arr, left, right) {
        var pivot = arr[left];
        var storeIndex = left;

        for (var i = left + 1; i <= right; i++) {
            if (arr[i] < pivot) {
                swap(arr, ++storeIndex, i);
            }
        }

        swap(arr, left, storeIndex);

        return storeIndex;
    }

    function sort(arr, left, right) {
        if (left < right) {
            var storeIndex = partition(arr, left, right);
            sort(arr, left, storeIndex - 1);
            sort(arr, storeIndex + 1, right);
        }
    }

    sort(arr, 0, arr.length - 1);

    return arr;
}

console.log(quickSort(6, 7, 3, 4, 1, 5, 9, 2, 8))
Copy after login

stability

Quick sort is an unstable sort. If you want to prove that a sorting is unstable, you only need to give an example.

So let’s give one~

就以数组 [1, 2, 3, 3, 4, 5] 为例,因为基准的选择不确定,假如选定了第三个元素(也就是第一个 3) 为基准,所有小于 3 的元素在前面,大于等于 3 的在后面,排序的结果没有问题。可是如果选择了第四个元素(也就是第二个 3 ),小于 3 的在基准前面,大于等于 3 的在基准后面,第一个 3 就会被移动到 第二个 3 后面,所以快速排序是不稳定的排序。

时间复杂度

阮一峰老师的实现中,基准取的是中间元素,而原地排序中基准取最左边的元素。快速排序的关键点就在于基准的选择,选取不同的基准时,会有不同性能表现。

快速排序的时间复杂度最好为 O(nlogn),可是为什么是 nlogn 呢?来一个并不严谨的证明:

在最佳情况下,每一次都平分整个数组。假设数组有 n 个元素,其递归的深度就为 log2n + 1,时间复杂度为 O(n)[(log2n + 1)],因为时间复杂度考察当输入值大小趋近无穷时的情况,所以会忽略低阶项,时间复杂度为:o(nlog2n)。

如果一个程序的运行时间是对数级的,则随着 n 的增大程序会渐渐慢下来。如果底数是 10,lg1000 等于 3,如果 n 为 1000000,lgn 等于 6,仅为之前的两倍。如果底数为 2,log21000 的值约为 10,log21000000 的值约为 19,约为之前的两倍。我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。所以我们认为 O(logn)已经可以表达所有底数的对数了,所以时间复杂度最后为: O(nlogn)。

而在最差情况下,如果对一个已经排序好的数组,每次选择基准元素时总是选择第一个元素或者最后一个元素,那么每次都会有一个子集是空的,递归的层数将达到 n,最后导致算法的时间复杂度退化为 O(n²)。

这也充分说明了一个基准的选择是多么的重要,而 v8 为了提高性能,就对基准的选择做了很多优化。

v8 基准选择

v8 选择基准的原理是从头和尾之外再选择一个元素,然后三个值排序取中间值。

当数组长度大于 10 但是小于 1000 的时候,取中间位置的元素,实现代码为:

// 基准的下标
// >> 1 相当于除以 2 (忽略余数)
third_index = from + ((to - from) >> 1);
Copy after login

当数组长度大于 1000 的时候,每隔 200 ~ 215 个元素取一个值,然后将这些值进行排序,取中间值的下标,实现的代码为:

// 简单处理过
function GetThirdIndex(a, from, to) {
    var t_array = new Array();

    // & 位运算符
    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;
}
Copy after login

也许你会好奇 200 + ((to - from) & 15) 是什么意思?

& 表示是按位与,对整数操作数逐位执行布尔与操作。只有两个操作数中相对应的位都是 1,结果中的这一位才是 1。

15 & 127 为例:

15 二进制为: (0000 1111)

127 二进制为:(1111 1111)

按位与结果为:(0000 1111)= 15

所以 15 & 127 的结果为 15

注意 15 的二进制为: 1111,这就意味着任何和 15 按位与的结果都会小于或者等于 15,这才实现了每隔 200 ~ 215 个元素取一个值。

v8 源码

终于到了看源码的时刻!源码地址为:https://github.com/v8/v8/blob/master/src/js/array.js#L758。

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element;
    }
};


function QuickSort(a, from, to) {

    var third_index = 0;
    while (true) {
            // Insertion sort is faster for short arrays.
        if (to - from <= 10) {
            InsertionSort(a, from, to);
            return;
        }
        if (to - from > 1000) {
            third_index = GetThirdIndex(a, from, to);
        } else {
            third_index = from + ((to - from) >> 1);
        }
        // Find a pivot as the median of first, last and middle element.
        var v0 = a[from];
        var v1 = a[to - 1];
        var v2 = a[third_index];

        var c01 = comparefn(v0, v1);
        if (c01 > 0) {
            // v1 < v0, so swap them.
            var tmp = v0;
            v0 = v1;
            v1 = tmp;
        } // v0 <= v1.
        var c02 = comparefn(v0, v2);
        if (c02 >= 0) {
            // v2 <= v0 <= v1.
            var tmp = v0;
            v0 = v2;
            v2 = v1;
            v1 = tmp;
        } else {
            // v0 <= v1 && v0 < v2
            var c12 = comparefn(v1, v2);
            if (c12 > 0) {
                // v0 <= v2 < v1
                var tmp = v1;
                v1 = v2;
                v2 = tmp;
            }
        }

        // v0 <= v1 <= v2
        a[from] = v0;
        a[to - 1] = v2;

        var pivot = v1;

        var low_end = from + 1; // Upper bound of elements lower than pivot.
        var high_start = to - 1; // Lower bound of elements greater than pivot.

        a[third_index] = a[low_end];
        a[low_end] = pivot;

        // From low_end to i are elements equal to pivot.
        // From i to high_start are elements that haven't been compared yet.

        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] = element;
                low_end++;
            } 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) {
                    element = a[i];
                    a[i] = a[low_end];
                    a[low_end] = element;
                    low_end++;
                }
            }
        }


        if (to - high_start < low_end - from) {
            QuickSort(a, high_start, to);
            to = low_end;
        } else {
            QuickSort(a, from, low_end);
            from = high_start;
        }
    }
}

var arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

function comparefn(a, b) {
    return a - b
}

QuickSort(arr, 0, arr.length)
console.log(arr)
Copy after login

我们以数组 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 为例,分析执行的过程。

1.执行 QuickSort 函数 参数 from 值为 0,参数 to 的值 11。

2.10 < to - from < 1000 第三个基准元素的下标为 (0 + 11 >> 1) = 5,基准值 a[5] 为 5。

3.比较 a[0] a[10] a[5] 的值,然后根据比较结果修改数组,数组此时为 [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10]

4.将基准值和数组的第(from + 1)个即数组的第二个元素互换,此时数组为 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10],此时在基准值 5 前面的元素肯定是小于 5 的,因为第三步已经做了一次比较。后面的元素是未排序的。

我们接下来要做的就是把后面的元素中小于 5 的全部移到 5 的前面。

5.然后我们进入 partition 循环,我们依然以这个数组为例,单独抽出来写个 demo 讲一讲

// 假设代码执行到这里,为了方便演示,我们直接设置 low_end 等变量的值
// 可以直接复制到浏览器中查看数组变换效果
var a = [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]
var low_end = 1;
var high_start = 10;
var pivot = 5;

console.log(&amp;#39;起始数组为&amp;#39;, a)

partition: for (var i = low_end + 1; i &lt; high_start; i++) {

    var element = a[i];
    console.log(&amp;#39;循环当前的元素为:&amp;#39;, a[i])
    var order = element - pivot;

    if (order &lt; 0) {
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
        console.log(a)
    }
    else if (order &gt; 0) {
        do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = top_elem - pivot;
        } while (order &gt; 0);

        a[i] = a[high_start];
        a[high_start] = element;

        console.log(a)

        if (order &lt; 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
        }
        console.log(a)
    }
}

console.log(&amp;#39;最后的结果为&amp;#39;, a)
console.log(low_end)
console.log(high_start)
Copy after login

6.此时数组为 [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10],循环从第三个元素开始,a[i] 的值为 8,因为大于基准值 5,即 order > 0,开始执行 do while 循环,do while 循环的目的在于倒序查找元素,找到第一个小于基准值的元素,然后让这个元素跟 a[i] 的位置交换。
第一个小于基准值的元素为 1,然后 1 与 8 交换,数组变成  [0, 5, 1, 7, 6, 9, 4, 3, 2, 8, 10]。high_start 的值是为了记录倒序查找到哪里了。

7. At this time, the value of a[i] becomes 1, and then exchange 1 with the base value 5, and the array becomes [0, 1, 5, 7, 6, 9, 4, 3 , 2, 8, 10], the value of low_end is increased by 1, the value of low_end is to record the location of the reference value.

8. The loop is then executed, traversing the fourth element 7, which is consistent with steps 6 and 7. The array first becomes [0, 1, 5, 2, 6, 9, 4, 3, 7, 8, 10], and then becomes [0, 1, 2, 5, 6, 9, 4, 3, 7, 8, 10]

9. Traverse the fifth element 6, the same as steps 6 and 7. The array first becomes [0, 1, 2, 5, 3, 9, 4, 6, 7, 8, 10], then becomes [0, 1, 2, 3, 5, 9, 4, 6, 7, 8, 10]

10. Traverse the sixth element 9, followed by Steps 6 and 7 are the same. The array first becomes [0, 1, 2, 3, 5, 4, 9, 6, 7, 8, 10], and then becomes [0 , 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]

#11. In the next traversal, because i == high_start, it means forward and reverse order The search finally found them together. The following elements must be greater than the base value. At this time, the loop exits

12. The result after traversal is [0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10], the elements before the base value 5 are all less than 5, and the elements behind are all greater than 5, then we perform QuickSort

13 on the two subsets respectively. This When the low_end value is 5, the high_start value is 6, the value of to is still 10, and the value of from is still 0, the result of to - high_start < low_end - from is true, We sort the following elements using QuickSort(a, 6, 10), but note that in the new QuickSort, because the value of from - to is less than 10, insertion sort is actually used this time. So to be precise, When the array length is greater than 10, v8 uses a hybrid sorting method of quick sort and insertion sort.

14. Then to = low_end that is, set to to 5. Because of while(true), it will be executed again. The value of to - from is 5, and InsertionSort is executed. (a, 0, 5), that is, perform an insertion sort on the element before the reference value.

15. Because there is a return statement in the judgment of to - from <= 10, the while loop ends.

16.v8 After performing a quick sort on the array, then performing insertion sort on the two subsets respectively, and finally modifying the array into a correctly sorted array.

Comparison

Finally, let’s take a schematic diagram to experience insertion sort and quick sort:

Issues about v8 sorting source code in JavaScript

The picture comes from https ://www.toptal.com/developers/sorting-algorithms

Special Series

JavaScript Special Series Directory address: https://github.com/mqyqingfeng/Blog.

The JavaScript topic series is expected to be about twenty articles, mainly studying the implementation of some functional points in daily development, such as anti-shake, throttling, deduplication, type judgment, copy, maximum value, flattening, curry, Recursion, reordering, sorting, etc. are characterized by studying (chao) the implementation of underscore and jQuery.


The above is the detailed content of Issues about v8 sorting source code in JavaScript. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Recommended: Excellent JS open source face detection and recognition project Recommended: Excellent JS open source face detection and recognition project Apr 03, 2024 am 11:55 AM

Face detection and recognition technology is already a relatively mature and widely used technology. Currently, the most widely used Internet application language is JS. Implementing face detection and recognition on the Web front-end has advantages and disadvantages compared to back-end face recognition. Advantages include reducing network interaction and real-time recognition, which greatly shortens user waiting time and improves user experience; disadvantages include: being limited by model size, the accuracy is also limited. How to use js to implement face detection on the web? In order to implement face recognition on the Web, you need to be familiar with related programming languages ​​and technologies, such as JavaScript, HTML, CSS, WebRTC, etc. At the same time, you also need to master relevant computer vision and artificial intelligence technologies. It is worth noting that due to the design of the Web side

Simple JavaScript Tutorial: How to Get HTTP Status Code Simple JavaScript Tutorial: How to Get HTTP Status Code Jan 05, 2024 pm 06:08 PM

JavaScript tutorial: How to get HTTP status code, specific code examples are required. Preface: In web development, data interaction with the server is often involved. When communicating with the server, we often need to obtain the returned HTTP status code to determine whether the operation is successful, and perform corresponding processing based on different status codes. This article will teach you how to use JavaScript to obtain HTTP status codes and provide some practical code examples. Using XMLHttpRequest

PHP and JS Development Tips: Master the Method of Drawing Stock Candle Charts PHP and JS Development Tips: Master the Method of Drawing Stock Candle Charts Dec 18, 2023 pm 03:39 PM

With the rapid development of Internet finance, stock investment has become the choice of more and more people. In stock trading, candle charts are a commonly used technical analysis method. It can show the changing trend of stock prices and help investors make more accurate decisions. This article will introduce the development skills of PHP and JS, lead readers to understand how to draw stock candle charts, and provide specific code examples. 1. Understanding Stock Candle Charts Before introducing how to draw stock candle charts, we first need to understand what a candle chart is. Candlestick charts were developed by the Japanese

How to solve the problem that jQuery cannot obtain the form element value How to solve the problem that jQuery cannot obtain the form element value Feb 19, 2024 pm 02:01 PM

To solve the problem that jQuery.val() cannot be used, specific code examples are required. For front-end developers, using jQuery is one of the common operations. Among them, using the .val() method to get or set the value of a form element is a very common operation. However, in some specific cases, the problem of not being able to use the .val() method may arise. This article will introduce some common situations and solutions, and provide specific code examples. Problem Description When using jQuery to develop front-end pages, sometimes you will encounter

The relationship between js and vue The relationship between js and vue Mar 11, 2024 pm 05:21 PM

The relationship between js and vue: 1. JS as the cornerstone of Web development; 2. The rise of Vue.js as a front-end framework; 3. The complementary relationship between JS and Vue; 4. The practical application of JS and Vue.

What are the questions in the Rulong 8 Wine Master exam? What are the questions in the Rulong 8 Wine Master exam? Feb 02, 2024 am 10:18 AM

What are the questions involved in the Yulong 8 Wine Master exam? What is the corresponding answer? How to pass the exam quickly? There are many questions that need to be answered in the Master of Wine Examination activities, and we can refer to the answers to solve them. These questions all involve knowledge of wine. If you need a reference, let’s take a look at the detailed analysis of the answers to the Yakuza 8 Wine Master exam questions! Detailed explanation of answers to questions in the Rulong 8 Wine Master exam 1. Questions about "wine". This is a distilled liquor produced by a distillery established by the royal family. It is brewed from the sugar of sugarcane grown in large quantities in Hawaii. What is the name of this wine? Answer: Rum 2. Question about "wine". The picture shows a drink made from dry ginseng and dry vermouth. It is characterized by the addition of olives and is known as "cockney"

How to solve the problem of the start menu that cannot be used after win11 installation How to solve the problem of the start menu that cannot be used after win11 installation Jan 06, 2024 pm 05:14 PM

Many users have tried to update the win11 system, but found that the start menu cannot be used after the update. This may be because there is a problem with the latest update. We can wait for Microsoft to fix or uninstall these updates to solve the problem. Let's take a look at it together. Solution. What to do if the start menu cannot be used after win11 is installed. Method 1: 1. First open the control panel in win11. 2. Then click the "Uninstall a program" button below the program. 3. Enter the uninstall interface and find "View installed updates" in the upper left corner. 4. After entering, you can view the update time in the update information and uninstall all recent updates. Method 2: 1. In addition, we can also directly download the win11 system without updates. 2. This is a product without the most

How to get HTTP status code in JavaScript the easy way How to get HTTP status code in JavaScript the easy way Jan 05, 2024 pm 01:37 PM

Introduction to the method of obtaining HTTP status code in JavaScript: In front-end development, we often need to deal with the interaction with the back-end interface, and HTTP status code is a very important part of it. Understanding and obtaining HTTP status codes helps us better handle the data returned by the interface. This article will introduce how to use JavaScript to obtain HTTP status codes and provide specific code examples. 1. What is HTTP status code? HTTP status code means that when the browser initiates a request to the server, the service

See all articles