Der effizienteste Weg, um zu sehen, ob eine ArrayList ein Objekt in Java enthält

Ich habe eine ArrayList mit Objekten in Java. Die Objekte haben vier Felder, von denen zwei die ich benutzen würde, zu prüfen, das Objekt gleich einem anderen. Ich bin auf der Suche nach der effizienteste Weg, diese beiden Felder, um zu sehen, ob das array enthält das Objekt.

Dem Schraubenschlüssel ist, dass diese Klassen werden generiert basierend auf dem XSD-Objekte, so kann ich nicht ändern, die Klassen selbst zu überschreiben, die .equals.

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

Edit: die ArrayList stammt aus einer SOAP-Antwort, ist unmarshallt in Objekte.

InformationsquelleAutor der Frage Parrots | 2009-02-17

  1. 97

    Es hängt davon ab, wie effizient Sie müssen Dinge zu sein. Einfach die Iteration über die Liste, suchen Sie das element an, welches eine bestimmte Bedingung ist O(n), aber so ist die ArrayList.Enthält, wenn Sie könnten, implementieren Sie die Equals-Methode. Wenn Sie nicht tun, diese in Schleifen oder inneren Schleifen dieser Ansatz ist wahrscheinlich just fine.

    Wenn Sie wirklich brauchen, sehr leistungsfähige look-up-Geschwindigkeiten an allen Kosten, müssen Sie zwei Dinge tun:

    1. Arbeit um die Tatsache, dass die Klasse
      generiert: Schreiben Sie eine adapter-Klasse, die
      wickeln kann die generierte Klasse und
      die Umsetzung equals() basiert
      auf diese beiden Felder (vorausgesetzt, Sie
      öffentlich sind). Vergessen Sie nicht auch
      implementieren hashCode() (*)
    2. Wickeln Sie jedes Objekt mit adapter und
      legen Sie es in ein HashSet.
      HashSet.enthält() hat Konstante
      access-Zeit, also O(1) statt O(n).

    Natürlich der Aufbau dieses HashSet hat noch eine O(n) Kosten. Sie sind nur gehen, um etwas gewinnen, wenn die Kosten für den Bau der HashSet ist vernachlässigbar im Vergleich zu den Gesamtkosten alle der contains() prüft, die Sie benötigen, zu tun. Versuchen, erstellen Sie eine Liste ohne Duplikate ist so ein Fall.

    *
    () Implementierung von hashCode() wird am besten durch XOR ' Ing (^- operator) die hashCodes der gleichen Felder, die Sie für die equals-Implementierung (aber multipliziert mit 31 zu reduzieren die chance von der XOR nachgeben 0)

    InformationsquelleAutor der Antwort Wim Coenen

  2. 35

    Könnten Sie einen Komparator mit der Java-built-in-Methoden für das Sortieren und Binär suchen. Angenommen, Sie haben eine Klasse wie diese, wo a und b sind die Felder, die Sie zum Sortieren verwenden möchten:

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

    Definieren Sie Ihre Komparator:

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

    Sowie endlich die binäre Suche:

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

    InformationsquelleAutor der Antwort Fabian Steeg

  3. 9

    Gegeben, Ihre Zwänge, Sie stecken mit brute-force-Suche (oder erstellen Sie einen index, wenn die Suche wiederholt werden). Können Sie näher erläutern, jeder, wie der ArrayList generiert wird-vielleicht gibt es einigen Spielraum gibt.

    Wenn alles, was Sie suchen, ist schöner code, erwägen Sie die Verwendung der Apache Commons Collections-Klassen, insbesondere CollectionUtils.finden()für die ready-made-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);
   }
});

    InformationsquelleAutor der Antwort Michael Brewer-Davis

  4. 5

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

    Wenn Sie das tun eine Menge, es würde fast sicherlich lohnen, Sortieren Sie die Liste das erste mal. Da können Sie nicht ändern Sie die Klassen, die Sie verwenden würde eine Comparator zu tun, die Sortierung und Suche.

    InformationsquelleAutor der Antwort Michael Myers

  5. 3

    Selbst wenn die equals-Methode wurden Vergleich dieser beiden Felder, dann logisch, wäre es genau der gleiche code, wie Sie es manuell zu tun. OK, es könnte sein, "chaotisch", aber es ist immer noch die richtige Antwort

    InformationsquelleAutor der Antwort oxbow_lakes

  6. 3

    Wenn Sie einen Benutzer von meinem ForEach-DSLes kann getan werden, mit einem Detect Abfrage.

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

    InformationsquelleAutor der Antwort akuhn

  7. 2

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

    Wenn Ihr Anliegen Wartbarkeit könnten Sie tun, was Fabian Steeg vorschlagen ( das ist, was ich tun würde ), obwohl es wahrscheinlich nicht die "effizienteste" ( weil Sie zu Sortieren das array zuerst und führen Sie dann die binäre Suche ), aber sicherlich die sauberste und bessere option.

    Wenn Sie wirklich besorgt mit Energieeffizienz, können Sie eine benutzerdefinierte Liste erstellen-Implementierung verwendet, die das Feld im Objekt als hash verwenden und eine HashMap, die als Speicher. Aber wahrscheinlich wäre dies zu viel.

    Dann müssen Sie änderungen an den Ort, wo Sie füllen die Daten aus der ArrayList zu YourCustomList.

    Wie: 

     List list = new ArrayList();

 fillFromSoap( list );

    : 

     List list = new MyCustomSpecialList();

 fillFromSoap( list );

    Die Umsetzung wäre so etwas wie die folgenden:

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

    }

    Ziemlich viel wie ein HashSet, das problem hier ist das HashSet setzt auf die gute Implementierung der hashCode-Methode, die Sie wahrscheinlich nicht haben. Stattdessen verwenden Sie als hash ", das Feld, das Sie wissen," welches macht, dass man Objekt ist gleich zu den anderen.

    Natürlich Implementierung einer Liste aus dem Grund viel komplizierter als mein snippet oben, das ist, warum ich sagen, das Fabian Steeg Vorschlag wäre besser und einfacher zu implementieren ( obwohl so etwas wie dies effizienter wäre )

    Sagen Sie uns, was Sie haben am Ende.

    InformationsquelleAutor der Antwort OscarRyz

  8. 2

    Vielleicht eine Liste ist nicht das, was Sie brauchen.

    Vielleicht ein TreeSet wäre eine bessere container. Sie bekommen in O(log N) einfügen und abrufen, und bestellt iteration (aber nicht zulassen, dass Duplikate).

    LinkedHashMap könnte noch besser für Ihre Nutzung Fall, dass der check out auch.

    InformationsquelleAutor der Antwort Ben Hardy

  9. 1

    Aufbau einer HashMap dieser Objekte, basierend auf den Wert des Feldes als Schlüssel könnte sich lohnen, aus der performance-Perspektive, z.B. Auffüllen Maps nach und finden Sie Objekte sehr effizient

    InformationsquelleAutor der Antwort Rocket Surgeon

  10. 1

    Wenn Sie suchen, die viele Zeit in der gleichen Liste, es kann sich auszahlen, um einen index zu erstellen.

    Iterieren einmal durch, und bauen eine HashMap mit dem Wert, die Sie suchen, wie Sie den Schlüssel und die entsprechenden Knoten als Wert. Wenn Sie brauchen, alle statt jedermann, der einen bestimmten Wert haben, dann lassen Sie die Karte haben einen Wert-Typ aus der Liste und erstellen Sie die gesamte Liste in der ersten iteration.

    Bitte beachten Sie, dass Sie sollten Messen, bevor dies zu tun, da der overhead für den Aufbau des index überschatten können nur durchqueren, bis der erwartete Knoten gefunden.

    InformationsquelleAutor der Antwort Thorbjørn Ravn Andersen

  11. 1

    Gibt es drei grundlegende Optionen:

    1) Wenn der Abruf der Leistung ist von größter Bedeutung und es ist praktisch, dies zu tun, verwenden Sie eine form der hash-Tabelle einmal gebaut (und verändert wie/, wenn die Liste der änderungen).

    2) Wenn die Liste bequem sortiert oder ist es sinnvoll zu Sortieren und in O(log n) Abfrage ist ausreichend, Sortieren und suchen.

    3) Wenn O(n) - Abruf ist schnell genug, oder wenn es unpraktisch ist, zu Bearbeiten/verwalten die Daten-Struktur oder eine Alternative, Iteration über die Liste.

    Bevor Sie code schreiben, die komplexer als eine einfache iteration über die Liste, es lohnt sich, denken über einige Fragen stellen.

    • Warum wird etwas anderes benötigt? (Zeit) Leistung? Eleganz? Wartbarkeit? Wiederverwenden? 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 ist? Verwaltete später?

    • Was ist der Lebenszyklus der Daten-Struktur (und die zugrunde liegenden Objekte)? Ist es gebaut, alle auf einmal und nie geändert, oder hochdynamische? Können Sie Ihre code-monitor (oder auch alter), die Ihren Lebenszyklus?

    • Gibt es andere wichtige Faktoren wie Speicher-footprint? Informationen über Duplikate Materie? Etc.

    InformationsquelleAutor der Antwort Jeremy Rishel

  12. 0

    Ich würde sagen, die einfachste Lösung wäre, wickeln Sie das Objekt und delegieren den Aufruf enthält eine Sammlung der umschlossenen Klasse. Das ist ähnlich wie der Komparator, aber nicht zwingen, Sie zu Sortieren, wird die resultierende Auflistung, können Sie einfach ArrayList.enthält().

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

    }

    InformationsquelleAutor der Antwort jonathan.cone

Schreibe einen Kommentar