从地图集合中高效移除包含在另一个地图中的任何地图的算法

Question

我有一组唯一的映射（目前是Java HashMaps），希望从中删除完全包含在集合中某个其他映射中的映射（即如果m.entrySet()是s中某个其他n.entrySet()的子集，则将m从s中删除）。

我有一个n²的算法，但速度太慢。有更高效的方法吗？

编辑：

如果需要，可能键的集合很小。

这里是一个低效的参考实现：

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

- rattigan

---

你只想在m是S的严格子集时从s中删除m的映射吗？ - Ben S

如果我的输入是{{a:1, b:1},{a:1}}，我希望输出为{{a:1, b:1}}，因为{a:1}是{a:1, b:1}的子映射。 - rattigan

这更像是O(n^2*m)，其中m是最大Map的大小。 - Claudiu

{{a: 2, b:1}, {a:1}}应该怎么处理？{{a:1, b:1}, {a:2}}呢？从你的例子来看，我猜测你实际上将这些映射用作集合本身。 - Svante

@Ben S：有点晚了……不一定是严格的子集，尽管对于我的问题来说，所有的地图都不同，所以这意味着相同的事情。 - rattigan

Answer 1

我不确定我能将这个算法转换成其他形式，但我有一个快捷方式可以使它更快。制作一个地图列表，并按每个地图的长度进行排序。地图的子集必须比您正在比较的地图短或相等-永远不需要与列表上的更高地图进行比较。

- Mark Ransom

---

谢谢 - 我想过这个，但是它并没有太大帮助。我现在正在处理一个典型的情况，其中有10000个大小为3的地图和40000个大小为4的地图。所以我仍然需要进行400m次比较。比2500m次比较好，但还不够好... - rattigan

Answer 2

这里有另一种尝试。

将所有的映射分解成一个键、值、映射编号的列表。按键和值对列表进行排序。遍历列表，对于每组键/值匹配，创建所有映射编号对的排列 - 这些是所有潜在子集。当你有最终的对列表时，按映射编号排序。遍历第二个列表，并计算每个对出现的次数 - 如果数字与其中一个映射的大小相匹配，则找到了一个子集。

- Mark Ransom

---

这看起来应该能解决问题。我要编写代码并查看。好主意，马克！ - rattigan

我本来想在接受答案之前编写代码的，但还是谢谢！我应该指出这种方法在最坏情况下性能非常糟糕。我想到了一种优化方法：不用列表存储映射数字对，而是使用这些对作为键生成一个映射。每次生成一对时，增加该键处的值即可。完成后无需对结果进行排序。 - Mark Ransom

啊，你说得对 - 我现在取消了接受。我认为你所指的问题是当键/值组很大时 - 这会导致每个键/值在最坏情况下生成多达n^2对。 - rattigan

我已经添加了自己的答案，实践证明它似乎很有效。我不确定复杂度是多少，但与我的朴素解决方案相比，它需要很少的时间。感谢您指引我按值进行索引的方向。 - rattigan

Answer 3

这是我最终采取的方法。在我的情况下，它能够很好地工作，因为通常只有少数映射共享某些值。感谢Mark Ransom推动我朝这个方向发展。

简而言之：按键/值对索引映射，以便每个键/值对都与一组映射相关联。然后，对于每个映射：找到与其键/值对之一关联的最小集合；对于我的数据，该集合通常很小。该集合中的每个映射都是潜在的“超级映射”；没有其他映射可以成为“超级映射”，因为它不包含此键/值对。在该集合中搜索超级映射。最后从原始集合中删除所有已识别的子映射。

private <K, V>  void removeSubmaps(Set<Map<K, V>> maps) {
    // index the maps by key/value
    List<Map<K, V>> mapList = toList(maps);
    Map<K, Map<V, List<Integer>>> values = LazyMap.create(HashMap.class, ArrayList.class);
    for (int i = 0, uniqueRowsSize = mapList.size(); i < uniqueRowsSize; i++) {
        Map<K, V> row = mapList.get(i);
        Integer idx = i;
        for (Map.Entry<K, V> entry : row.entrySet()) 
            values.get(entry.getKey()).get(entry.getValue()).add(idx);
    }

    // find submaps
    Set<Map<K, V>> toRemove = Sets.newHashSet();
    for (Map<K, V> submap : mapList) {
        // find the smallest set of maps with a matching key/value
        List<Integer> smallestList = null;
        for (Map.Entry<K, V> entry : submap.entrySet()) {
            List<Integer> list = values.get(entry.getKey()).get(entry.getValue());
            if (smallestList  == null || list.size() < smallestList.size())
                smallestList = list;
        }

        // compare with each of the maps in that set
        for (int i : smallestList) {
            Map<K, V> map = mapList.get(i);
            if (isSubmap(submap, map))
                toRemove.add(submap);
        }
    }

    maps.removeAll(toRemove);
}

private <K,V> boolean isSubmap(Map<K, V> submap, Map<K,V> map){
    if (submap.size() >= map.size())
        return false;
    for (Map.Entry<K,V> entry : submap.entrySet()) {
        V other = map.get(entry.getKey());
        if (other == null)
            return false;
        if (!other.equals(entry.getValue()))
            return false;
    }
    return true;
}

- rattigan

---

嗯，如果你的两个地图是相同的，那么这里可能会有一个错误：我认为两者都将被删除。留给读者的练习... - rattigan

Answer 4

编辑：我最初对问题的解释是错误的，这里是基于我重新阅读问题后得出的新答案。

您可以为HashMap创建一个自定义哈希函数，该函数返回其条目的所有哈希值的乘积。对哈希值列表进行排序，并从最大值开始循环，从较小的哈希值中找到所有除数，这些是此哈希映射的可能子集，在标记它们以进行删除之前使用set.containsAll()进行确认。

这有效地将问题转化为从集合中查找可能的除数的数学问题。您可以应用所有常见的除数搜索优化。

复杂度为O(n^2)，但如果许多哈希映射是其他哈希映射的子集，则实际花费的时间可以更好，接近于最佳情况下的O(n)（如果所有哈希映射都是一个子集）。但即使在最坏的情况下，除法计算也比set.containsAll()快得多，后者本身是O(n^2)，其中n是哈希映射中项的数量。

您还可以为哈希映射条目对象创建一个简单的哈希函数，以返回较小的数字，以增加乘法/除法性能。

- Bill Yang

---

这里似乎会出现溢出问题。除法和排序都可能因为溢出而出错。使用布隆过滤器似乎可以实现类似的功能。 - rattigan

溢出可以通过为哈希映射条目创建自定义哈希函数来避免，该函数返回相对较小的数字；布隆过滤器似乎很有趣，稍微修改一下可能会更好，这是个好点子！ - Bill Yang

Answer 5

这里有一个寻找集合中极大子集的次二次算法（O(N**2 / log N)）：An Old Sub-Quadratic Algorithm for Finding Extremal Sets。

但是，如果你了解你的数据分布，你可以在平均情况下做得更好。

- Ants Aasma

---

感谢您找到此内容，看起来很相关。至少我现在知道这个算法叫什么了...不幸的是，它是一个昂贵的算法。我添加的解决方案似乎对我的数据有很好的效果。 - rattigan