"LEFT JOIN" di due diversi oggetti Java

Question

Ho un elenco di Object1 (List<Object1>) e un elenco di Object2 (List<Object2>)

• Oggetto 1 ha diverse proprietà, tra cui id
• Oggetto 2 dispone di più properites, tra cui object1id

ho un po 'di sfondo SQL e quello che sto cercando di fare è di eseguire una "sinistra join" sul

object1.id = object2.object1id

Ciò comporterebbe un List<Object3> che rappresenta l'unione sinistra. Potrei hardcode un algoritmo in Java (per ... per ...), ma sono sicuro che questo non sarebbe efficiente con almeno una complessità di n * m.

Avete una soluzione migliore? (con il codice, se possibile, grazie!)

Answer 1

Si sta cercando di fare qualcosa che Java non è davvero significava per.

Se siete in grado di farlo, si sarebbe meglio aggiungendo un attributo alla Object1, che sarebbe un elenco di Object2 contenente gli oggetti legati alla this.

Se non è possibile, abbiamo ancora la possibilità di farlo ingenuamente, altrimenti si potrebbe provare qualcosa di simile:

HashSet<Integer> hs = new HashSet<Integer>(list2.size()); 
for(Object2 o : list2) { 
    hs.add(o.object1id); 
} 
//hs contains all the ids of list2 
List<Object1> result = new ArrayList<Object1>(); //Or another class implementing List 
for(Object1 o : list1) { 
    if(hs.contains(o.id)) 
     result.add(o); 
} 

Non abbastanza, poiché è necessario memorizzare tutti gli ID di un HashSet, ma dal momento che l'aggiunta e accedere agli elementi in HashSet sono O (1) (in teoria), l'algoritmo è O (n + m)

Se la classe Object3 è costruito con un Object1 e Object2, utilizzare un HasMap invece di HashSet dove le chiavi sono id e i valori object2. L'ultima for ciclo nel codice diventerà:

Object2 o2 = hs.get(o.id); 
if(o2 != null) 
    result.add(new Object3(o, o2); 

---

A seguito di Óscar López commento:

Se l'objectid1 vostro non unico, è necessario adattare il codice come segue:

HashMap<Integer, List<Object2>> hm = new HashMap<Integer, List<Object2>>(); 
for(Object2 o : list2) { 
    List<Object2> l = hm.get(o.objectid1); 
    if(l != null) { 
     l.add(o); 
    } else { 
     List<Object2> l = new ArrayList<Object2>(); 
     l.add(o); 
     hm.put(o.objectid1, l); 
} 
//hm is map, where each entry contains the list of Object2 associated with objectid1 
List<Object1> result = new ArrayList<Object1>(); 
for(Object1 o : list1) { 
    List<Object2> l = hm.get(o.id); 
    //l contains all Object2 with object1id = o.id 
    for(Object2 o2 : l) 
     result.add(new Object3(o, o2)); 
} 

Ancora in O (n + m), ma con costanti più grandi ...

Answer 2

Se si utilizza Java 8, è possibile utilizzare streams. Potrebbe essere simile a questa (supponendo id è l'id della Object1 a guardare in alto):

List<Object3> newList = obj2List.stream().filter(x -> x.object1id == id).map(x -> obj2To3(x)).collect(Collectors.toList()); 

caso previsto è piuttosto vago, quindi è difficile dare una risposta più dettagliata.

Answer 3

credo che una soluzione O(n*m) è inevitabile, a meno che non si crea una più complessa infrastruttura di struttura dati - efficiente si unisce in un database sono implemented utilizzando indici, hash, ecc Anche tenere a mente che una corretta attuazione dovrebbe prendere in considerazione il caso dove più di un oggetto in list2 ha lo stesso object1id - il mio codice funziona in questo caso, ma tutte le soluzioni che aggiungono semplicemente obj2.object1id a Set o come chiavi in ​​un Map, non riusciranno.

Ma la complessità di implementazione vale la pena? se gli elenchi di input sono piccoli, una soluzione O(n*m) funzionerà correttamente. Ecco la mia proposta, utilizzando i buoni vecchi cicli annidati:

List<Object3> list3 = new ArrayList<>(); 
for (Object1 obj1 : list1) { 
    boolean found = false; 
    for (Object2 obj2 : list2) { 
     if (obj1.id.equals(obj2.object1id)) { 
      list3.add(new Object3(obj1, obj2)); 
      found = true; 
     } 
    } 
    if (!found) 
     list3.add(new Object3(obj1, null)); 
} 

Per quanto sopra per lavorare, sto usando un oggetto di output che assomiglia a questo:

public class Object3 { 
    private Object1 obj1; 
    private Object2 obj2; 
    public Object3(Object1 obj1, Object2 obj2) { 
     this.obj1 = obj1; 
     this.obj2 = obj2; 
    } 
} 

Answer 4

creare un indice su List. Lista Scan e compilare l'indice:

HashMap<Integer, Object2> index=HashMap<Integer, Object2>(); 
for (Object2 obj2: list2) { 
    index.put(obj2.object1id, obj2); 
} 

Quindi, eseguire la scansione del List e fare il join:

for (Object1 obj1: list1) { 
    Object2 obj2=index.get(obj1.id); // may be null 
    Object3 obj3=new Object3(obj1, obj2); 
} 

Answer 5

A condizione che implementano un'interfaccia comune (questo renderà le cose più facili, in particolare con il casting), quindi questo è relativamente semplice.

È ancora O (nm), dal momento che devi passare attraverso entrambe le lunghezze della lista per trovare gli elementi da aggiungere.

Answer 6

Una buona soluzione potrebbe essere la conversione dell'elenco di oggetti2 in una mappa. Quindi scorrere l'Elenco Oggetti1 e ottenere l'Oggetto2 dalla Mappa, creando in definitiva il join e aggiungendo il risultato nell'elenco Object3.