Wie vergleicht man am besten zwei Sammlungen in Java und handelt entsprechend?

Question

Ich habe zwei Sammlungen desselben Objekts, Collection oldSet und Collection newSet. Die erforderliche Logik lautet wie folgt:

• wenn foo in oldSet ist, aber nicht in newSet, rufe doRemove(foo) auf
• oder wenn foo nicht in oldSet ist, aber in newSet, rufe doAdd(foo) auf
• oder wenn foo in beiden Sammlungen ist, aber geändert, rufe doUpdate(oldFoo, newFoo) auf
• oder wenn !foo.activated && foo.startDate >= now, rufe doStart(foo) auf
• oder wenn foo.activated && foo.endDate <= now, rufe doEnd(foo) auf

(*) "in" bedeutet, dass der eindeutige Bezeichner übereinstimmt, nicht unbedingt der Inhalt.

Der aktuelle (legacy) Code führt viele Vergleiche durch, um removeSet, addSet, updateSet, startSet und endSet zu ermitteln und dann iteriert und auf jedes Element angewendet.

Der Code ist ziemlich unübersichtlich (teilweise, weil ich bereits einige Spaghetti-Logik weggelassen habe) und ich versuche, ihn zu überarbeiten. Einige zusätzliche Hintergrundinformationen:

• Soweit ich weiß, werden die oldSet und newSet tatsächlich von ArrayList unterstützt
• Jede Sammlung enthält weniger als 100 Elemente, höchstwahrscheinlich maximal 20
• Dieser Code wird häufig aufgerufen (in Millionen/Tag gemessen), obwohl sich die Sets selten unterscheiden

Meine Fragen:

• Wenn ich oldSet und newSet in HashMap umwandele (die Reihenfolge ist hier nicht relevant), würde der Code dann leichter lesbar und einfacher vergleichbar sein? Wie viel Zeit- und Speicherleistung geht durch die Konvertierung verloren?
• Wäre es effizienter und prägnanter, die beiden Sets zu durchlaufen und die entsprechenden Operationen durchzuführen?

Answer 1

Die Apache commons.collections-Bibliothek verfügt über eine CollectionUtils-Klasse, die benutzerfreundliche Methoden für die Manipulation/Überprüfung von Sammlungen bereitstellt, wie z.B. Schnittmenge, Differenz und Vereinigung.

Die org.apache.commons.collections.CollectionUtils-API-Dokumentation finden Sie hier.

Answer 2

Sie können Java 8-Streams verwenden, zum Beispiel

set1.stream().filter(s -> set2.contains(s)).collect(Collectors.toSet());

oder die Sets-Klasse von Guava:

Set intersection = Sets.intersection(set1, set2);
Set difference = Sets.difference(set1, set2);
Set symmetricDifference = Sets.symmetricDifference(set1, set2);
Set union = Sets.union(set1, set2);

Answer 3

Ich habe eine Approximation dessen erstellt, was ich denke, dass du suchst, nur unter Verwendung des Collections-Frameworks in Java. Ehrlich gesagt denke ich, dass es wahrscheinlich überdimensioniert ist, wie @ Mike Deck bemerkt. Für eine so kleine Menge von Elementen zum Vergleichen und Verarbeiten denke ich, dass Arrays aus prozeduraler Sicht eine bessere Wahl wären, aber hier ist meine Pseudocode-Lösung (weil ich faul bin). Ich gehe davon aus, dass die Foo-Klasse auf der Basis ihrer eindeutigen ID vergleichbar ist und nicht auf allen Daten in ihrem Inhalt:

Collection oldSet = ...;
Collection newSet = ...;

private Collection difference(Collection a, Collection b) {
    Collection result = a.clone();
    result.removeAll(b)
    return result;
}

private Collection intersection(Collection a, Collection b) {
    Collection result = a.clone();
    result.retainAll(b)
    return result;
}

public doWork() {
    // Wenn foo in oldSet, aber nicht in newSet ist, rufe doRemove(foo) auf
    Collection removed = difference(oldSet, newSet);
    if (!removed.isEmpty()) {
        loop removed {
            Foo foo = removedIter.next();
            doRemove(foo);
        }
    }
    // andernfalls, wenn foo nicht in oldSet, aber in newSet ist, rufe doAdd(foo) auf
    Collection added = difference(newSet, oldSet);
    if (!added.isEmpty()) {
        loop added  {
            Foo foo = addedIter.next();
            doAdd(foo);
        }
    }

    // ansonsten, wenn foo in beiden Sammlungen ist aber modifiziert, rufe doUpdate(oldFoo, newFoo) auf
    Collection matched = intersection(oldSet, newSet);
    Comparator comp = new Comparator() {
        int compare(Object o1, Object o2) {
            Foo f1, f2;
            if (o1 instanceof Foo) f1 = (Foo)o1;
            if (o2 instanceof Foo) f2 = (Foo)o2;
            return f1.activated == f2.activated ? f1.startdate.compareTo(f2.startdate) == 0 ? ... : f1.startdate.compareTo(f2.startdate) : f1.activated ? 1 : 0;
        }

        boolean equals(Object o) {
             // Gleich diesem Comparator .. nicht verwendet
        }
    }
    loop matched {
        Foo foo = matchedIter.next();
        Foo oldFoo = oldSet.get(foo);
        Foo newFoo = newSet.get(foo);
        if (comp.compareTo(oldFoo, newFoo ) != 0) {
            doUpdate(oldFoo, newFoo);
        } else {
            // sonst wenn !foo.activated && foo.startDate >= now, rufe doStart(foo) auf
            if (!foo.activated && foo.startDate >= now) doStart(foo);

            // sonst wenn foo.activated && foo.endDate <= now, rufe doEnd(foo) auf
            if (foo.activated && foo.endDate <= now) doEnd(foo);
        }
    }
}

In Bezug auf deine Fragen: Wenn ich oldSet und newSet in HashMaps umwandele (Reihenfolge ist hier nicht wichtig), mit den IDs als Schlüssel, würde es den Code lesbarer und einfacher vergleichbar machen? Wie viel Zeit und Speicherleistung geht bei der Konvertierung verloren? Ich denke, dass du den Code wahrscheinlich lesbarer machen würdest, indem du eine Map benutzt, ABER... du würdest wahrscheinlich mehr Speicher und Zeit während der Konvertierung verwenden.

Wäre es effizienter und prägnanter, die beiden Sets zu durchlaufen und die entsprechende Operation durchzuführen? Ja, dies wäre das Beste aus beiden Welten, insbesondere wenn du dem Rat von @Mike Sharek folgst und deine eigene Liste mit spezialisierten Methoden erstellst oder etwas wie das Visitor Design Pattern verwendest, um deine Sammlung durchzugehen und jedes Element zu verarbeiten.

Answer 4

Ich denke, der einfachste Weg, das zu tun, ist die Verwendung der Apache Collections API - CollectionUtils.subtract(list1, list2), solange die Listen vom gleichen Typ sind.

Answer 5

Ich würde zu Listen wechseln und es auf diese Weise lösen:

1. Sortiere beide Listen nach aufsteigender ID mithilfe eines benutzerdefinierten Comparator, wenn Objekte in den Listen nicht Comparable sind
2. Iteriere über Elemente in beiden Listen wie in der Einfügephase im Mergesort-Algorithmus, aber anstatt Listen zusammenzuführen, überprüfst du deine Logik.

Der Code würde in etwa so aussehen:

/* Hauptmethode */
private void execute(Collection oldSet, Collection newSet) {
  List oldList = asSortedList(oldSet);
  List newList = asSortedList(newSet);

  int oldIndex = 0;
  int newIndex = 0;
  // Iteriere über beide Sammlungen, aber nicht immer im selben Tempo
  while( oldIndex < oldList.size() 
      && newIndex < newIndex.size())  {
    Foo oldObject = oldList.get(oldIndex);
    Foo newObject = newList.get(newIndex);

    // Deine Logik hier
    if(oldObject.getId() < newObject.getId()) {
      doRemove(oldObject);
      oldIndex++;
    } else if( oldObject.getId() > newObject.getId() ) {
      doAdd(newObject);
      newIndex++;
    } else if( oldObject.getId() == newObject.getId() 
            && isModified(oldObject, newObject) ) {
      doUpdate(oldObject, newObject);
      oldIndex++;
      newIndex++;
    } else {
      ... 
    }
  }// während

  // Überprüfe, ob noch Objekte in *oldList* oder *newList* übrig sind

  for(; oldIndex < oldList.size(); oldIndex++ ) {
    doRemove( oldList.get(oldIndex) );  
  }// für( oldIndex )

  for(; newIndex < newList.size(); newIndex++ ) {
    doAdd( newList.get(newIndex) );
  }// für( newIndex ) 
}// execute( oldSet, newSet )

/** Erstelle sortierte Liste aus Sammlung 
    Wenn du tatsächlich Aktionen auf den Eingabesammlungen durchführst, solltest du 
    immer eine neue Instanz der Liste zurückgeben, um den Algorithmus einfach zu halten.
*/
private List asSortedList(Collection data) {
  List resultList;
  if(data instanceof List) {
     resultList = (List)data;
  } else {
     resultList = new ArrayList(data);
  }
  Collections.sort(resultList)
  return resultList;
}