不可变集合的两种迭代方法之间的时间复杂度

Question

有一个 Immutable.js 以结构数据作为集合。让我们看一张地图。还有一些方法可以使用：

包括
过滤器

让我们考虑这些数据：

const data = Map({
  id1: Map({id: 'id1'}),
  id2: Map({id: 'id2'}),
  id100: Map({id: 'id100'}),
});

const ids = List(['id1', 'id100']);

以及迭代此 Map 的两种方法：

function selectData() {
  return data.filter((item) => ids.includes(item.get("id")));
}

function selectData() {
  let selected = Map();

  ids.forEach((id) => {
    selected = selected.set(id, data.get(id));
  });

  return selected;
}

所以，问题是：这两种方法是否等效并且在

中具有相同的时间复杂度

一般
这种特殊情况与上面地图中的数据

从我的观点来看，它们并不等价，但时间复杂度应该相同。

更新：等效 - 做同样的事情，提供相同的结果。

Answer 1

正如您所指出的，语义略有不同。在示例中，它们都提供了 id 的交集，因此


> JSON.stringify(s1())
'{"id1":{"id":"id1"},"id100":{"id":"id100"}}'
> JSON.stringify(s2())
'{"id1":{"id":"id1"},"id100":{"id":"id100"}}'

但是，有些边缘情况的数据结构不会产生类似的结果，例如您在评论中给出的示例：

const data = Map({
  id1: Map({id: 'id1'}),
  id2: Map({id: 'id1'}),
  id100: Map({id: 'id100'}),
});

const ids = List(['id1', 'id100']);

...

> JSON.stringify(s1())
'{"id1":{"id":"id1"},"id2":{"id":"id1"},"id100":{"id":"id100"}}'
> JSON.stringify(s2())
'{"id1":{"id":"id1"},"id100":{"id":"id100"}}'

注意。上面的例子看起来像一个错误，因为（值）映射中的 id 与键的 id 不匹配；但谁知道呢？

一般

方法 1 为顶级地图 (data) 中的每个项目生成 1 个项目，其值具有包含在列表中的 id 项目。
方法 2 为列表中每个在顶级映射 (data) 中有条目的值生成 1 个项目

由于这两种方法在 amp (data) 中的查找方面有所不同——一种通过键查找，另一种通过值映射中 id 的值查找——如果这两个值不一致，按照第二个例子，你会得到不同。

一般来说，第二种方法可能会更好，因为如果两个集合的大小相似，则查找 Map 可能比查找列表更便宜。如果集合的大小差异很大，您需要考虑到这一点。

查找列表的时间复杂度为 O(N)，而查找 Map is documented 的时间复杂度为 O(log32 N)（因此是某种宽树实现）。因此对于地图 M 和列表 L，方法 1 的成本将是 O(L * log32 M) 而第二种方法的成本将是 O(M * L)，如果 M == L（或接近），则课程方法 1 获胜，纸上。

分析这些东西几乎总是最好的，而不是担心理论上的时间复杂度。

实际上，可能还有另一种不错的方法，它依赖于地图已经排序的性质。如果您首先对列表进行排序，(O(L log L))，那么您可以只对两者的元素使用滑动 window 来找到交集...

不可变集合的两种迭代方法之间的时间复杂度

Time complexity between two iterate methods of immutable collection

javascript

immutable.js