Come confrontare due diversi oggetti hashset con oltre 100.000 record

Question

Come confrontare due diversi oggetti hashset con oltre 100.000 record

#1 da (6 voti)

-1

Ho due classi

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
}

Ho 100.000 oggetti di tipo A e 100.000 oggetti di tipo B.

Così, ho eliminato i duplicati in entrambe le classi usando HashSet. Ora sto confrontando HashSet<A> e HashSet<B> con il campo id e collochi gli oggetti con corrispondenza in un altro elenco con il seguente codice nella classe principale ..

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

il codice precedente impiega 15 minuti per confrontare 100.000 record ... Esiste una soluzione per aumentare le prestazioni del codice .. (con in meno tempo)

java

posta sekhar 07.10.2014 - 11:50

fonte

1 risposta

Leggi altre domande sui tag java

Quando diciamo che una variabile non è definita? [chiuso] Sarebbe possibile creare un linguaggio simile a Ruby / Python con una tipizzazione statica che abbia l'utilizzo di velocità / memoria di un programma C compilato? [chiuso]

score 6 · Accepted Answer

Hai due set as e bs . Si vuole calcolare il set cs tale che contenga tutti gli elementi dal set A che hanno un ID uguale a quello di qualsiasi oggetto nel set cs . Stai utilizzando questo ciclo annidato:

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

Questo richiede un po 'di tempo perché fai un loop di tutti gli elementi del set bs . Ha una complessità algoritmica O(|as| · |bs|) , dove |x| è la dimensione del set x .

Potremmo applicare una semplice ottimizzazione: una volta trovato un elemento corrispondente nel set bs , aggiungiamo la corrente a a cs e continuiamo con l'elemento successivo da as . Non cerchiamo ulteriori corrispondenze in bs , poiché aggiungere nuovamente un elemento corrispondente non modifica il set di risultati:

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

Anche se questo dovrebbe essere un po 'più veloce, questo ha ancora O(|as| · |xs|) complessità.

Possiamo fare di meglio. Ad esempio, potremmo ordinare tutti gli elementi in base al loro ID (costo di una volta O(n log n) ) in ordine ascendente e iterare su di essi utilizzando un algoritmo O(n) che salta gli elementi fintanto che sono più grandi dell'elemento corrente dal altra sequenza. Questo è meglio, ma non è ancora ottimale.

La soluzione ottimale è creare un set hash di ID del set bs . Ciò non richiede l'ordinamento di entrambi gli insiemi e consente il test di appartenenza a tempo lineare. Esiste un costo percentuale pari a% co_de per assemblare il set di ID.

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

La complessità totale di questa soluzione è O(n) . In altre parole, dovrebbe essere eseguito circa 100.000 volte più velocemente.