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

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;
}

因此，问题是：这两种方法在中是等效的，并且具有相同的时间复杂性吗

• 概述
• 上面Map中数据的特殊情况

从我的POV来看，它们不相等，但时间复杂性应该相同。

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

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"}}'

注意。上面的情况看起来像一个bug，因为(value(映射中的id与键的id不匹配；但谁知道呢？

一般情况下

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

由于这两种方法在amp(data(中的查找方面不同——一种是按键查找，另一种是值映射中id的值查找——如果这两个值不一致，如第二个示例所示，您将得到差异。

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

对列表的查找将是O(N(，而对Map的查找记录为O(log32 N)(因此是某种宽树实现(。因此，对于映射M和列表L，近似1的成本将是O(L * log32 M)，而第二种方法的成本将为O(M * L)，如果M == L(或接近(，那么方法1当然获胜，在纸上。

与其担心理论上的时间复杂性，不如描述这些事情。

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