javascript - 在 Javascript 中反转数组的最有效方法是什么？

Question

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

出于好奇，任何人都可以通过展示示例或指出正确的方向来帮助我探索这个问题，以便我可以阅读它吗？关于如何衡量性能的任何建议也很棒。

Answer 1

基于此设置:

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

Array.reverse(); 是第一或第二慢的!

基准在这里:

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

跨浏览器，交换循环更快。有两种常见类型的交换算法(参见 Wikipedia )，每种都有两种变体。

两种类型的交换算法是临时交换和异或交换。

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

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

临时交换:

第一个变体:

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(); 方法的算法是最短的示例，它们看起来也最干净。我希望他们以后的表现越来越好。

---

另一个值得一提的是，现代浏览器正在改进数组push 和splice 操作的性能。

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

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

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