问如何比较记录超过10万条的两个不同的hashset对象
EN

Software Engineering用户

提问于 2014-10-07 01:50:26

回答 1查看 14.8K关注 0票数 -1

我有两堂课

class A{ 
  int id; 
  String name; 
  public boolean equals(Object o)
  { 
     if(o instanceof A) {   
           A a=(A)o;
           if(a.getId().equals(this.getId()))
              return true; 
       } 
    return false;
  } 
  public int hashCode() { return id;}  
  //setter& getter 
}

class B{ 
  int id; 
  String address; 
  public boolean equals(Object o){
    if(o instanceof B)
    {
      B b=(B)o;
      if(b.getId().equals(this.getId()))
       return true;
    }
    return false;
 } 
 public int hashCode()
 { return id;} 
 //setter& getter
}

我有10万个A型对象和10万个B型对象。

因此，我已经使用HashSet消除了两个类中的重复项。现在，我将HashSet<A>和HashSet<B>与id字段进行比较，并将匹配的对象放在另一个列表中，并在主类中使用以下代码。

HashSet<A> A_Set=new HashSet<>();
HashSet<B> B_Set=new HashSet<>();
    for (A c1 : A_Set) {
            for (B c2 : B_Set) {
                if (c1.getId().equals(c2.getIid())) {
                    matchedData.add(c1);                    
                }
            }
        }

上面的代码花费了15分钟来比较100,000 records...Is，任何解决方案都可以提高代码的性能。(用较少的时间)

java

回答 1

Software Engineering用户

回答已采纳

发布于 2014-10-07 05:16:04

您有两组as和bs。您需要计算set cs，以便它包含来自set A的所有元素，这些元素的ID与set cs中的任何对象的ID相同。您目前正在使用这个嵌套循环：

Set<A> as = ...;
Set<B> bs = ...;

Set<A> cs = new HashSet<>();

for (A a : as) {
    for (B b : bs) {
        if (a.getId() == b.getId())
            cs.add(a);
    }
}

这花费了相当长的时间，因为您遍历了集合bs的所有元素。它具有算法复杂度O(|as| · |bs|)，其中|x|是集x的大小。

我们可以应用一个简单的优化:一旦在set bs中找到了匹配的元素，就可以将当前的a添加到cs中，然后继续使用as中的下一个元素。我们不会在bs中搜索进一步的匹配，因为再次添加匹配元素不会更改结果集：

for (A a : as) {
    for (B b : bs) {
        if (a.getId() == b.getId()) {
            cs.add(a);
            break;
        }
    }
}

虽然这应该会更快一些，但它仍然具有O(|as| · |xs|)复杂性。

我们可以做得更好。例如，我们可以按照所有元素的ID (一次O(n log n)成本)按升序排序，并使用跳过元素的O(n)算法迭代它们，只要它们从其他序列中跳过当前元素。这是更好的，但仍然不是最佳的。

最佳解决方案是创建bs集的ID哈希集。这不需要对这两个集合进行排序，并且允许线性时间成员资格测试.组装这组ID需要一次性的O(n)成本。

HashSet<Integer> bIds = new HashSet<>(bs.size());
for (B b : bs)
    bIDs.add(b.getId());

for (A a : as)
    if (bIds.contains(a.getId()))
        cs.add(a);