javascript - 如何在不分配的情况下迭代 Javascript 映射或对象？

Question

我正在用 Javascript 开发一款游戏，其中涉及尽快运行渲染循环。我注意到 GC(垃圾收集器)尖峰中断了平滑的帧速率，并且在分析之后我发现我的实体查询系统正在生成大量垃圾。

在这样做的过程中，我发现 iterators cause allocations在Javascript中。在我的代码的一部分中，我正在做这样的事情:

let minimumSet = this.getSmallestEntitySet(componentTypes);

for (let entity of minimumSet) {
  // handle entity
}

不幸的是，仅仅执行 for of 循环会导致分配(因为每次循环运行时它都会创建一个新的迭代器对象)，并且由于它运行得如此频繁，因此会产生大量垃圾。我环顾四周，找不到是否有一种方法可以在不执行的情况下迭代 Set、Map 或 Object拨款。例如，对于 Javascript 数组，您可以迭代它，同时避免这样的分配:

for (let i = 0; i < arr.length; i++) {
  let item = arr[i];

  // handle item
}

但是我找不到一种方法来像这样使用常规的 for 循环迭代 Map 或 Set。可能吗？

假设这是不可能的，我假设解决方法是使用排序数组而不是映射，对吗？唯一的问题是插入和删除是 O(log n) 而不是 O(1)，但我想这可能是值得的，只是为了避免分配。

我最好的选择是有没有一种方法可以在不执行分配的情况下迭代这些集合？

Answer 1

(此处为 V8 开发人员。)

正如您链接到的问题所指出的那样，JavaScript 引擎(至少是 V8)确实优化了迭代协议(protocol)的规范文本所讨论的临时对象；尽管完整的答案(通常如此)是“视情况而定”。

一个影响是优化编译器所做的事情是优化事物，而那些不会立即启动(因为通常情况下，这会浪费精力)。所以如果你只运行一个函数几次，你会看到它的未优化版本分配了短暂的垃圾。但这种情况很快就会改变(具体取决于引擎)，只要该功能被视为“热门”并得到优化。

您可能遇到的另一个问题是遍历 Map直接(如:let map = new Map(); ...; for (let e of map) {...} 指定返回 e 作为数组 [key, value] 每次。这个数组没有被优化掉；它必须在每次迭代中分配。但是如果你只对处理感兴趣无论如何，您可以通过仅迭代值来避免创建它:for (let v of map.values()) {...} 不分配任何短期对象。迭代 map.keys() 也是如此。

如果您同时需要键和值，您可以将对键的迭代与映射查找相结合:for (let key of map.keys()) { let value = map.get(key); ...} ，但是这比遍历值要慢很多。如果你的对象实现 interface Entry如您的回答所示，即他们有一个带有 key 的属性，那么您可以改用它:for (let value of map.values()) { let key = value.id; ...} .

---

综上所述:如果SparseSet解决方案适合您，那当然也很酷。你甚至可以让它更有效率:如果你改变 add至 add(item: T) { let key = item.id; ...}并更新 delete包括 this.sparse.delete(key) ，则集合本身可以保证其内部数据始终一致，则contains可以像 return this.sparse.get(key) !== undefined; 一样简单.

I assume the work-around for this is to instead use a sorted array instead of a map, right? The only issue with that is that insertion and deletion is O(log n)

排序数组的插入和删除是 O(n)，因为您可能需要移动整个内容。 (如果您使用二进制搜索，则通过排序键查找元素的时间复杂度为 O(log n)。)但是，使用未排序 数组可能比直觉上预期的要快，只要它们仍然很小(大约几十个条目)。像这样的东西:

class UnsortedArray<T extends Entry> {
  contents: Array<T> = [];

  add(item: T) { contents.push(T); }  // optional: check for duplicates first
  private find(key: number) {
    for (let i = 0; i < contents.length; i++) {
      if (contents[i].id == key) return i;
    }
    return -1;
  }
  size() { return contents.length; }
  get_by_index(index: number) { return contents[index]; }
  get_by_key(key: number) { return contents[find(key)]; }
  has(item: T) { return find(T.id) >= 0; }
  delete(item: T) {
    let index = find(T.id);
    if (index < 0) return;
    let last = contents.pop();
    if (index !== contents.length) contents[index] = last;
  }
}

这为您提供了 O(1) 的插入、无开销的经典迭代 ( for (let i = 0; i < unsorted_array.size(); i++) { let entry = unsorted_array.get_by_index(i); ...} )、删除和 has在 O(n) 中。我期待 has一旦超过 30-50 个元素，实际上只会比对有序数组进行二分查找慢；当然，这取决于您的用例是否 has性能至关重要。