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

Question

У меня есть ArrayList объектов в Java. Объекты имеют четыре поля, два из которых я бы использовал, чтобы рассмотреть объект, равный другому. Я ищу наиболее эффективный способ, учитывая эти два поля, чтобы увидеть, содержит ли массив этот объект.

Ключ состоит в том, что эти классы создаются на основе объектов XSD, поэтому я не могу изменять сами классы, чтобы перезаписать .equals.

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

Редактировать: ArrayList получен из ответа SOAP, который не привязан к объектам.

Answer 1

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

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

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

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

---

* ( ) Реализация хэш-код() лучше всего сделать с помощью XOR-(^ оператором) hashCodes тех же полей, которые вы используете для реализации Equals (но multiply by 31, чтобы уменьшить шанс из XOR уступая 0)

Answer 2

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

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

Answer 3

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

Answer 4

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

Если все, что вы ищете красивее код, следует использовать классы Apache Commons Коллекции, в частности 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); 
    } 
}); 

Answer 5

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

Answer 6

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

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

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

Answer 7

Вы можете использовать Компаратор с встроенными методами Java для сортировки и двоичного поиска. Предположим, у вас есть класс, как это, где а и Ь являются поля, которые вы хотите использовать для сортировки:

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

Answer 8

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

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

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

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

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

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

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

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

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

Answer 9

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

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

Если вы действительно заинтересованы в эффективности, вы можете создать пользовательскую реализацию List, которая использует поле в вашем объекте как хэш и использует 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 предложение было бы лучше и легче реализовать (хотя что-то вроде этого было бы более эффективным)

Сообщите нам что вы сделали в конце.

Answer 10

Я бы сказал, что самым простым решением было бы обернуть объект и делегировать вызов 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(); 
     } 

    } 

Answer 11

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

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

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

Answer 12

Если вы являетесь пользователем моего 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();