将值添加到数组的最有效方法

Question

假设我有一个大小为N(where 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;
}

Answer 1

我不确定在big-O方面效率更高,但肯定使用该unshift方法更简洁:

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

[编辑]

这个jsPerf基准测试显示,unshift至少在几个浏览器中速度要快得多,不管可能有不同的大O性能,如果你可以就地修改阵列.如果你真的无法改变原始数组,那么你会做类似下面的代码片段,它似乎没有比你的解决方案快得多:

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

[编辑2]

为了完整起见,可以使用以下函数代替OP的示例prependArray(...)来利用Array unshift(...)方法:

function prepend(value, array) {
  var newArray = array.slice();
  newArray.unshift(value);
  return newArray;
}

var x = [1, 2, 3];
var y = prepend(0, x);
y; // => [0, 1, 2, 3];
x; // => [1, 2, 3];

Answer 2

使用ES6,您现在可以使用spread运算符创建一个新数组,并在原始元素之前插入新元素.

// 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:性能

我打算在这个答案中提出一种我认为更难忘和简洁的替代语法.应该注意的是,根据一些基准测试(参见其他答案),这种语法明显变慢.除非您在循环中执行许多这些操作,否则这可能不重要.

Answer 3

如果您将数组添加到另一个数组的前面,则使用它会更有效concat.所以:

var newArray = values.concat(oldArray);

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

在oldArray的大小中,没有办法比O(N)做得更好,因为数组存储在连续的内存中,第一个元素处于固定位置.如果要在第一个元素之前插入,则需要移动所有其他元素.如果您需要解决此问题,请执行@GWW所说的内容并使用链接列表或不同的数据结构.

Answer 4

如果您想要添加数组(a1与数组a2),您可以使用以下内容:

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

Answer 5

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

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

Answer 6

我对不同的前置方法进行了一些新的测试。对于小型数组（<1000 个元素），领导者是 for 循环与 Push 方法相结合。对于大型数组，Unshift 方法成为领导者。

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

ES6 在所有浏览器中的传播速度慢了 100 倍以上。

https://jsbench.me/cgjfc79bgx/1

Answer 7

如果需要保留旧数组,请将旧数组切片并将新值取消移动到切片的开头.

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
*/

Answer 8

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

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

或者简单地使用扩展运算符：

[ newVal, ...array ]

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