并集和交集的java缓慢实现
我正试图找到一种更好的方法来实现这些方法,因为在非常大的集合上,它们需要很长的时间,有什么想法吗
import java.util.HashMap;
import java.util.HashSet;
public class Multiset<E> extends HashSet<E> {
private static final long serialVersionUID = -9013417064272046980L;
private HashMap<E, Integer> multiplicities = new HashMap<E, Integer>();
@Override
public boolean add(E element){
if(multiplicities.containsKey(element)){
int x = (int) multiplicities.get(element);
multiplicities.put(element, ++x);
}else{
multiplicities.put(element, 1);
}
return super.add(element);
}
/**
* Adds all of the elements of another multiset to this one.
* This method allows the preservation of multiplicities
* which would not occur using the superclass's addAll().
* @param elements
* @return true if all elements were successfully added
*/
public boolean addAll(Multiset<E> elements) {
boolean flag = false;
for(E element : elements){
for(int i = 0; i < elements.multiplicity(element); i++)
flag = add(element);
}
return flag;
}
/**
* The set-view of a multiset is the ordinary set of all
* elements with multiplicity >= 1.
* @return all elements that have multiplicity >= 1
*/
public Multiset<E> setView(){
Multiset<E> set = new Multiset<E>();
for(E o : multiplicities.keySet()){
set.add(o);
}
return set;
}
/**
* provides a union of two multisets whereby the multiplicity of each
* element is the larger of the two
* @param second
* @return
*/
public Multiset<E> union(Multiset<E> second){
Multiset<E> union = new Multiset<E>();
Multiset<E> join = new Multiset<E>();
join.addAll(this);
join.addAll(second);
for(E o : join){
int i = this.multiplicity(o);
int j = second.multiplicity(o);
i = i > j ? i : j;
for(int c = 0; c < i; c++){
union.add(o);
}
}
return union;
}
/**
* provides an intersection of two multisets whereby
* the multiplicity of each element is the smaller of the two
* @param second
* @return The multiset containing the intersection of two multisets
*/
public Multiset<E> intersect(Multiset<E> second){
Multiset<E> intersection = new Multiset<E>();
for(E o : this.setView()){
if (second.setView().contains(o)) {
int i = this.multiplicity(o);
int j = second.multiplicity(o);
i = i < j ? i : j;
for(int c = 0; c < i; c++){
intersection.add(o);
}
}
}
return intersection;
}
/**
* The Multiplicity is the number of occurrences of an object
* in the multiset
* @param o
* @return number of occurrences of o
*/
public int multiplicity(E o){
return (multiplicities.containsKey(o)) ? multiplicities.get(o) : 0;
}
public int cardinality(){
int card = 0;
for(Integer i : multiplicities.values()){
card += i;
}
return card;
}
/**
* Measures the similarity between two multisets
* @param A
* @param B
* @return the cardinality of the difference of A and B
*/
public int similarityOfMultisets(Multiset<E> second){
Multiset<E> union, intersection;
int difference;
union = union(second);
intersection = intersect(second);
difference = union.cardinality() - intersection.cardinality();
return difference;
}
}
编辑:
我相信我已经找到了一种更快的方法来计算多重集方法的相似性:
public int similarityOfMultisets(Multiset<E> second){
int c = 0;
for(E elem: this.setView()){
c += Math.min(this.multiplicity(elem), second.multiplicity(elem));
}
Multiset<E> union = this.union(second);
return union.cardinality() - c;
}
# 1 楼答案
下面是该类的重构。不一定更快——除了不在循环中重新运行setView()——但在某些方面可能更干净。FWIW
# 2 楼答案
我不明白setView方法的目的。。。看起来你只是在返回你自己的一个副本,但是每个密钥的多重性都设置为1
对于union,请尝试以下内容(可能无法编译):
# 3 楼答案
我认为问题是你在调用第二个。setView()-重新创建该集合-用于此集合中的每个元素。setView()。试试这个:
# 4 楼答案
我们算法的第一个变量的性能测试结果:
卡尔的联盟打败了我的联盟
测试代码here。不过,我没有验证计算结果的正确性
测试代码2的各种集合大小和方差here(JDK 7b59)。结果xslx/ods
# 5 楼答案
这就是我提出的G-C:
结果:
没有基准。 看来,你的基数可以用两次而不是三次遍历来计算