在 Javascript 中反转数组的最有效方法是什么? [英] What is the most efficient way to reverse an array in Javascript?

问题描述

最近有人问我在 Javascript 中反转数组的最有效方法是什么.目前，我建议使用 for 循环并摆弄数组，但后来意识到有一个本机 Array.reverse() 方法.

I was asked recently what was the most efficient way to reverse an array in Javascript. At the moment, I suggested using a for loop and fiddling with the array but then realized there is a native Array.reverse() method.

出于好奇，任何人都可以通过展示示例或指出正确的方向来帮助我探索这一点，以便我可以阅读此内容吗?任何关于如何衡量绩效的建议也很棒.

For curiosity's sake, can anyone help me explore this by showing examples or pointing in the right direction so I can read into this? Any suggestions regarding how to measure performance would be awesome too.

推荐答案

基于此设置:

var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var length = array.length;

Array.reverse(); 是第一个或第二个最慢的！

Array.reverse(); is the first or second slowest!

基准点在这里:

https://jsperf.com/js-array-reverse-vs-while-loop/9

跨浏览器，交换循环更快.有两种常见类型的交换算法(参见 维基百科)，每一种都有两个变化.

Across browsers, swap loops are faster. There are two common types of swap algorithms (see Wikipedia), each with two variations.

两种交换算法是临时交换和异或交换.

The two types of swap algorithms are temporary swap and XOR swap.

这两个变体以不同的方式处理索引计算.第一个变体比较当前的左索引和右索引，然后递减数组的右索引.第二个变体比较当前左索引和除以一半的长度，然后为每次迭代重新计算右索引.

The two variations handle index calculations differently. The first variation compares the current left index and the right index and then decrements the right index of the array. The second variation compares the current left index and the length divided by half and then recalculates the right index for each iteration.

您可能会也可能不会看到这两种变体之间的巨大差异.例如，在 Chrome 18 中，临时交换和异或交换的第一个变体比第二个变体慢 60% 以上，但在 Opera 12 中，临时交换和异或交换的两个变体具有相似的性能.

You may or may not see huge differences between the two variations. For example, in Chrome 18, the first variations of the temporary swap and XOR swap are over 60% slower than the second variations, but in Opera 12, both variations of the temporary swap and XOR swap have similar performance.

临时交换:

第一个变体:

function temporarySwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

第二个变体:

function temporarySwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

<小时>

异或交换:

第一个变体:

function xorSwap(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0, r = length - 1; i < r; i += 1, r -= 1)
    {
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

第二个变体:

function xorSwapHalf(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0; i < length / 2; i += 1)
    {
        r = length - 1 - i;
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

<小时>

还有另一种称为解构赋值的交换方法:http://wiki.ecmascript.org/doku.php?id=harmony:destructuring

解构赋值:

第一个变体:

function destructuringSwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

第二个变体:

function destructuringSwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

目前，使用解构赋值的算法是所有算法中最慢的.它甚至比 Array.reverse(); 还要慢.然而，使用解构赋值和Array.reverse();方法的算法是最短的例子，它们看起来最干净.希望他们以后的表现越来越好.

Right now, an algorithm using destructuring assignment is the slowest of them all. It is even slower than Array.reverse();. However, the algorithms using destructuring assignments and Array.reverse(); methods are the shortest examples, and they look the cleanest. I hope their performance gets better in the future.

另一个提到的是，现代浏览器正在提高其数组push 和splice 操作的性能.

Another mention is that modern browsers are improving their performance of array push and splice operations.

在 Firefox 10 中，这个使用数组 push 和 splice 的 for 循环算法可以与临时交换和 XOR 交换循环算法相媲美.

In Firefox 10, this for loop algorithm using array push and splice rivals the temporary swap and XOR swap loop algorithms.

for (length -= 2; length > -1; length -= 1)
{
    array.push(array[length]);
    array.splice(length, 1);
}

但是，您可能应该坚持使用交换循环算法，直到许多其他浏览器匹配或超过它们的数组 push 和 splice 性能.

However, you should probably stick with the swap loop algorithms until many of the other browsers match or exceed their array push and splice performance.

这篇关于在 Javascript 中反转数组的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！