Union和Intersection实现缓慢

Question

我正在尝试找到一种更好的方法来实现这些方法，因为对于非常大的集合，它们需要非常长的时间，你有什么想法吗？

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;

}
}

编辑：

我相信我已经找到了一种更快的方法来计算similarityOfMultisets方法：

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;     
}

Answer 1

下面是类的重构。不一定更快-除了不在循环中重新运行setView() -但在某些方面可能更干净。FWIW。

import java.util.HashMap;
import java.util.HashSet;

public class Multiset<E> extends HashSet<E> {
    private static final long           serialVersionUID    = -9013417064272046980L;
    private final HashMap<E, Integer>   multiplicities      = new HashMap<E, Integer>();

    public boolean add(E element) {
        return add(element, 1);
    }

    private boolean add(E element, int copies) {
        if (!contains(element))
            multiplicities.put(element, 0);
        int n = multiplicities.get(element);
        multiplicities.put(element, n + copies);
        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 that
     * @return true if all elements were successfully added
     */
    public boolean addAll(Multiset<E> that) {
        boolean flag = false;
        for (E element : that)
            flag = add(element, that.multiplicity(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 that
     * @return
     */
    public Multiset<E> union(Multiset<E> that) {
        HashSet<E> both = new HashSet<E>();
        both.addAll(this);
        both.addAll(that);
        Multiset<E> union = new Multiset<E>();
        for (E element : both)
            union.add(element, Math.max(this.multiplicity(element), that.multiplicity(element)));
        return union;
    }

    /**
     * provides an intersection of two multisets whereby the multiplicity of each element is the smaller of the two
     * 
     * @param that
     * @return The multiset containing the intersection of two multisets
     */
    public Multiset<E> intersect(Multiset<E> that) {
        Multiset<E> intersection = new Multiset<E>();
        final Multiset<E> other = that.setView();
        for (E element : this.setView())
            if (other.contains(element))
                intersection.add(element, Math.min(this.multiplicity(element), that.multiplicity(element)));
        return intersection;
    }

    /**
     * The Multiplicity is the number of occurrences of an object in the multiset
     * 
     * @param element
     * @return number of occurrences of o
     */
    public int multiplicity(E element) {
        return contains(element) ? multiplicities.get(element) : 0;
    }

    public int cardinality() {
        int card = 0;
        for (Integer n : multiplicities.values())
            card += n;
        return card;
    }

    /**
     * Measures the similarity between two multisets
     * 
     * @param that
     * @return the cardinality of the difference of A and B
     */
    public int similarityOfMultisets(Multiset<E> that) {
        return union(that).cardinality() - intersect(that).cardinality();
    }
}

Answer 2

我不明白setView method...seems的用途，就像您只是返回自己的一个副本，但是每个键的重数都设置为1。

对于联合尝试，这可能(可能不会编译)：

public Multiset<E> union(Multiset<E> second) {
    Multiset<E> union = new Multiset<E>();
    union.addAll(this);
    union.addAll(second);

    for(E o : union){
        int multiplicity = Math.max (this.multiplicity(o), second.multiplicity(o));
        union.multiplicities.put (o, multiplicity);
    }

    return union;
}

Answer 3

我认为问题在于您正在为this.setView()中的每个元素调用second.setView() -重新创建set。试着这样做：

/**
 * 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>();
    Set<E> other = second.setView();
    for(E o : this.setView()){
        if (other.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;        
}