假设我有一个大小为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;
}
我不确定在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(...)
来利用Arrayunshift(...)
方法:
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];
使用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:性能
我希望这个答案能够提供一种我认为更容易记住和简洁的替代语法。应该注意的是,根据某些基准测试(请参见此其他答案),该语法要慢得多。除非您要循环执行许多这些操作,否则这可能无关紧要。
如果将一个数组放在另一个数组的前面,则使用会更有效率concat
。所以:
var newArray = values.concat(oldArray);
但这仍然是oldArray大小的O(N)。不过,它比手动遍历oldArray更有效。另外,根据细节,这可能会为您提供帮助,因为如果要添加多个值,最好先将它们放入一个数组中,然后在最后连接concat 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]
如果您需要保留旧数组,将旧数组切成薄片,然后将新值取消移位到切片的开头。
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
*/
我对不同的前置方法进行了一些新的测试。对于小阵列(<1000个元素),引导者用于循环并采用推入方法。对于大型数组,Unshift方法将成为领导者。
但是这种情况仅适用于Chrome浏览器。在Firefox中,unshift具有出色的优化功能,并且在所有情况下都更快。
在所有浏览器中,ES6的传播速度要慢100倍以上。
https://jsbench.me/cgjfc79bgx/1
有特殊的方法:
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]
调用unshift
仅返回新数组的长度。因此,为了在开头添加一个元素并返回一个新数组,我这样做:
let newVal = 'someValue';
let array = ['hello', 'world'];
[ newVal ].concat(array);
或简单地使用传播算子:
[ newVal, ...array ]
这样,原始阵列保持不变。
就地前置示例:
var A = [7,8,9]
var B = [1,2,3]
A.unshift(...B)
console.log(A) // [1,2,3,7,8,9]
文章标签:arrays , javascript , prepend
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!
评论已关闭!