Najbardziej efektywny sposób sprawdzania, czy ArrayList zawiera obiekt w Javie

Możesz użyć komparatora z wbudowanymi metodami Javy do sortowania i wyszukiwania binarnego. Załóżmy, że masz klasę taką jak ta, gdzie A i b są polami, których chcesz użyć do sortowania:

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

Zdefiniowałbyś swój 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);
  }
};

Następnie posortuj listę:

Collections.sort(list, comparator);

I na koniec wykonaj wyszukiwanie binarne:

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

Biorąc pod uwagę twoje ograniczenia, utknąłeś z wyszukiwaniem brute force (lub tworzeniem indeksu, jeśli wyszukiwanie będzie powtarzane). Czy możesz rozwinąć jakiś sposób generowania ArrayList -- Być może jest tam jakaś przestrzeń do poruszania się.

Jeśli szukasz ładniejszego kodu, rozważ użycie klas Apache Commons Collections, w szczególności CollectionUtils.find () , dla gotowego cukru składniowego:

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

Jeśli lista jest posortowana , możesz użyć wyszukiwania binarnego. Jeśli nie, to nie ma lepszego sposobu.

Jeśli robisz to często, prawie na pewno warto byłoby posortować listę za pierwszym razem. Ponieważ nie możesz modyfikować klas, musisz użyć Comparator do sortowania i wyszukiwania.

Nawet jeśli metoda equals byłaby porównując te dwa pola, to logicznie, byłby to ten sam kod, co robi się to ręcznie. OK, to może być "bałagan", ale to nadal prawidłowa odpowiedź

Jeśli jesteś użytkownikiem mojego ForEach DSL , można to zrobić za pomocą zapytania Detect.

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

czy jest lepszy sposób niż tylko przeplatanie i ręczne porównywanie dwóch pól dla każdego obiektu, a następnie łamanie po znalezieniu? To wygląda na bałagan, szukając lepszego sposobu.

Jeśli twoim problemem jest konserwacja, możesz zrobić to, co Fabian Steeg zasugerował (to właśnie bym zrobił), chociaż prawdopodobnie nie jest to "najbardziej wydajne" (ponieważ najpierw musisz posortować tablicę, a następnie wykonać wyszukiwanie binarne), ale z pewnością najczystsze i lepszą opcją.

Jeśli naprawdę zależy ci na wydajności, możesz utworzyć niestandardową implementację listy, która używa pola w Twoim obiekcie jako hash i używa Hashmapy jako pamięci masowej. Ale pewnie to by było za dużo.

Następnie musisz zmienić miejsce, w którym wypełniasz dane z ArrayList na YourCustomList.

Jak:

 List list = new ArrayList();

 fillFromSoap( list );

Do:

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

Implementacja byłaby podobna do następującej:

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

}

Prawie podobnie jak HashSet, problem polega na tym, że HashSet opiera się na dobrej implementacji metody hashCode, której prawdopodobnie nie masz. Zamiast tego używasz jako hash "to pole, które znasz" , które sprawia, że jeden obiekt jest równy drugiemu.

Oczywiście implementacja listy od zera o wiele trudniejsza niż mój fragment powyżej, dlatego mówię, że sugestia Fabian Steeg byłaby lepsza i łatwiejsza do wdrożenia ( chociaż coś takiego byłoby bardziej efektywne )

Może lista nie jest tym, czego potrzebujesz.

Może TreeSet byłby lepszym pojemnikiem. Otrzymujesz o (log N) wstawianie i pobieranie oraz uporządkowaną iterację (ale nie pozwoli na duplikaty).

LinkedHashMap może być jeszcze lepszy dla Twojego przypadku użycia, sprawdź też to.

Budowanie HashMap tych obiektów na podstawie wartości pola jako klucza może być opłacalne z punktu widzenia wydajności, np.]}

Jeśli musisz przeszukiwać wiele razy na tej samej liście, zbudowanie indeksu może się opłacić.

Powtórz raz i zbuduj Hashmapę z wartością równą, której szukasz jako klucz i odpowiednim węzłem jako wartością. Jeśli potrzebujesz wszystkich zamiast kogokolwiek o podanej wartości, niech mapa ma typ wartości listy i zbuduje całą listę w początkowej iteracji.

Należy pamiętać, że należy zmierzyć przed zrobieniem tego, ponieważ narzut budynku indeksu może przyciemnienie tylko przemieszcza się aż do znalezienia oczekiwanego węzła.

Istnieją trzy podstawowe opcje:

1) Jeśli wydajność pobierania jest najważniejsza i jest to praktyczne, użyj postaci tabeli hash zbudowanej raz(i zmienionej jako / jeśli Lista się zmieni).

2) Jeśli lista jest wygodnie posortowana lub jest to praktyczne, aby ją sortować i o (log n) pobieranie jest wystarczające, Sortuj I Szukaj.

3) Jeśli O(n) pobieranie jest wystarczająco szybkie lub jeśli manipulowanie/utrzymywanie struktury danych lub alternatywy jest niepraktyczne, iteratuj listę.

Zanim napiszesz kod bardziej złożony niż prosta iteracja nad listą, warto przemyśleć kilka pytań.

• Dlaczego potrzebne jest coś innego? (Czas) wydajność? Elegancja? Konserwacja? Ponowne użycie? Wszystkie z tych powodów są w porządku, osobno lub razem, ale mają wpływ na rozwiązanie.

• Jak bardzo masz kontrolę nad daną strukturą danych? Czy możesz wpłynąć na to, jak jest zbudowany? Udało się później?

• Co to jest cykl życia struktury danych (i obiektów bazowych)? Czy jest zbudowany na raz i nigdy się nie zmienił, czy jest bardzo dynamiczny? Czy Twój kod może monitorować (a nawet zmieniać) jego cykl życia?

• Czy istnieją inne ważne ograniczenia, takie jak pamięć footprintu? Czy informacje o duplikatach mają znaczenie? Itd.

Powiedziałbym, że najprostszym rozwiązaniem byłoby zawinięcie obiektu i delegowanie wywołania contains do kolekcji zawiniętej klasy. Jest to podobne do komparatora, ale nie zmusza cię do sortowania wynikowej kolekcji, możesz po prostu użyć ArrayList.zawiera().

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

    }