wake-up-neo.com

Effizienteste Methode, um festzustellen, ob eine ArrayList ein Objekt in Java enthält

Ich habe eine ArrayList von Objekten in Java. Die Objekte haben vier Felder, von denen ich zwei verwenden würde, um das Objekt als gleich zu betrachten. In Anbetracht dieser beiden Felder suche ich nach der effizientesten Methode, um festzustellen, ob das Array dieses Objekt enthält.

Der Schlüssel ist, dass diese Klassen basierend auf XSD-Objekten generiert werden, daher kann ich die Klassen selbst nicht ändern, um den .equals Zu überschreiben.

Gibt es eine bessere Möglichkeit, als nur die beiden Felder für jedes Objekt zu durchlaufen und manuell zu vergleichen und dann zu brechen, wenn sie gefunden werden? Das scheint einfach so chaotisch, auf der Suche nach einem besseren Weg.

Edit: Die ArrayList stammt aus einer SOAP Antwort, die nicht in Objekte zusammengefasst ist.

71
Parrots

Sie können einen Komparator mit den in Java integrierten Methoden zum Sortieren und zur binären Suche verwenden. Angenommen, Sie haben eine Klasse wie diese, in der a und b die Felder sind, die Sie zum Sortieren verwenden möchten:

class Thing { String a, b, c, d; }

Sie würden Ihren Komparator definieren:

Comparator<Thing> comparator = new Comparator<Thing>() {
  public int compare(Thing o1, Thing o2) {
    if (o1.a.equals(o2.a)) {
      return o1.b.compareTo(o2.b);
    }
    return o1.a.compareTo(o2.a);
  }
};

Sortieren Sie dann Ihre Liste:

Collections.sort(list, comparator);

Und zum Schluss die binäre Suche:

int i = Collections.binarySearch(list, thingToFind, comparator);
37
Fabian Steeg

In Anbetracht Ihrer Einschränkungen stecken Sie bei der Brute-Force-Suche fest (oder beim Erstellen eines Index, wenn die Suche wiederholt wird). Können Sie etwas genauer erläutern, wie ArrayList generiert wird? Vielleicht gibt es da etwas Spielraum für Wackeleffekte.

Wenn Sie nur nach schönerem Code suchen, sollten Sie die Apache Commons Collections-Klassen verwenden, insbesondere CollectionUtils.find () für vorgefertigten syntaktischen Zucker:

ArrayList haystack = // ...
final Object needleField1 = // ...
final Object needleField2 = // ...

Object found = CollectionUtils.find(haystack, new Predicate() {
   public boolean evaluate(Object input) {
      return needleField1.equals(input.field1) && 
             needleField2.equals(input.field2);
   }
});
10

Wenn die Liste sortiert ist, können Sie binäre Suche verwenden. Wenn nicht, gibt es keinen besseren Weg.

Wenn Sie dies häufig tun, lohnt es sich mit ziemlicher Sicherheit, die Liste beim ersten Mal zu sortieren. Da Sie die Klassen nicht ändern können, müssten Sie zum Sortieren und Suchen ein Comparator verwenden.

6
Michael Myers

Wenn Sie ein Benutzer von meinem ForEach DSL sind, kann dies mit einer Detect Abfrage erfolgen.

Foo foo = ...
Detect<Foo> query = Detect.from(list);
for (Detect<Foo> each: query) 
    each.yield = each.element.a == foo.a && each.element.b == foo.b;
return query.result();
4
akuhn

Selbst wenn die Methode equals were diese beiden Felder vergleicht, wäre es logischerweise nur derselbe Code, den Sie manuell ausführen. OK, es könnte "chaotisch" sein, aber es ist immer noch die richtige Antwort

4
oxbow_lakes

Gibt es eine bessere Möglichkeit, als nur die beiden Felder für jedes Objekt zu durchlaufen und manuell zu vergleichen und dann zu brechen, wenn sie gefunden werden? Das scheint einfach so chaotisch, auf der Suche nach einem besseren Weg.

Wenn Ihr Anliegen die Wartbarkeit ist, können Sie tun, was Fabian Steeg vorschlagen (das würde ich tun), obwohl es wahrscheinlich nicht das "effizienteste" ist (weil Sie zuerst das Array sortieren und dann das ausführen müssen) binäre Suche), aber sicherlich die sauberste und bessere Option.

Wenn Sie wirklich Wert auf Effizienz legen, können Sie eine benutzerdefinierte List-Implementierung erstellen, die das Feld in Ihrem Objekt als Hash verwendet und eine HashMap als Speicher verwendet. Aber wahrscheinlich wäre das zu viel.

Dann müssen Sie den Ort ändern, an dem Sie die Daten von ArrayList zu YourCustomList füllen.

Mögen:

 List list = new ArrayList();

 fillFromSoap( list );

Zu:

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

Die Implementierung würde ungefähr so ​​aussehen:

class MyCustomSpecialList extends AbstractList  { 
    private Map<Integer, YourObject> internalMap;

    public boolean add( YourObject o ) { 
         internalMap.put( o.getThatFieldYouKnow(), o );
    }

    public boolean contains( YourObject o ) { 
        return internalMap.containsKey( o.getThatFieldYouKnow() );
    }

}

Ähnlich wie bei einem HashSet besteht das Problem darin, dass das HashSet auf der guten Implementierung der hashCode-Methode beruht, die Sie wahrscheinlich nicht haben. Stattdessen verwenden Sie als Hash "das Feld, das Sie kennen", das ein Objekt gleich dem anderen macht.

Natürlich ist das Implementieren einer Liste von Grund auf schwieriger als das obige Snippet. Deshalb würde ich sagen, dass der Vorschlag Fabian Steeg besser und einfacher zu implementieren wäre (obwohl so etwas effizienter wäre).

Sagen Sie uns, was Sie am Ende getan haben.

2
OscarRyz

Vielleicht ist eine Liste nicht das, was Sie brauchen.

Vielleicht wäre ein TreeSet ein besserer Container. Sie erhalten O (log N) für das Einfügen und Abrufen sowie eine geordnete Iteration (lassen jedoch keine Duplikate zu).

LinkedHashMap ist möglicherweise sogar noch besser für Ihren Anwendungsfall, sehen Sie sich das auch an.

2
Ben Hardy

Es gibt drei grundlegende Optionen:

1) Wenn die Abrufleistung von größter Bedeutung ist und dies sinnvoll ist, verwenden Sie eine Form einer Hash-Tabelle, die einmal erstellt (und geändert wird, wenn sich die Liste ändert).

2) Wenn die Liste bequem sortiert ist oder es praktisch ist, sie zu sortieren, und das Abrufen von O (log n) ausreicht, sortieren und suchen Sie.

3) Wenn O(n) das Abrufen schnell genug ist oder wenn es unpraktisch ist, die Datenstruktur oder eine Alternative zu manipulieren/beizubehalten, iterieren Sie über die Liste.

Bevor Sie Code schreiben, der komplexer ist als eine einfache Iteration, sollten Sie sich einige Fragen überlegen.

  • Warum braucht man etwas anderes? (Zeit-) Leistung? Eleganz? Wartbarkeit? Wiederverwendung? Alle diese Gründe sind in Ordnung, getrennt oder zusammen, aber sie beeinflussen die Lösung.

  • Wie viel Kontrolle haben Sie über die betreffende Datenstruktur? Können Sie beeinflussen, wie es gebaut wird? Später gehandhabt?

  • Wie ist der Lebenszyklus der Datenstruktur (und der zugrunde liegenden Objekte)? Ist es auf einmal aufgebaut und nie verändert oder hochdynamisch? Kann Ihr Code seinen Lebenszyklus überwachen (oder sogar verändern)?

  • Gibt es andere wichtige Einschränkungen, z. B. den Speicherbedarf? Sind Informationen zu Duplikaten wichtig? Etc.

1
Jeremy Rishel

Das Erstellen einer HashMap dieser Objekte auf der Grundlage des Feldwerts als Schlüssel kann aus Sicht der Leistung sinnvoll sein, z. Füllen Sie Maps einmal und finden Sie Objekte sehr effizient

1
Rocket Surgeon

Wenn Sie häufig in derselben Liste suchen müssen, lohnt es sich möglicherweise, einen Index zu erstellen.

Durchlaufen Sie die Datei einmal und erstellen Sie eine HashMap mit dem gewünschten Wert als Schlüssel und dem entsprechenden Knoten als Wert. Wenn Sie all anstelle von nobody eines bestimmten Werts benötigen, lassen Sie die Map einen Listentyp haben und erstellen Sie die gesamte Liste in der anfänglichen Iteration.

Bitte beachten Sie, dass Sie vor dem Ausführen dieses Vorgangs eine Messung durchführen sollten, da der Overhead beim Erstellen des Index möglicherweise nur das Überqueren überschattet, bis der erwartete Knoten gefunden wurde.

Ich würde sagen, dass die einfachste Lösung darin besteht, das Objekt zu umbrechen und den Aufruf contain an eine Auflistung der umschlossenen Klasse zu delegieren. Dies ähnelt dem Komparator, erzwingt jedoch keine Sortierung der resultierenden Auflistung. Sie können einfach ArrayList.contains () verwenden.

public class Widget {
        private String name;
        private String desc;

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public String getDesc() {
            return desc;
        }

        public void setDesc(String desc) {
            this.desc = desc;
        }
    }



    public abstract class EqualsHashcodeEnforcer<T> {

        protected T wrapped;

        public T getWrappedObject() {
            return wrapped;
        }

        @Override
        public boolean equals(Object obj) {
            return equalsDelegate(obj);
        }

        @Override
        public int hashCode() {
            return hashCodeDelegate();
        }

        protected abstract boolean equalsDelegate(Object obj);

        protected abstract int hashCodeDelegate();
    }


    public class WrappedWidget extends EqualsHashcodeEnforcer<Widget> {

        @Override
        protected boolean equalsDelegate(Object obj) {
            if (obj == null) {
                return false;
            }
            if (obj == getWrappedObject()) {
                return true;
            }
            if (obj.getClass() != getWrappedObject().getClass()) {
                return false;
            }
            Widget rhs = (Widget) obj;

            return new EqualsBuilder().append(getWrappedObject().getName(),
                    rhs.getName()).append(getWrappedObject().getDesc(),
                    rhs.getDesc()).isEquals();
        }

        @Override
        protected int hashCodeDelegate() {

            return new HashCodeBuilder(121, 991).append(
                    getWrappedObject().getName()).append(
                    getWrappedObject().getDesc()).toHashCode();
        }

    }
0
jonathan.cone