algorithm - 从 map 集合中删除另一个 map 中包含的任何 map 的高效算法

Question

我已经设置了一组独特的映射(目前是 Java HashMap)，并希望从中删除任何完全被该集合中的其他映射完全包含的映射(即如果 m.entrySet() 是一个，则从 s 中删除 m s 中其他 n 的 n.entrySet() 的子集。)

我有一个 n^2 算法，但它太慢了。有没有更有效的方法来做到这一点？

编辑:

如果有帮助的话，可能的键集很小。

这是一个低效的引用实现:

public void removeSubmaps(Set<Map> s) {
    Set<Map> toRemove = new HashSet<Map>();
    for (Map a: s) {
        for (Map b : s) {
            if (a.entrySet().containsAll(b.entrySet()))
                toRemove.add(b);
        }
    }
    s.removeAll(toRemove);    
}

Answer 1

我不确定除了 n^2 算法之外我还能做些什么，但我有一个快捷方式可以让它更快。用每张 map 的长度列出你的 map 并对其进行排序。 map 的适当子集必须短于或等于您正在比较的 map - 永远不需要与列表中更高的 map 进行比较。