在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(); 是第一个还是第二个最慢的!

基准测试如下:http: //jsperf.com/js-array-reverse-vs-while-loop/5

在浏览器中,交换循环更快.有两种常见类型的交换算法(见维基百科),每种都有两种变体.

两种类型的交换算法是临时交换和XOR交换.

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

您可能会或可能不会看到两种变体之间存在巨大差异.例如,在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;
}

XOR交换:

第一个变化:

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 = hash: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中,这种for循环算法使用数组push并且可以splice与临时交换和XOR交换循环算法相媲美.

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

但是,您应该坚持使用交换循环算法,直到许多其他浏览器匹配或超出其阵列push和splice性能.

Answer 2

本机方法总是更快.

所以Array.reverse尽可能使用.否则,运行的实现O(1)将是最好的;)

否则只需使用这样的东西

var reverse = function(arr) {
   var result = [],
       ii = arr.length;
   for (var i = ii - 1;i !== 0;i--) {
       result.push(arr[i]);
   }
   return result;
}

基准!

如果您使用for构造的所有三个阶段而不是仅一个阶段,则有趣的循环更快.

for(var i = ii - 1; i !== 0;i--) 比那更快 var i = ii - 1;for(;i-- !== 0;)

Answer 3

以简单的方式,您可以使用地图执行此操作.

let list = [10, 20, 30, 60, 90]
let reversedList = list.map((e, i, a)=> a[(a.length -1) -i]) // [90, 60...]

Answer 4

我在Firefox中打开了一个关于慢速反向性能的Firefox错误.Mozilla的某个人看过接受的帖子中使用的基准测试,并说这是非常误导的 - 在他们的分析中,本机方法通常对于反转数组更好.(应该是!)

Answer 5

这是使用三元运算符反转数组的最有效和最干净的方法。

function reverse(arr) {
  return arr.length < 2 ? arr : [arr.pop()].concat(reverse(arr));
}
console.log(reverse([4, 3, 3, 1]));