如何比较记录超过10万条的两个不同的hashset对象
我有两堂课
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，任何解决方案都可以提高代码的性能。(用较少的时间)
回答 1
Software Engineering用户
发布于 2014-10-07 13: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);这个解决方案的总复杂性是O(|as| + |bs|)。换句话说，它的运行速度大约要快100,000倍。
https://softwareengineering.stackexchange.com/questions/258297
复制相似问题
腾讯云开发者
