快速检查两个集合是否至少包含一个相同元素的方法

3

我有两个TreeMaps,想要检查它们是否至少包含一个相同的键(键为字符串)。因此我使用了两个循环进行比较:

boolean found = false;
for(String key1 : map1.keySet()){
    for(String key2 : map2.keySet()){
        if(key1.equals(key2)){
            found = true;
            break;
        }
    }
    if(found){
        break;
    }
}
if(found){
    someFunction(map1, map2);
}

我有500,000个TreeMaps(每个Map大约有1000个键),我想检查每个Map与其他Map是否相同,这需要很长时间。有没有人知道更快的解决方案?

*编辑:每当我找到两个至少有一个相同键的Map时,我想调用“someFunction()”方法。我认为在90%以上的情况下,“found == false”。


1
map.containsKey()方法也可以。 - Shoaib Chikate
1
所以你想知道那些500k个地图中有没有至少一个共同的键?还是只要知道是否存在这样的地图?在最坏情况下,你期望有多少个不同的键,可能是5亿个吗? - Thomas
你怎么修改回答他的第一个问题?我觉得我没明白。 - kai
Thomas, kai: 哎呀,我不擅长用英语解释 =/ 再详细一点:我有一个包含500k个地图的地图(每个地图有1k个键)。对于每两个至少有一个共享键的地图,我想调用一个函数。 - Munchkin
既然你接受了我的答案,我就假设你使用了那种方法或类似的方法。能否提供一些关于加速效果的细节呢?这真的很有趣。 :) - Thomas
显示剩余4条评论
3个回答

5

有一种方法可以尝试,就是创建一个键->映射的多重映射,即遍历所有500k个映射,并将它们添加到它们包含的每个键中。

然后再次遍历键,如果一个键有两个或更多的映射,则这些映射共享该键。

采用这种方法,复杂度应该从O(n² * m)降至O(n * m) (n是映射的数量,m是键的数量)。

大致概述:

Multimap<Key, Map<Key, Value>> mapsContainingKey = ... ;//could be a Guava Multimap
//O(n * m) complexity
for(Map<Key, Value> m : largeSetOfTreeMaps ) {
  for(Key k : m.keySet() ) {
    mapsContainingKey.put( k, m );
  }
}

//O(m)
for( Entry<Key, Map<Key, Value>> entry : mapsContainingKey.entries() ) {
  Key key = entry.getKey();
  Collection<Map<Key, Value>> mapsWithSameKey = entry.getValue();
  if( mapsWithSameKey.size() > 1 ) {
    //all maps in that collection share this key
  }
}

更新: 我进行了快速基准测试,虽然它并没有经过优化,但有一个明显的趋势:

"天真"的方法是循环遍历所有地图,并检查所有后续地图,以便每对只被检查一次。此外,我应用了Holger建议用于比较两个地图的方法。

"Map"方法就是我在这里发布的方法。

我的机器上对1000张地图进行测试,每张地图都有100个长度为10的随机字符串键:

naive: 11656 ms
map:     235 ms

更新2: 不同大小的一些结果:

1000张地图,每张地图有100个不同长度的键(键越长,碰撞越少)。

key length   1        2         3         4         5        10        20
naive      417 ms  3221 ms  10937 ms  11273 ms  11357 ms  11383 ms  11706 ms
map         16 ms    43 ms     86 ms    224 ms    245 ms    210 ms    154 ms

有1000张地图,每张地图上的键数量和键长都不同(键越多,冲突越多)。

key count    50       100       500
naive      4865 ms  11368 ms  81280 ms 
map          64 ms    206 ms    913 ms

不同数量的地图,每个地图有1000个长度为10的键(地图越多,冲突越多)

map count    500     1000      2000
naive      6323 ms  12766 ms  47798 ms 
map         139 ms    206 ms    333 ms

正如您所看到的,地图的数量对此产生的影响最大,其次是键的数量。


2

您没有提到排序的问题,但我假设所有的TreeMap都有相同的排序方式。在这种情况下,您可以通过使用第二个映射的边界来减少外层迭代范围。您的内部迭代完全是不必要的,因为您可以简单地询问该映射是否包含该键。

for(String s: map1.navigableKeySet().subSet(map2.firstKey(), true, map2.lastKey(), true)) {
    if(map2.containsKey(s)) {
        someFunction(map1, map2);
        break;
    }
}

说明:

假设您有以下地图键:

map2:    D, E, F, G, H
         |           |
       first        last
map1: A,    E,    G,   I
            |<--->|
          subset("D", true, "H", true)

这里,map2 的第一个元素是 "D",最后一个元素是 "H"。当将这些元素作为 map1 的 navigableKeySet().subSet(…) 方法的包含边界时,我们将得到最接近的内部集合 ["E", "G"] 作为搜索范围,因此在进行线性搜索之前,我们已经排除了 "A""I"(请记住,这些仅是示例占位符,它们可能代表大量的键)。
通过更深入地思考,您可以在比较两个映射时跳过任意范围:
public static boolean haveCommonKeys(TreeMap<String,?> map1, TreeMap<String,?> map2) {
    if(map1.isEmpty()) return false;
    for(String s=map1.firstKey(); s!=null; ) {
        String s2=map2.ceilingKey(s);
        if(s2==null) break;
        if(s2.equals(s)) return true;
        s=map1.ceilingKey(s2);
        if(s2.equals(s)) return true;
    }
    return false;
}

在这个解决方案中,我们从地图的第一个(最小的)键开始,并要求每个地图提供一个与在其他地图中找到的值相同或更大的键。这样,我们将跳过另一个地图不包含中间键的所有连续键。请注意保留HTML标签。

你能解释一下第一行代码吗?为什么它比for(String s: map1.keySet())更好? - Munchkin
它跳过第二个映射的第一个元素之前(小于)的所有元素,以及第二个映射的最后一个元素之后(大于)的所有元素,因为这些元素不能出现在第二个映射中。根据第一个和最后一个元素的实际值,这可能意味着很大的节省。 - Holger

0
创建一个包含每个键的对象集合的地图。如果您在键上调用getter方法,您将获得对象的集合。如果您在此集合上调用size()方法,您将知道是否有多个对象映射到该键。但是,您不应该将所有数据放在一个地图中,因为这会严重减慢速度。最好是对键进行排序,如果可以的话。例如,将所有由数字组成的键放在一个地图中,将所有由字母组成的键放在另一个地图中,将其余的键放在第三个地图中。然后,您可以检查键,获取与之相关的地图,并与之一起工作。就像这样:
public class MyMap{

private Map<String key, Set<Object>> stuff;

 public MyMap(){
  stuff = new HashMap<String key, Set<Object>>(); // Or any other map instead of HashMap
 }

 public void put(final String pKey, final Object pObject){
  Set<Object> objects = stuff.get(pKey);
  if(objects!=null)
   objects.add(pObject);
  else{
   Set<Object> objects = new HashSet<Object>();
   objects.add(pObject);
   stuff.put(pKey, objects);
  }
 }

 public Set<Object> get(String pKey){
  return stuff.get(pKey);
 }

 public void remove(String pKey){
  stuff.remove(pKey);
 }

}

但要小心,如果你有很多地图,这确实会影响你的性能。你必须分割键来加快速度 :) 你也可以使用任何其他的地图/集合。我使用了 HashSet,因为我认为如果你想进行检查这样的操作,你不希望将相同的对象两次添加到同一个键中。

希望我能帮到你 :)


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接