JavaScript的数组.length的时间复杂度

Question

array.length 在 JavaScript 中的时间复杂度是什么？我认为它应该是常数级别，因为这个属性在所有数组上都自动设置，并且你只是在查找它，不需要计算。

- devdropper87

---

如果我可以问一下，为什么对象属性的时间复杂度会引起关注？它似乎很小，不是吗？ - Sterling Archer

@SterlingArcher 任何时候复杂度都很重要，这样最终的时间复杂度才能与其他解决方案的复杂度进行比较。 - KeitelDOG

@KeitelDOG 如果你正在计算对象属性的时间复杂度，那么要么你喜欢痛苦，要么你的老板讨厌你。 - Sterling Archer

@SterlingArcher 在这种情况下，我同意，因为那是对象属性。但更多的是因为它超出了我们的控制，而不是因为它很小。 - KeitelDOG

Answer 1

我认为这会是一个常数，因为它似乎会自动设置在所有数组上，并且您只需要查找它?

对的。 这是一个存储（而不是计算）并根据需要自动更新的属性。 规范明确说明了这一点这里 和这里等其他地方。

理论上，JavaScript引擎可以在访问时计算length，就好像它是一个访问器属性一样，只要您无法发现（这意味着它不能在代码中被检测到），但是考虑到length被重复使用很多次（例如 for (let n = 0; n < array.length; ++n)），我们可以假设所有广泛使用的JavaScript引擎都遵循规范或至少执行的是常数时间访问。

---

仅供参考：请记住，理论上JavaScript的标准数组只是具有特殊行为的对象。 而在理论上，JavaScript对象是属性包。 因此，在属性包中查找属性可能会取决于有多少其他属性存在，如果对象被实现为某种名称 ->值哈希映射（在不好的旧日子里就是这样）。 现代引擎对对象进行优化（Chrome的V8著名地动态创建类并编译它们），但对这些对象的操作仍然可以改变属性查找性能。 例如，添加一个属性可能会导致V8创建子类。 删除属性（实际使用delete）可能会使V8举起双手并回退到“字典模式”，从而大大降低对象上的属性访问。

换句话说：它可能因引擎而异，甚至因对象而异。但是，如果您仅将数组用作数组（不在其上存储其他非数组属性），那么您很有可能获得常数时间查找。

- T.J. Crowder

---

简而言之，这是否意味着我不必将数组长度保存在变量中并像(let n = 0; n < arrLen; ++n)一样引用它。使用(let n = 0; n < array.length; ++n)就可以了吗？ - cmgchess

@cmgchess - 基本上是这样的。从技术上讲，如果你将它保存到一个变量（最好是一个const）中，你就避免了每次循环的属性访问，这会非常轻微地加速循环。但是，这里的节省可能会被你在循环中所做的任何操作所抵消，并且你必须循环遍历一个巨大的数组。在今天的引擎中，这可能是过早的优化。 :-) 只是为了好玩，我放了这个。虽然有一定效果，但在现代JS引擎中，它的影响非常小。 :-) - T.J. Crowder

当然，有时候它在语义上很重要（例如，如果您正在改变数组的长度），但我知道您知道这一点。 :-) - T.J. Crowder

@T.J.Crowder 感谢提供的 jsfiddle，很高兴看到性能提升不大。 - undefined

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>

- wolfhammer