为数组预置值的最有效方法

Most efficient way to prepend a value to an array

本文关键字：有效 方法 数组      更新时间：2023-09-26

假设我有一个大小为 N 的数组(其中 N > 0 (，是否有更有效的方法来预置不需要 O(N + 1( 步长的数组？

在代码中，本质上，我目前正在做的是

function prependArray(value, oldArray) {
  var newArray = new Array(value);
  for(var i = 0; i < oldArray.length; ++i) {
    newArray.push(oldArray[i]);
  }
  return newArray;
}

我不确定在 big-O 方面是否更有效率，但肯定使用 unshift 方法更简洁：

var a = [1, 2, 3, 4];
a.unshift(0);
// => [0, 1, 2, 3, 4]
console.log({a});

[编辑]

这个 jsPerf 基准测试表明，如果您可以就地修改数组，无论可能不同的 big-O 性能如何，unshift至少在几个浏览器中都相当快。 如果您真的无法改变原始数组，那么您可以执行以下代码片段之类的操作，它似乎并不比您的解决方案快得多：

a.slice().unshift(0); // Use "slice" to avoid mutating "a".

[编辑2]

为了完整起见，可以使用以下函数代替 OP 的示例prependArray(...)以利用数组unshift(...)方法：

function prepend(value, array) {
  var newArray = array.slice();
  newArray.unshift(value);
  return newArray;
}
var x = [1, 2, 3];
var y = prepend(0, x);
// x => [1, 2, 3];
// y => [0, 1, 2, 3];
console.log({ x, y });

在 ES6 中，您现在可以使用展开运算符创建一个新数组，并在原始元素之前插入新元素。

// Prepend a single item.
const a = [1, 2, 3];
console.log([0, ...a]);

// Prepend an array.
const a = [2, 3];
const b = [0, 1];
console.log([...b, ...a]);

更新 2018-08-17： 性能

我打算用这个答案来呈现一种我认为更令人难忘和简洁的替代语法。应该注意的是，根据一些基准(请参阅另一个答案(，此语法明显较慢。除非您在循环中执行许多此类操作，否则这可能无关紧要。

如果您将一个数组放在另一个数组的前面，则仅使用 concat 更有效。所以：

const newArray = [1, 2, 3].concat([4, 5]);
newArray; // [1, 2, 3, 4, 5]

但这仍然是 O(N( 的大小 oldArray。尽管如此，它仍然比手动迭代oldArray更有效。此外，根据细节，它可能会对您有所帮助，因为如果您要在前面添加许多值，最好先将它们放入数组中，然后在末尾连接 oldArray，而不是单独预置每个值。

在

oldArray的大小上，没有办法比O(N(做得更好，因为数组存储在连续的内存中，第一个元素位于固定位置。如果要在第一个元素之前插入，则需要移动所有其他元素。如果您需要解决此问题的方法，请按照@GWW所说的进行操作并使用链表或其他数据结构。

如果你想在数组前面加上数组(a1 加上数组 a2(，你可以使用以下内容：

var a1 = [1, 2];
var a2 = [3, 4];
Array.prototype.unshift.apply(a1, a2);
console.log(a1);
// => [3, 4, 1, 2]

以一种不可变的方式，这可能是最好的方法：

const x = 1
const list = [2, 3, 4]
const newList = [x].concat(list) // [1, 2, 3, 4]

我对不同的前缀方法进行了一些新的测试。对于小型阵列(<1000 elems(，引线用于循环耦合的推送方法。对于大型阵列，Unshift 方法成为领导者。

但这种情况仅适用于Chrome浏览器。在Firefox中，unshift具有令人敬畏的优化，并且在所有情况下都更快。

ES6 在所有浏览器中的传播速度都慢 100+ 倍。

https://jsbench.me/cgjfc79bgx/1

你需要保留旧数组，对旧值进行切片并取消移动新值到切片的开头。

var oldA=[4,5,6];
newA=oldA.slice(0);
newA.unshift(1,2,3)
oldA+''n'+newA
/*  returned value:
4,5,6
1,2,3,4,5,6
*/
调用

unshift仅返回新数组的长度。因此，为了在开头添加一个元素并返回一个新数组，我这样做了：

let newVal = 'someValue';
let array = ['hello', 'world'];
[ newVal ].concat(array);

或者简单地使用点差运算符：

[ newVal, ...array ]

这样，原始数组保持不变。

有特殊的方法：

a.unshift(value);

但是如果你想在数组前面附加几个元素，使用这样的方法会更快：

var a = [1, 2, 3],
    b = [4, 5];
function prependArray(a, b) {
    var args = b;
    args.unshift(0);
    args.unshift(0);
    Array.prototype.splice.apply(a, args);
}
prependArray(a, b);
console.log(a); // -> [4, 5, 1, 2, 3]

就地预置的示例：

var A = [7,8,9]
var B = [1,2,3]
A.unshift(...B)
console.log(A) // [1,2,3,7,8,9]

我刚刚在 Chrome 上运行了 4 种算法的基准测试：

就地：

// 1) splice method
{
    let x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    x.splice(0, 0, ...y); // 87'426 ops/s (but big variation of 35%)
    // x is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}
// 2) unshift method
{
    let x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    x.unshift(...y); // 69'471 ops/s
    // x is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}

复制：

// 3) spread operator
{
    const x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    const z = [...y, ...x]; // 17'118 ops/s
    // z is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}
// 4) concat method
{
    const x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    const z = y.concat(x); // 6'286 ops/s
    // z is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}

总结：如果你想在原地预置，取消移位和拼接都很好，如果你想要一个副本，那么传播运算符似乎是最好的选择......至少在Chrome上。

相关文章：