JavaScript中，使用第二个参数排序更快

JavaScript, sorting with second parameter is faster

本文关键字：参数 排序 第二个 JavaScript      更新时间：2023-09-26

我做了一个小测试，发现array.sort(function(a, b) { return a - b; });在JavaScript中比array.sort();快得多。

结果非常令人震惊，IE9快1.7倍，FF7快1.6倍，Chrome快6.7倍。

另外，通过在JS中自己实现快速排序，我发现它比上面提到的两种方法都要快。两种不同的实现，一种接受比较函数作为参数，另一种不接受。)

有合理的解释吗?

编辑:我的实现:

没有比较器:

function quickSort(array, from, to) {
    if(typeof from === 'undefined') {
        from = 0;
        to = array.length - 1;
    }
    else if(typeof to === 'undefined') {
        to = array.length - 1;
    }
    if(to - from < 1) {
        return;
    }
    var i = from, pivot = to, t;
    while(i < pivot) {
        if(array[i] > array[pivot]) {
            t = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = t;
            pivot--;
        }
        else {
            i++;
        }
    }
    quickSort(array, from, pivot - 1);
    quickSort(array, pivot + 1, to);
}
与比较器:

function quickSortFunc(array, sortfunc, from, to) {
    if(typeof from === 'undefined') {
        from = 0;
        to = array.length - 1;
    }
    else if(typeof to === 'undefined') {
        to = array.length - 1;
    }
    if(to - from < 1) {
        return;
    }
    var i = from, pivot = to, t;
    while(i < pivot) {
        if(sortfunc(array[i], array[pivot]) > 0) {
            t = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = t;
            pivot--;
        }
        else {
            i++;
        }
    }
    quickSortFunc(array, sortfunc, from, pivot - 1);
    quickSortFunc(array, sortfunc, pivot + 1, to);
}

有两个因素在起作用:

首先，正如Felix King在注释中提到的，本机sort方法在比较之前将每个数组成员转换为字符串。如果所有(或大多数)数组成员都是数字，使用function(a, b) { return a - b; }会更快。

第二，排序算法依赖于实现。您可能知道，也可能不知道，如果将新元素插入到已经排序的数组中，快速排序的性能会非常差。也许这就是WebKit决定实现选择排序的原因。

但是不要害怕，帮助就在附近!有人已经分叉WebKit来修复这个

有很多原因。不必检查变量类型是其中之一，而且只是其中之一。你的实现让优化器很高兴。它适用于密集数组，它只适用于数字，变量的作用域很好，并且可以重用。没有this，没有with，没有eval，没有魔法变量，属性，函数或类型。它会很好地优化。

但是，如果您尝试实现类型无关、顺序无关的数组方法，例如reverse()，您可能还会发现您自己的实现更快。至少我的是。

为什么?

JavaScript现在进行了大量优化，特别是在循环和重复操作相同类型的东西-数字，字符串，甚至相同形状的对象(这很复杂)。在极端情况下，运行时将内联您的函数，将跳过变量类型检查，并且，在Chrome的情况下，甚至会将您的数字保存在注册表中，以便您的循环可以像c一样快。

哇。

但这些优化只是在最近几年才开始流行起来。目前，本机函数还没有用户代码那么可优化。它们不像用户代码那样经历那么多的动态优化。

好了，我说出来了。

目前，用户代码可能比本机实现运行得更快，特别是因为程序员知道其中的数据流。但这可能是暂时的。

我将停在这里，让您决定是否要创建自己的数组库。div;)

这是一个相当疯狂的猜测，但是由于本机排序，检查传递的属性是否为空白或null，是否会导致性能下降…因此，在每次搜索中搜索默认函数(而不是一次)…

这可能是一个错误的优化问题，可以解决，如果真…希望firefox开发人员能回答这个问题:)

相关文章：