JavaScript 的 array.length 的时间复杂度

Question

在JavaScript中调用array.length的时间复杂度是多少？我认为它会保持不变，因为属性似乎是在所有数组上自动设置的，而您只是在查找它？

Answer 1

I think it would be constant since it seems that property is set automatically on all arrays and you're just looking it up?

没错。它是一个属性存储（未计算）并根据需要自动更新。该规范明确说明 here and here 以及其他地方。

理论上，JavaScript 引擎可以在访问时自由计算 length，就好像它是访问器属性一样，只要您无法分辨（这意味着它不可能真的是访问器属性，因为你可以在代码中检测到它），但考虑到 length 被重复使用 lot（for (let n = 0; n < array.length; ++n) 突然想到），我认为我们可以假设所有 JavaScript 广泛使用的引擎都按照规范所说的去做，或者至少做一些持续时间访问的事情。

只是 FWIW：请记住 JavaScript 的标准数组在理论上只是 objects with special behavior。而理论上，JavaScript个物体是属性个包。因此，在属性包中查找属性理论上，如果该对象被实现为某种名称->值哈希映射（并且它们过去常常是，回到糟糕的过去）。现代引擎优化对象（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>

JavaScript 的 array.length 的时间复杂度

Time complexity of JavaScript's array.length

javascript

time-complexity