javascript - 为什么在这个 Immutable JS 测试中 equals 很慢？

Question

在更新某些状态以使用 ImmutableJS 之前，我正在对个人项目进行一些合理性测试。我编写了一个小测试以确保 Immutable.List.equals 的执行符合我的预期 - O(1)。

https://github.com/naddeoa/immutablejs-slow-equals.git

下面是重点

function compareImmutableMany(l1, l2) {
  let result = false;
  for (let i = 0; i < iterations; i++) {
    result = l1.equals(l2);
  }
  return result;
}

i1 = createImmutableList();
i2 = createImmutableList();
console.log("immutable lists are equal", compareImmutableMany(i1, i2));

测试正在比较两个大小为 100,000 的原生 js 列表，然后比较两个大小为 100,000 的 Immutable.List，每个 1000 次。我肯定错过了什么。我发现 Immutable.List 示例相对于 native 列表示例表现非常差。

starting
immutable lists are equal true
Seconds: 11.423
starting
normal lists are equal: true
Seconds: 0.109

您可以使用以下命令在本地运行它。

git clone https://github.com/naddeoa/immutablejs-slow-equals.git
cd immutablejs-slow-equals
npm i
node main.js

如果我犯了一个简单的错误，那么我会感谢一些眼睛让我知道它在哪里。我绝对希望这会非常快。特别是因为将 l1.equals(l2) 替换为对 l1.hashCode() 的调用非常快。

Answer 1

根据docs :

Two immutable collections are considered value equal (via .equals() or is()) if they represent the same collection of values. This differs from JavaScript's typical reference equal (via === or ==) for Objects and Arrays which only determines if two variables represent references to the same object instance.

这意味着它不能是 O(1)，因为它需要检查列表中所有值的相等性。这将大大降低速度(如您所见)。

还记录了性能权衡:

When comparing two collections, value equality may require considering every item in each collection, on an O(N) time complexity. For large collections of values, this could become a costly operation. Though if the two are not equal and hardly similar, the inequality is determined very quickly. In contrast, when comparing two collections with reference equality, only the initial references to memory need to be compared which is not based on the size of the collections, which has an O(1) time complexity. Checking reference equality is always very fast, however just because two collections are not reference-equal does not rule out the possibility that they may be value-equal.