`for(key in obj) BREAK` 的复杂度为 O(N) 而不是 O(1)。有没有办法克服这个

Question

可以期待与此类似的代码

for(let i = 0 ; i !== N ; ++i ) break

具有 O(1) 的复杂性。

但如果是 for(of) 或 for(in)，则永远无法确定。因为它强烈依赖于引擎的specifics.

因此，以下代码片段在我的 Chrome 87、FF 83 和 Node.js 14 分别为小对象和大对象提供大约 0 毫秒（0.01 毫秒）和 150 毫秒。

const create_obj = n => {
  return Object.fromEntries((function *() {
    for(let i = 0; i!==n ; ++i) yield [i,i]
  })())
}

const check_forin_peformance = obj => {
  let start_time = performance.now()
  for(const key in obj) {
    console.log("first iteration after", performance.now() - start_time, "ms")
    break
  }
}
const small_obj = create_obj(1_000)
const big_obj = create_obj(1_000_000)

console.log("small obj has", Object.keys(small_obj).length, "fields")
check_forin_peformance(small_obj)
console.log("big obj has", Object.keys(big_obj).length, "fields")
check_forin_peformance(big_obj)

这让我相信它具有 O(N) 的复杂性。尽管存在 break 和 仅执行一次迭代。

In FF for(const x of Object.keys(obj)) 提供更好的性能。不过看起来还是眼线：

let obj = Object.fromEntries((function *(){ for(let i = 0 ; i !== 1_000_000; ++i ) yield [i,i] })())
let start_time = performance.now()
let x = Object.keys(obj).length
console.log(performance.now() - start_time);

obj = Object.fromEntries((function *(){ for(let i = 0 ; i !== 1_000_000; ++i ) yield [i,i] })())
start_time = performance.now()
for(const x of Object.keys(obj)) { console.log("first iteration after", performance.now() - start_time); break; }

obj = Object.fromEntries((function *(){ for(let i = 0 ; i !== 1_000_000; ++i ) yield [i,i] })())
start_time = performance.now()
for(const x in obj) { console.log("first iteration after", performance.now() - start_time); break; }

还不是很清楚，但这可能是由于 section 规范所致。特别是由于这些行

 i. Let `keys` be ? `object`.[[OwnPropertyKeys]]().
ii. For each `key` of `keys` in List order, do
      1. If `Type(key)` is String, then
             a. Append `key` to `remaining`.

因此，由于可能在第一次迭代之前创建了一些列表，O(N) 是一个很好的猜测。但这显然是次优的。可以想象一种算法在迭代器的帮助下枚举对象的键，以便第一次迭代在 O(1) 时间后开始。但现在就是这样了。

我想知道：有什么可以做的吗？因此，如果我遍历 n 个键（比 N 小得多），我得到 O(n) 复杂度而不是 O(N)。也许有一些我不知道的聪明技巧。但它应该适用于任何对象，而不仅仅是我自己创建的对象。

以及对 V8 源代码中发生这一切的地方的引用也将不胜感激。

Answer 1

除了已经在评论中讨论过的内容之外，这里没什么可补充的...

另请参阅我的回答：Object.keys() complexity?

for..in 是一个特别复杂的操作，因为它甚至考虑了原型链。 for..of 可能更快；但是 for (... of obj.keys()) 仍然至少是线性的，因为 Object.keys() returns 一个数组。

创建临时数组的捷径通常是不可能的，因为循环体可能会修改对象，并且语言规范通常会准确说明当它这样做时应该发生什么：通常这样的修改不能反映在迭代中，所以引擎确实必须首先复制属性列表。

我不知道有什么方法可以通用地避免这种情况（对于所有对象）。

当心微基准测试，因为它们通常具有误导性，除非您已经知道幕后发生的事情以及原因。可以肯定的是，所有引擎处理具有一百万个属性的对象与具有十个属性的对象不同，因此您对前者的调查不应影响您对后者的决定。

`for(key in obj) BREAK` 的复杂度为 O(N) 而不是 O(1)。有没有办法克服这个

`for(key in obj) BREAK` has an O(N) compexity and not O(1). Is there a way to overcome this

javascript

performance

v8