Лучший datastructure для часто запрашиваемого списка объектов
У меня есть список объектов, говорят, Список. Класс Объекта имеет, равняется методу, на немногих атрибутах (бизнес-правило) для дифференциации одного объекта Объекта от другого.
Задача, которую мы обычно выполняем на этом списке, состоит в том, чтобы удалить все дубликаты что-то вроде этого:
List<Entity> noDuplicates = new ArrayList<Entity>();
for(Entity entity: lstEntities)
{
int indexOf = noDuplicates.indexOf(entity);
if(indexOf >= 0 )
{
noDuplicates.get(indexOf).merge(entity);
}
else
{
noDuplicates.add(entity);
}
}
Теперь, проблема, которую я наблюдал, состоит в том, что эта часть кода, замедляется значительно, как только список имеет объекты больше чем 10 000. Я понимаю, что arraylist делает o (N) поиск.
Существует ли более быстрая альтернатива, использование HashMap не является опцией, потому что уникальность объекта создается на 4 из своих атрибутов вместе, это было бы утомительно, чтобы вставить сам ключ в карту? отсортированный набор поможет в более быстрых запросах?
Спасибо
6 ответов
Теперь проблема, которую я наблюдал, заключается в том, что эта часть кода значительно замедляется, как только в списке есть объекты более 10000. Я понимаю, что arraylist выполняет поиск ao (N).
Опубликованный вами алгоритм на самом деле хуже, чем O (N)
- Обходя входной список
lstEntities- O (N) - в этом цикле, вы вызываете
ArrayList. indexOf (T), который должен сканировать список - O (N) снова
Ваш алгоритм на самом деле O (N ^ 2), поскольку вы потенциально просматриваете список дважды в цикле.
Похоже, вы хотите сделать две операции:
- Из входного
List, удалить все дубликаты. - Когда вы найдете дубликаты, «объедините» объекты.
Вы можете сделать это, просмотрев список только один раз, а не во вложенных циклах. Я бы рекомендовал разбить вашу Entity , чтобы переместить поля, которые «идентифицируют» Entity, в другой тип, например ID , или, по крайней мере, добавить getID () метод, который может возвращать эти поля, сгруппированные в один тип. Таким образом, вы можете легко построить карту между двумя типами, чтобы иметь возможность объединять сущности с «дублирующими» идентичностями. Это может выглядеть примерно так:
Map<ID, Entity> map = new HashMap<ID, Entity>(inputList.size());
for (Entity e : inputList) {
Entity existing = map.get(e.getID());
if (existing == null) {
//not in map, add it
map.put(e.getID(), e);
}
else {
existing.merge(e);
}
}
Итерация по списку - O (n), а HashMap.get (K) - операция с постоянным временем.
Все зависит от того, что делает эта операция merge. Изменяет ли merge какие-либо атрибуты, которые сравниваются при выполнении equals? Если нет, то вы будете поражены тем, насколько быстрее это произойдет, если вы сделаете следующее:
Во-первых, определите hashCode для вашего класса Entity, который совместим с вашим определением equals. Один из распространенных способов сделать это:
public int hashCode() {
// assuming the four attributes that determine equality are called
// attrFoo, attrBar, attrBaz, and attrQux
int hash = 1;
hash += attrFoo == null ? 0 : attrFoo.hashCode();
hash *= 37;
hash += attrBar == null ? 0 : attrBar.hashCode();
hash *= 37;
hash += attrBaz == null ? 0 : attrBaz.hashCode();
hash *= 37;
hash += attrQux == null ? 0 : attrQux.hashCode();
return hash;
}
Затем используйте HashMap, чтобы вы могли найти эти вещи:
Map<Entity, Entity> map = new HashMap<Entity, Entity>();
for(Entity entity: lstEntities) {
if (map.containsKey(entity)) {
map.get(entity).merge(entity);
} else {
map.put(entity, entity);
}
}
return map.values(); // or keys(). Whichever.
Должен заметить, что я чувствую себя немного грязным, когда пишу вышеприведенный код, потому что вы действительно не должны делать Map ключи, которые не являются неизменяемыми, но это будет работать и намного, намного быстрее, чем то, что вы делаете сейчас.
Вместо списочной структуры можно использовать набор (более подходящий, если вы заботитесь об уникальности сущностей), как предложил Ларс. Кроме того, если производительность является проблемой, я бы рассмотрел возможность использования TreeSet и реализации Comparator для сравнения экземпляров сущностей на основе их атрибутов. Древовидная структура позволит быстро (с логарифмической сложностью) выполнять операции вставки, удаления и извлечения.
Есть идея использовать Set вместо List, в Set нет дубликатов. Чтобы удалить дубликаты из списка, можно просто добавить Список в новый Набор
List<Entity> list = //your list.
Set<Entity> set = new HashSet<Entitiy>();
set.addAll(list);
Но опять же, может быть, есть какая-то причина для использования Списка в первую очередь? Если нет, то вместо него можно использовать Set, и не беспокоиться о дубликатах.
EDIT
В Set нет индексной ссылки на элементы (по сравнению с List, где вы можете сделать get(int index)). Элементы в Set плавают вокруг без конкретной точки отсчета.
Если вам нужно найти конкретный элемент, вам нужно перебрать их все. Если это не устраивает и/или вы не можете обойтись без индексированной ссылки - которая позволяет get(int index) и remove(int index) - полагаю, Set для вас не вариант.
Если у вас нет причин для необходимости упорядочивания списка, вам, вероятно, лучше использовать набор - в частности, HashSet.
Я понимаю ваше беспокойство по поводу использования хэшированной коллекции, потому что "уникальность сущности строится на 4 ее атрибутах вместе", но это легко преодолимо. Вам просто нужно определить метод hashcode(), который совместим с существующим методом equals(), и тогда вы сможете вставлять свои сущности в Set, и, как волшебный побочный эффект, вам больше никогда не придется удалять дубликаты.
Два простых шага для алгоритма O (N * Log (N)):
- Сортировать список с помощью компаратора на основе четырех важных полей.
- Перебирать список, сравнивая каждый элемент со следующим в списке , если они равны, объедините их и удалите одну.