2015-08-03 3 views
3

У меня есть ArrayList пользовательских объектов (DTO), структуру DTO:Эффективный алгоритм для объединения объектов в ArrayList

private String id; 
private String text; 
private String query; 
private String locatorId; 
private Collection<String> categories; 
private Collection<String> triggers; 

У меня есть две задачи:

  • Удалить дубликаты в массив (это кажется ОК, я должен использовать HashSet)
  • Найти объекты в ArrayList с одинаковым полем id и объединить их в один объект (я должен объединить категории полей и триггеры) и создать окончательный список с объединенными объектами.

Каков наиболее эффективный подход к такой задаче? Также мне интересно использовать выражение Lambda в моем алгоритме.

+2

Как объединить текст, запрос и категорию? – m0skit0

+0

Эти поля не будут объединены (они будут одинаковыми, только разница в категориях полей и триггерах). –

ответ

1

Внесите equals и hashCode на основании поля id в DTO и сохраните DTO в Set. Это должно устранить обе проблемы; учитывая то, как теперь определено равенство ваших DTO, никакие дубликаты с одинаковыми id не могут существовать в Set.

EDIT:

Как ваше требование, чтобы объединить категории и триггеры существующего DTO на основе значений из нового, то лучше всего подходит структура данных для хранения DTO сек будет Map<DTO, DTO> (потому что это обременительно возвращайте элементы обратно из Set после того, как вы их положили). Кроме того, я думаю, что категории и триггеры в вашем DTO должны быть определены как Set s, запрещающие дубликаты; это будет сделать операцию слияния намного проще:

private Set<String> categories; 
private Set<String> triggers; 

Предполагая, что DTO обеспечивает аксессоров (getCategories/getTriggers) для указанных полей (и что поля никогда не null), слияние теперь может быть реализована следующим образом:

public static void mergeOrPut(Map<DTO,DTO> dtos, DTO dto) { 
    if (dtos.containsKey(dto)) { 
     DTO existing = dtos.get(dto); 
     existing.getCategories().addAll(dto.getCategories()); 
     existing.getTriggers().addAll(dto.getTriggers()); 
    } else { 
     dtos.put(dto, dto); 
    } 
} 

Приведенный выше код может быть легко модифицирован для работы с Map<Integer, DTO>, в этом случае вам не нужно переопределить equals и hashCode в DTO классе.

+2

Это не будет * объединять * объекты с одинаковыми идентификаторами. Он просто опустит один из тех, чей идентификатор в противном случае был бы дублирован. Кроме того, я сомневаюсь, что разумная реализация 'hashCode' и' equals' возможна, когда она основана только на ID. – Marco13

+0

Aggree with @ Marco13, мне нужно не только удалять дубликаты, но и объединять объекты с одним и тем же идентификатором. –

+0

@ Marco13, реализация 'equals', основанная только на идентификаторе, имеет очень большой смысл, например. когда DTO моделирует объект, который соответствует строке в таблице базы данных. –

2

Создайте Map<Integer, DTO> и поместите свой id как ключ и объект как DTO. И перед тем, как нанести на карту, просто проверьте, содержит ли он уже этот ключ, и если он содержит этот ключ, тогда вытащите объект DTO для этого ключа и сгруппируйте категории и триггеры со старым объектом.

1

Если вы настаиваете, чтобы использовать лямбда-выражения, вы можете сделать следующее:

Set<X> x = new TreeSet<>((o1, o2) -> 
     ((X)o1).getId().equals(((X)o2).getId()) ? 0 : 1); 

List<X> list = new ArrayList<>(set.addAll(x)); 

Это создаст набор с уникальными объектами в соответствии с их идентификаторами. Затем для каждого объекта в list найдите соответствующий из исходного списка и объедините внутренние коллекции.

2

Одним из возможных решений, предложенным в документе answer by Naman Gala, является использование Map от идентификаторов к объектам и объединение слияния сущностей при их одинаковом идентификаторе.

Это реализуется здесь в методе mergeById, с некоторой фиктивной/например, вход где

  • две организации должны быть объединены (в связи с тем же ID)
  • два лица равны (они также будут быть «объединены», что дает тот же результат, что и один из входов)

.

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collection; 
import java.util.HashMap; 
import java.util.LinkedHashSet; 
import java.util.List; 
import java.util.Map; 
import java.util.Objects; 


public class MergeById 
{ 
    public static void main(String[] args) 
    { 
     List<Entity> entities = new ArrayList<Entity>(); 
     entities.add(new Entity("0", "A", "X", "-1", 
      Arrays.asList("C0", "C1"), Arrays.asList("T0", "T1"))); 
     entities.add(new Entity("0", "A", "X", "-1", 
      Arrays.asList("C2", "C3"), Arrays.asList("T2"))); 
     entities.add(new Entity("1", "B", "Y", "-2", 
      Arrays.asList("C0"), Arrays.asList("T0", "T1"))); 
     entities.add(new Entity("1", "B", "Y", "-2", 
      Arrays.asList("C0"), Arrays.asList("T0", "T1"))); 
     entities.add(new Entity("2", "C", "Z", "-3", 
      Arrays.asList("C0", "C1"), Arrays.asList("T1"))); 

     System.out.println("Before merge:"); 
     for (Entity entity : entities) 
     { 
      System.out.println(entity); 
     } 

     List<Entity> merged = mergeById(entities); 

     System.out.println("After merge:"); 
     for (Entity entity : merged) 
     { 
      System.out.println(entity); 
     } 
    } 

    private static List<Entity> mergeById(Iterable<? extends Entity> entities) 
    { 
     Map<String, Entity> merged = new HashMap<String, Entity>(); 
     for (Entity entity : entities) 
     { 
      String id = entity.getId(); 
      Entity present = merged.get(id); 
      if (present == null) 
      { 
       merged.put(id, entity); 
      } 
      else 
      { 
       merged.put(id, Entity.merge(present, entity)); 
      } 
     } 
     return new ArrayList<Entity>(merged.values()); 
    } 

} 


class Entity 
{ 
    private String id; 
    private String text; 
    private String query; 
    private String locatorId; 
    private Collection<String> categories; 
    private Collection<String> triggers; 

    Entity() 
    { 
     categories = new LinkedHashSet<String>(); 
     triggers = new LinkedHashSet<String>(); 
    } 

    Entity(String id, String text, String query, String locatorId, 
     Collection<String> categories, Collection<String> triggers) 
    { 
     this.id = id; 
     this.text = text; 
     this.query = query; 
     this.locatorId = locatorId; 
     this.categories = categories; 
     this.triggers = triggers; 
    } 

    String getId() 
    { 
     return id; 
    } 

    static Entity merge(Entity e0, Entity e1) 
    { 
     if (!Objects.equals(e0.id, e1.id)) 
     { 
      throw new IllegalArgumentException("Different id"); 
     } 
     if (!Objects.equals(e0.text, e1.text)) 
     { 
      throw new IllegalArgumentException("Different text"); 
     } 
     if (!Objects.equals(e0.query, e1.query)) 
     { 
      throw new IllegalArgumentException("Different query"); 
     } 
     if (!Objects.equals(e0.locatorId, e1.locatorId)) 
     { 
      throw new IllegalArgumentException("Different id"); 
     } 
     Entity e = new Entity(e0.id, e0.text, e0.query, e0.locatorId, 
      new LinkedHashSet<String>(), new LinkedHashSet<String>()); 
     e.categories.addAll(e0.categories); 
     e.categories.addAll(e1.categories); 
     e.triggers.addAll(e0.triggers); 
     e.triggers.addAll(e1.triggers); 
     return e; 
    } 

    @Override 
    public String toString() 
    { 
     return "Entity [id=" + id + ", text=" + text + ", query=" + query + 
      ", locatorId=" + locatorId + ", categories=" + categories + 
      ", triggers=" + triggers + "]"; 
    } 

} 

Выход

Before merge: 
Entity [id=0, text=A, query=X, locatorId=-1, categories=[C0, C1], triggers=[T0, T1]] 
Entity [id=0, text=A, query=X, locatorId=-1, categories=[C2, C3], triggers=[T2]] 
Entity [id=1, text=B, query=Y, locatorId=-2, categories=[C0], triggers=[T0, T1]] 
Entity [id=1, text=B, query=Y, locatorId=-2, categories=[C0], triggers=[T0, T1]] 
Entity [id=2, text=C, query=Z, locatorId=-3, categories=[C0, C1], triggers=[T1]] 
After merge: 
Entity [id=0, text=A, query=X, locatorId=-1, categories=[C0, C1, C2, C3], triggers=[T0, T1, T2]] 
Entity [id=1, text=B, query=Y, locatorId=-2, categories=[C0], triggers=[T0, T1]] 
Entity [id=2, text=C, query=Z, locatorId=-3, categories=[C0, C1], triggers=[T1]] 

Что касается просьбы сделать это с лямбды: Это, наверное, можно написать какой-нибудь каверзный entities.stream().collect(...) приложения. Но поскольку это не было главной целью вопроса, я оставлю эту часть ответа кому-то еще (но не пропущу этого небольшого намека: просто потому, что вы можете это не значит, что вам нужно. Иногда цикл просто отлично).

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

+0

Спасибо @ Marco13, я буду использовать этот подход как более эффективный для меня (позже добавьте один материал Lambda самостоятельно) –

4

Слиянием объектов по указанному ключу с использованием API потока является довольно просто. Во-первых, определить метод merge в вашем Entity классе, как это:

public Entity merge(Entity other) { 
    this.categories.addAll(other.categories); 
    this.triggers.addAll(other.triggers); 
    return this; 
} 

Тогда вы можете создать пользовательские группировки коллектора:

import static java.util.stream.Collectors.*; 

public static Collection<Entity> mergeAll(Collection<Entity> input) { 
    return input.stream() 
       .collect(groupingBy(Entity::getId, 
        collectingAndThen(reducing(Entity::merge), Optional::get))) 
       .values(); 
} 

Здесь группа Entity элементы по результату getId метода и вниз по течению коллектора просто вызывает Entity.merge(), когда встречается то же самое id (нам нужно развернуть на Optional дополнительно). Никаких специальных hashCode() или equals() реализация необходима для Entity в этом решении.

Обратите внимание, что это решение изменяет существующие без помех объекты Entity. Если это нежелательно, создайте новый Entity в методе merge() и верните его вместо этого (как в ответе @ Marco13).

+1

или 'toMap (Entity :: getId, e-> e, Entity :: merge)' в качестве альтернативы 'groupingBy' -' сокращение' – Misha

+1

@ Миша, спасибо. Вероятно, у меня слишком много мышления «groupingBy» и всегда забывайте об альтернативе «toMap». –

+0

Обратите внимание, что если 'categories' и' триггеры' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' ' –

Смежные вопросы