javascript的.length的时间复杂度

Question

javascript的数组.length的时间复杂度是多少？我认为它会保持不变,因为看起来属性是在所有阵列上自动设置的,你只是在查找它？

Answer 1

我认为它会保持不变,因为看起来属性是在所有阵列上自动设置的,你只是在查找它？

对.可能.它是一个存储(未计算)并根据需要自动更新的属性.

话虽如此,请记住JavaScript引擎可以在封面下自由地执行他们喜欢的操作,前提是您无法忽略规范所说的内容.由于规范没有说明时间复杂性length......

还要记住,JavaScript的标准数组在理论上只是具有特殊行为的对象.而从理论上讲,JavaScript对象是财产袋.因此,在理论上,查找属性包中的属性可能取决于有多少其他属性,如果对象被实现为某种名称 - >值hashmap(过去它们曾经是旧的).现代引擎优化对象(Chrome的V8着名创建动态类并编译它们),但对这些对象的操作仍然可以改变属性查找性能.例如,添加属性可能会导致V8创建子类.删除属性(实际使用delete)可以让V8举手并退回到"字典模式",这大大降低了对象的属性访问.

换句话说:它可能会有所不同,从引擎到引擎,甚至是对象.但是如果你纯粹使用数组作为数组(不在其上存储其他非数组属性),那么你可能会获得恒定时间查找.

Answer 2

它看起来不像是瓶颈，但如果您想确定使用var len = arr.length并检查它。它没有伤害，并且在我的机器上似乎更快一点，尽管没有显着差异。

var arr = [];
for (var i = 0; i < 1000000; i++) {
  arr[i] = Math.random();
}


var start = new Date();
for (var i = 0; i < arr.length; i++) {
   arr[i] = Math.random(); 
}

var time1 = new Date() - start;
var start = new Date();

for (var i = 0, len = arr.length; i < len; i++) {
  arr[i] = Math.random();
}

var time2 = new Date() - start;

document.getElementById("output").innerHTML = ".length: " + time1 + "<br/>\nvar len: " + time2;

<div id="output"></div>