Лучшая структура данных для часто запрашиваемого списка объектов

Question

У меня есть список объектов, скажем, Список. Класс Entity имеет метод equals, по нескольким атрибутам (бизнес-правилам), чтобы отличить один объект Entity от другого.

Задача, которую мы обычно выполняем в этом списке, состоит в том, чтобы удалить все дубликаты примерно так:

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

Теперь проблема, которую я наблюдал, состоит в том, что эта часть кода значительно замедляется, как только в списке есть объекты более 10000. Я понимаю, что arraylist выполняет поиск o (N).

Есть ли более быстрая альтернатива, использование HashMap не вариант, потому что уникальность сущности строится на 4 ее атрибутах вместе, было бы утомительно вставлять сам ключ в карту? будет ли сортированный набор помощи в более быстрых запросах?

Спасибо

Answer 1

Вместо структуры списка вы можете использовать набор (более подходящий, если вы беспокоитесь об уникальности сущности), как предложил Ларс. Кроме того, если производительность является проблемой, я бы посмотрел на использование TreeSet и реализовал Comparator для сравнения экземпляров сущностей на основе их атрибутов. Древовидная структура обеспечивает быстрые (логарифмическая сложность) операции вставки, удаления и извлечения.

Answer 2

Теперь проблема, с которой я столкнулся, заключается в том, что эта часть кода значительно замедляется, как только в списке появляются объекты более чем 10000. Я понимаю, что arraylist выполняет поиск ao (N).

Алгоритм, который вы опубликовали, на самом деле хуже, чем O (N)

• Итерация по списку ввода lstEntities - O (N)
• в этомцикл, вы вызываете ArrayList.indexOf(T), который должен сканировать список - O (N) снова

Вы на самом деле алгоритм O (N ^ 2), так как вы потенциально сканируете список дважды в цикле.

Похоже, что вы действительно хотите выполнить две операции:

1. С входа List удалить все дубликаты
2. Когда вы найдете дубликаты, "объединить" сущности.

Вы можете сделать это путем сканирования списка только один раз, а не во вложенных циклах.Я бы рекомендовал разбить ваш 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) - операция с постоянным временем.

Answer 3

Идея состоит в том, чтобы использовать Set вместо List, в Set нет дубликатов. Чтобы удалить дубликаты из списка, вы можете просто добавить List к новому Set

List<Entity> list = //your list.
Set<Entity> set = new HashSet<Entitiy>();
set.addAll(list);

Но опять же, может быть, есть какая-то причина для использования List в первую очередь? Если нет, вы можете использовать Set вместо этого, и вам не придется беспокоиться о дубликатах.

EDIT

Нет ссылки на индекс элементов в Set (по сравнению с List, где вы можете сделать get(int index)). Элементы в Set плавают без конкретной точки отсчета.

Если вам нужно найти конкретный, вам нужно перебрать их все. Если это не так, и / или вы не можете быть без индексированной ссылки - это учитывает get(int index) и remove(int index) - я думаю, Set не вариант для вас.

Answer 4

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

Answer 5

Два простых шага для алгоритма O (N * Log (N)):

1. Сортировка списка с использованием компаратора по четырем важным полям
2. Перебирайте список, сравнивая каждый элемент со следующим в списке, если они равны, объедините их и удалите один.

Answer 6

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

Я вижу ваше беспокойство по поводу использования хешированной коллекции, потому что "уникальность сущности основана на 4 ее атрибутах вместе" , но это легко преодолеть. Вам просто нужно определить метод hashcode (), который совместим с вашим существующим методом equals (), а затем вы можете вставить свои сущности в набор, и в качестве магического побочного эффекта больше никогда не придется удалять дубликаты.