Effizienteste Weg, um zu sehen, ob eine Arraylist ein Objekt in Java enthält

StackOverflow https://stackoverflow.com/questions/558978

Frage

Ich habe eine Arraylist von Objekten in Java. Die Objekte haben vier Felder, von denen zwei ich würde das Objekt gleich einem anderen zu betrachten. Ich bin für die effizienteste Art und Weise suchen, da diese beiden Felder, um zu sehen, ob das Array, das Objekt enthält.

Der Schlüssel ist, dass diese Klassen basierend auf XSD-Objekte erzeugt werden, also kann ich die Klassen selbst nicht ändern Sie die .equals zu überschreiben.

Gibt es einen besseren Weg, als nur durch Schleifen und manuell die beiden Felder für jedes Objekt zu vergleichen und dann, wenn gefunden zu brechen? Das scheint nur so chaotisch, nach einem besseren Weg suchen.

Edit:. die Arraylist stammt aus einer SOAP-Antwort, die in Objekte entordnet ist

War es hilfreich?

Lösung

Es hängt davon ab, wie effizient Sie brauchen, um Dinge zu sein. Einfach über die Liste iterieren für das Element suchen, die eine bestimmte Bedingung erfüllt ist O (n), aber so ist ArrayList.Contains, wenn Sie die Equals-Methode implementieren könnte. Wenn Sie nicht diese in Schleifen oder inneren Schleifen dieser Ansatz zu tun ist wahrscheinlich gut.

Wenn Sie wirklich sehr effizient Nachschau benötigen Geschwindigkeiten an allen Kosten, müssen Sie zwei Dinge tun:

  1. Arbeits um die Tatsache, dass die Klasse erzeugt wird: eine Adapterklasse schreiben, kann die erzeugte Klasse wickeln und die Umsetzung (gleich) Based auf diese beiden Bereiche (vorausgesetzt, sie Öffentlichkeit ist). Vergessen Sie nicht, auch implementieren hashCode () (*)
  2. Wrap jedes Objekt mit diesem Adapter und steckt es in einer HashSet. HashSet.contains ( ) hat konstante Zugriffszeit, das heißt O (1) anstelle von O (n).

Natürlich Bau dieses HashSet hat noch eine O (n) Kosten. Sie werden nur etwas gewinnen, wenn die Kosten für die HashSet des Gebäudes vernachlässigbar auf die Gesamtkosten aller enthält () prüft, verglichen wird, die Sie tun müssen. Der Versuch, eine Liste ohne Duplikate zu bauen, ist ein solcher Fall.

* () Implementierung von hashCode () wird am besten durch XOR-Verknüpfung (Operator ^) die Hashcodes der gleichen Felder, die Sie für die Gleiche Implementierung verwenden (aber multiplizieren mit 31 der Möglichkeit des XOR zu reduzieren wodurch man 0)

Andere Tipps

Sie könnten einen Komparator mit Java integrierten Methoden zum Sortieren und binäre Suche verwenden. Angenommen, Sie eine Klasse wie dieses haben, wobei a und b sind die Felder, die Sie für das Sortieren verwenden möchten: 

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

Sie würden definieren Ihren Vergleicher: 

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

Dann sortieren Sie Ihre Liste: 

Collections.sort(list, comparator);

Und tun schließlich die binäre Suche: 

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

Ihre Einschränkungen gegeben, sind Sie mit Brute-Force-Suche (oder das Erstellen eines Index, wenn die Suche wiederholt wird) fest. Können Sie jede auf erarbeiten, wie die ArrayList erzeugt wird -. Vielleicht gibt wenig Spielraum gibt es

Wenn alle Sie suchen ist schönere Code, sollten Sie die Apache Commons Collections-Klassen, insbesondere CollectionUtils.find () , für fertige syntaktische 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);
   }
});

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

Wenn Sie dies tun viel, wäre es fast sicher sein lohnt sich die Liste zum ersten Mal zu sortieren. Da Sie die Klassen nicht ändern können, würden Sie eine Comparator die Sortierung zu tun und zu suchen.

Auch wenn die Methode equals wurden diese beiden Felder zu vergleichen, dann logisch wäre es nur der gleiche Code, wie Sie es manuell zu tun. OK, es könnte „chaotisch“ sein, aber es ist immer noch die richtige Antwort

Wenn Sie ein Benutzer meiner FürJeden DSL , kann es mit einer Detect Abfrage durchgeführt werden. 

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

Gibt es einen besseren Weg, als nur durch Schleifen und manuell die beiden Felder für jedes Objekt zu vergleichen und dann, wenn gefunden zu brechen? Das scheint nur so chaotisch, nach einem besseren Weg suchen.

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

Wenn Sie wirklich mit Effizienz betroffen sind, können Sie eine benutzerdefinierte Liste Implementierung erstellen, die das Feld in Ihrem Objekt als Hash verwendet und eine HashMap als Speicher verwenden. Aber wahrscheinlich würde dies zu viel sein.

Dann müssen Sie den Ort wechseln, in dem Sie die Daten von Arraylist YourCustomList füllen.

Wie: 

 List list = new ArrayList();

 fillFromSoap( list );

An: 

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

Die Umsetzung wäre in etwa wie folgt: 

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

}

So ziemlich wie ein HashSet, hier ist das Problem der HashSet stützt sich auf die gute Umsetzung der hashCode-Methode, die Sie wahrscheinlich nicht haben. Stattdessen verwenden Sie als Hash „das Feld Sie wissen“, welche die ist, die ein Objekt macht mit dem anderen gleicht.

Natürlich eine Liste von Grund auf viel komplizierter als meine Schnipsel über Implementierung, deshalb sage ich die Fabian Steeg Vorschlag wäre besser und einfacher zu implementieren (obwohl so etwas wie dies wäre effizienter)

Sagen Sie uns, was Sie am Ende getan hat.

Vielleicht eine Liste ist nicht das, was Sie brauchen.

Vielleicht ein TreeSet wäre ein besserer Behälter. Sie erhalten O Einfügen und Abrufen (N log), und bestellte Iteration (aber nicht zulassen, dass Duplikate).

LinkedHashMap könnte sein, noch besser für Ihren Anwendungsfall, das ist zu überprüfen.

Der Aufbau einer HashMap dieser Objekte auf dem Feldwert basiert wie ein Schlüssel aus anwendungstechnischer Sicht sinnvoll sein könnte, z.B. besiedeln Karten einmal und Objekte finden sehr effizient

Wenn Sie viel Zeit in der gleichen Liste suchen müssen, kann es sich auszahlen, einen Index zu erstellen.

Iterate einmal durch, und eine HashMap bauen mit dem Gleichheits schätzen Sie als Schlüssel und den entsprechenden Knoten als Wert suchen. Wenn Sie alle statt jemandem von a gleich Wert gegeben müssen, dann lassen Sie die Karte einen Werttyp der Liste hat und die gesamte Liste in der anfänglichen Iteration bauen.

Bitte beachten Sie, dass Sie, bevor Sie diese als Kopf für den Bau des Index durchqueren kann beschatten messen sollen, gerade bis der erwartete Knoten gefunden wird.

Es gibt drei grundlegende Optionen:

1) Bei Abrufleistung ist von größter Bedeutung, und es ist praktisch eine Form von Hash-Tabelle Verwenden Sie dazu gebaut einmal (und veränderte wie / wenn die Liste Änderungen).

2) Wenn die Liste bequem sortiert ist, oder es ist praktisch es und O zu sortieren (log n) Retrieval genügt, zu sortieren und zu suchen.

3) Wenn O (n) Retrieval ist schnell genug, oder wenn es unpraktisch ist, die Datenstruktur oder eine andere zu manipulieren / aufrechtzuerhalten, über die Liste iterieren.

Vor dem Code komplexer als eine einfache Iteration über die Liste zu schreiben, lohnt es sich, durch einige Fragen zu denken.

  • Warum ist etwas anderes benötigt? (Time) Leistung? Eleganz? Wartbarkeit? Wiederverwendung? Alle diese sind in Ordnung Gründen auseinander oder zusammen, aber sie beeinflussen die Lösung.

  • Wie viel Kontrolle haben Sie über die Datenstruktur in Frage? Können Sie beeinflussen, wie es gebaut wird? Managed später?

  • Was ist der Lebenszyklus der Datenstruktur (und darunter liegende Objekte)? Ist es gebaut auf einmal und nie verändert oder hochdynamische? Können Sie den Code-Monitor (oder sogar ändern) seines Lebenszyklus?

  • Gibt es andere wichtige Einschränkungen, wie Speicherbedarf? Enthält Informationen über Duplikate von Bedeutung? Etc.

Ich würde sagen, die einfachste Lösung, um das Objekt sein würde, und delegiert die enthält Aufruf zu einer Sammlung der verpackten Klasse wickeln. Dies ist vergleichbar mit dem Komparator aber zwingt Sie nicht die resultierende Sammlung zu sortieren, können Sie einfach ArrayList.contains verwenden können (). 

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

    }
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top