медленная реализация объединения и пересечения

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;

}
}

EDIT:

Полагаю, я нашел более быстрый способ вычисления метода 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

Результат теста производительности для первых вариантов наших алгоритмов:

Robert-Union: 2263374 us
Robert-Intersection: 603134 us
Robert-Similarity: 2926389 us
Carl-Union: 3372 us
Carl-Intersection: 5097 us
Carl-Similarity: 6913 us
David-Union: 5182 us
David-Intersection: 2527 us
David-Similarity: 5270 us

Союз Карла побеждает мой союз.

Тестовый код здесь . Хотя я не проверил правильность результатов вычислений.

Тестовый код 2 для различных установленных размеров и отклонений здесь (JDK 7b59). Результаты xslx / ods .

Answer 2

Вот рефакторинг класса. Не обязательно быстрее - за исключением не повторного запуска 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 3

Я не понимаю цели метода setView ... кажется, что вы просто возвращаете свою копию, но с кратностью, установленной на 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 4

Я думаю, проблема в том, что вы вызываете second.setView () - воссоздаете этот набор - для каждого элемента в this.setView (). Попробуйте вместо этого:

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

Answer 5

Вот что я придумал G-C:

import com.google.common.collect.Multiset;
import com.google.common.collect.Multisets;
import com.google.common.collect.Multiset.Entry;
public class MultisetOp {
    public static void main(String[] args) {
        Multiset<Integer> ms1 = Multisets.newHashMultiset(1, 1, 2, 3, 4, 4, 4);
        Multiset<Integer> ms2 = Multisets.newHashMultiset(1, 2, 3, 3,
            4, 5, 5, 5);
        Multiset<Integer> mu = Multisets.newHashMultiset();
        Multiset<Integer> mi = Multisets.newHashMultiset();
        // -------- UNION START -----------
        for (Entry<Integer> e : ms1.entrySet()) {
            int j = ms2.count(e.getElement());
            mu.add(e.getElement(), Math.max(e.getCount(), j));
        }
        for (Entry<Integer> e : ms2.entrySet()) {
            int j = ms1.count(e.getElement());
            if (j == 0) {
                mu.add(e.getElement(), e.getCount());
            }
        }
        // -------- UNION END -----------

        // -------- INTERSECT START -----------
        for (Entry<Integer> e : ms1.entrySet()) {
            int j = ms2.count(e.getElement());
            if (j > 0) {
                mi.add(e.getElement(), Math.min(e.getCount(), j));
            }
        }
        // -------- INTERSECT END -----------

        System.out.printf("Union: %s%n", mu);
        System.out.printf("Intersection: %s%n", mi);
        System.out.printf("Cardinality: %d%n", mu.size() - mi.size());

    }
}

Результат:

[1 x 2, 2, 3 x 2, 4 x 3, 5 x 3]
[1, 2, 3, 4]

Не тестируется. Кажется, ваша мощность может быть вычислена с двумя обходами вместо трех.