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

Question

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

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

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

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

Answer 1

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

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

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

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

---

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

Answer 2

Вы можете использовать Comparator со встроенными в 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);

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

Может быть, Список - это не то, что вам нужно.

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

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

Answer 8

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

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

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

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

Как:

 List list = new ArrayList();

 fillFromSoap( list );

Кому:

 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, которого, вероятно, у вас нет. Вместо этого вы используете в качестве хеша «то поле, которое вы знаете», которое делает один объект равным другому.

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

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

Answer 9

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

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

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

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

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

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

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

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

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

Answer 10

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

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

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