Самый эффективный способ увидеть, содержит ли ArrayList объект в Java

Ответ 1

Это зависит от того, насколько эффективно вам нужны вещи. Простое повторение списка, ищущего элемент, который удовлетворяет определенному условию, - это O (n), но это также ArrayList.Contains, если вы можете реализовать метод Equals. Если вы не делаете этого в циклах или внутренних циклах, этот подход, вероятно, просто прекрасен.

Если вам действительно нужны очень эффективные скорости поиска любой ценой, вам нужно сделать две вещи:

• Работайте над тем, что класс : Создать класс адаптера, который может обернуть сгенерированный класс и которые реализуют equals() на основе на этих двух полях (при условии, что они являются общедоступными). Не забудьте также реализовать hashCode() (*)
• Оберните каждый объект с помощью этого адаптера и поместите его в HashSet. HashSet.contains() имеет постоянную время доступа, то есть O (1) вместо O (n).

Конечно, для построения этого HashSet по-прежнему существует стоимость O (n). Вы только выиграете, если стоимость создания HashSet незначительна по сравнению с общей стоимостью всех проверок contains(), которые вам нужно сделать. Попытка создать список без дубликатов - это такой случай.

Ответ 2

Вы можете использовать Компаратор с встроенными методами Java для сортировки и бинарного поиска. Предположим, у вас есть такой класс, где a и b - поля, которые вы хотите использовать для сортировки:

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

Вы бы определили свой компаратор:

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

Затем отсортируйте список:

Collections.sort(list, comparator);

И, наконец, выполните двоичный поиск:

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

Ответ 3

Учитывая ваши ограничения, вы застряли в поиске грубой силы (или создании индекса, если поиск будет повторяться). Можете ли вы рассказать о том, как генерируется ArrayList - возможно, там есть место для маневра.

Если вы ищете более красивый код, рассмотрите классы Apache Commons Collections, в частности CollectionUtils.find(), для готовый синтаксический сахар:

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

Ответ 4

Если список отсортирован, вы можете использовать двоичный файл поиск. Если нет, тогда нет лучшего способа.

Если вы делаете это много, почти наверняка стоит потратить время на сортировку списка в первый раз. Поскольку вы не можете изменять классы, вам нужно будет использовать Comparator для сортировки и поиска.

Ответ 5

Даже если метод equals сравнивал эти два поля, то логически, это был бы тот же код, что и вы его вручную. Хорошо, это может быть "грязно", но он по-прежнему правильный ответ

Ответ 6

Если вы являетесь пользователем моего ForEach DSL, это можно сделать с помощью запроса 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();

Ответ 7

Есть ли лучший способ, чем просто перебирать и вручную сравнивать два поля для каждого объекта, а затем ломаться при их обнаружении? Это просто кажется таким грязным, ища лучший способ.

Если ваша проблема связана с ремонтопригодностью, вы можете сделать что-то Fabian Steeg (что бы я сделал), хотя это, вероятно, не "самый эффективный" (потому что вы нужно сначала отсортировать массив, а затем выполнить бинарный поиск), но, безусловно, самый чистый и лучший вариант.

Если вы действительно заинтересованы в эффективности, вы можете создать собственную реализацию списка, которая использует поле в вашем объекте как хеш и использует HashMap в качестве хранилища. Но, вероятно, это было бы слишком много.

Затем вы должны изменить место, где вы заполняете данные из ArrayList, в YourCustomList.

Вроде:

 List list = new ArrayList();

 fillFromSoap( list );

To:

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

Реализация будет выглядеть примерно так:

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

}

В значительной степени, как HashSet, проблема заключается в том, что HashSet полагается на хорошую реализацию метода hashCode, которого, вероятно, у вас нет. Вместо этого вы используете как хэш "это поле, которое вы знаете", которое является тем, которое делает один объект равным другому.

Конечно, реализация списка с нуля намного сложнее, чем мой фрагмент выше, поэтому я говорю, что предложение Fabian Steeg было бы лучше и проще реализовать (хотя что-то подобное было бы более эффективным)

Расскажите, что вы сделали в конце.

Ответ 8

Возможно, список не то, что вам нужно.

Может быть, TreeSet будет лучшим контейнером. Вы получаете вложение и извлечение O (log N) и упорядочивали итерацию (но не допускаете дубликатов).

LinkedHashMap может быть еще лучше для вашего прецедента, проверьте это тоже.

Ответ 9

Построение HashMap этих объектов на основе значения поля в качестве ключа может быть целесообразным с точки зрения производительности, например. заполнять Карты один раз и находить объекты очень эффективно

Ответ 10

Если вам нужно найти много времени в одном списке, он может окупиться, чтобы создать индекс.

Итерации один раз и постройте HashMap с эквивалентным значением, которое вы ищете как ключ и соответствующий node как значение. Если вам нужно все вместо любого заданного значения равным, то пусть карта имеет тип значения списка и построит весь список в начальной итерации.

Обратите внимание, что перед этим нужно измерять, так как накладные расходы на создание индекса могут затенять только перемещение до тех пор, пока не будет найден ожидаемый node.

Ответ 11

Существует три основных варианта:

1) Если производительность поиска имеет первостепенное значение, и это практически целесообразно, используйте одну из форм хеш-таблицы, построенной один раз (и измененную как/если список изменяется).

2) Если список удобно сортировать или его целесообразно сортировать, а поиск O (log n) достаточен, сортировка и поиск.

3) Если извлечение O (n) достаточно быстро или если непрактично манипулировать/поддерживать структуру данных или альтернативу, перебирайте список.

Прежде чем писать код более сложным, чем простая итерация над списком, стоит подумать над некоторыми вопросами.

• Почему нужно что-то другое? (Время)? Elegance? Ремонтопригодность? Повторное использование? Все это в порядке, отдельно или вместе, но они влияют на решение.

• Сколько у вас контроля над рассматриваемой структурой данных? Можете ли вы повлиять на его построение? Управляется позже?

• Каков жизненный цикл структуры данных (и базовых объектов)? Является ли он создан сразу и никогда не изменился или не был очень динамичным? Может ли ваш код отслеживать (или даже изменять) его жизненный цикл?

• Существуют ли другие важные ограничения, такие как объем памяти? Имеет ли информация о дубликатах? Etc.

Ответ 12

Я бы сказал, что самым простым решением было бы обернуть объект и делегировать вызов contains в коллекцию завернутого класса. Это похоже на компаратор, но не заставляет вас сортировать полученную коллекцию, вы можете просто использовать ArrayList.contains().

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

    }