"LEFT JOIN" von zwei verschiedenen Java-Objekte

Question

Ich habe eine Liste von Object1 (List<Object1>) und eine Liste von Object2 (List<Object2>)

• Objekt 1 mehrere Eigenschaften, einschließlich id
• Objekt 2 hat mehrere properites, einschließlich object1id

ich einige SQL Hintergrund haben und was ich versuche zu tun, auf einem „LEFT JOIN“ auszuführen

object1.id = object2.object1id

in einem List<Object3> Dies würde dazu führen, dass die linke darstellt verbinden. Ich könnte einen Algorithmus in Java fest codieren (für ... für ...), aber ich bin mir sicher, dass dies mit einer Komplexität von n * m nicht effizient wäre.

Haben Sie eine bessere Lösung? (mit Code, wenn möglich, danke!)

Answer 1

Sie versuchen, etwas zu tun, dass Java nicht wirklich gemeint für.

Wenn Sie in der Lage sind, es zu tun, würden Sie besser dran Hinzufügen eines Attributs zu Object1, die eine Liste von Object2 sein würde, die Objekte im Zusammenhang mit this enthält.

Wenn Sie nicht, wir haben immer noch die Möglichkeit, es naiv zu tun, sonst könnte man so etwas versuchen:

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

Nicht schön, da Sie alle IDs in einem HashSet zu speichern, aber da das Hinzufügen und Elemente in HashSet ist O (1) (theoretisch), der Algorithmus ist O (n + m)

Wenn Object3 Klasse konstruiert ist mit einem Object1 und Object2, verwenden Sie eine HasMap anstelle von HashSet wo der Schlüssel Zugriff sind IDs und die Werte object2. Die letzte for Schleife im Code werden:

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

---

Weitere zu Óscar López Kommentar:

Wenn Ihr objectid1 Ihr nicht eindeutig zuzuordnen, müssen Sie den Code anzupassen, wie folgt:

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

Noch in O (n + m), aber mit größeren Konstanten ...

Answer 2

Wenn Sie Java 8 verwenden, können Sie streams nutzen. Es könnte wie folgt aussehen (id vorausgesetzt, ist die ID des Object1 zu sehen):

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

Der zur Verfügung gestellte Fall ist ziemlich vage, so ist es schwer, eine ausführlichere Antwort zu geben.

Answer 3

Ich glaube, eine O(n*m) Lösung unvermeidlich ist, es sei denn, eine komplexere Datenstruktur Infrastruktur geschaffen - effizient verbindet in einer Datenbank implemented Verwendung von Indizes, Hashes usw. bedenken Sie auch, dass eine korrekte Umsetzung der Fall betrachtet werden sollte wo mehr als ein Objekt in list2 hat die gleiche object1id - mein Code funktioniert in diesem Fall, aber alle Lösungen, die einfach obj2.object1id zu einem Set oder als Schlüssel in einem Map hinzufügen, werden fehlschlagen.

Aber lohnt sich die Komplexität der Implementierung? Wenn die Eingabelisten klein sind, wird eine O(n*m) Lösung gut funktionieren. Hier ist mein Vorschlag, mit guter alter verschachtelter Schleife:

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

Für die oben zu arbeiten, ich bin mit einem Output-Objekt, das wie folgt aussieht:

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

Answer 4

einen Index auf Liste erstellen. Scan-Liste und füllen Sie den Index:

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

Dann scannen Sie die Liste und machen die Verbindung:

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

Answer 5

Vorausgesetzt, dass Sie implementieren eine gemeinsame Schnittstelle (dies wird die Dinge vereinfachen, insbesondere beim Casting), dann ist das relativ einfach.

Es ist immer noch O (nm), da Sie beide Längen der Liste durchgehen müssen, um Elemente zum Hinzufügen zu finden.

public interface JoinInterface { 
    int getId(); 
    int getObject1Id(); // likely baggage here 
} 


public static List<? extends JoinableEntity> leftJoin(List<? extends JoinableEntity> left, 
               List<? extends JoinableEntity> right) { 
    List<JoinableEntity> result = new ArrayList<>(); 

    result.addAll(left); 
    for(JoinableEntity aLeft : left) { 
     for(JoinableEntity aRight : right) { 
      if(aLeft.getId() == aRight.getObject1Id()) { 
       result.add(aRight); 
       break; 
      } 
     } 
    } 

    return result; 
} 

Answer 6

Eine gute Lösung könnte die Liste von Object2 in eine Map konvertieren. Führen Sie dann eine Iteration durch die Objekt1-Liste durch, und rufen Sie das Objekt2 aus Map ab, wobei Sie schließlich das Join-Objekt und das Ergebnis in der Objekt3-Liste erstellen.