这是我最终采取的方法。在我的情况下,它能够很好地工作,因为通常只有少数映射共享某些值。感谢Mark Ransom推动我朝这个方向发展。
简而言之:按键/值对索引映射,以便每个键/值对都与一组映射相关联。然后,对于每个映射:找到与其键/值对之一关联的最小集合;对于我的数据,该集合通常很小。该集合中的每个映射都是潜在的“超级映射”;没有其他映射可以成为“超级映射”,因为它不包含此键/值对。在该集合中搜索超级映射。最后从原始集合中删除所有已识别的子映射。
private <K, V> void removeSubmaps(Set<Map<K, V>> maps) {
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);
}
Set<Map<K, V>> toRemove = Sets.newHashSet();
for (Map<K, V> submap : mapList) {
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;
}
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;
}
m
是S
的严格子集时从s
中删除m
的映射吗? - Ben S{{a: 2, b:1}, {a:1}}
应该怎么处理?{{a:1, b:1}, {a:2}}
呢?从你的例子来看,我猜测你实际上将这些映射用作集合本身。 - Svante