Разделить набор на подмножества объектов, имеющих одинаковое поле?

Question

В настоящее время я пытаюсь реализовать структуру данных в java и хотел бы разделить набор входных объектов на различные подмножества объектов, имеющих одинаковое поле.

An example use case:

Мы хотим разделить список лиц на подсписок лиц, родившихся в определенный день.

Input: человек1, родившийся в 1990 году, человек2, родившийся в 2000 году, человек3, родившийся в 1990 году.

Output:

1 -> person1, person3

2 -> person2

public Map<Integer, List<Foo>> getIntToFooMap(List<Foo> foos) { 
    Map<Integer, List<Foo>> map = new TreeMap<>(); // need keys to be automatically ordered.
    List<Foo> foosWithSameSetId = new ArrayList<>();
    if (!foos.isEmpty) { 
       for (Foo foo: foos) {
           for (Foo foo2: foos) {
               if (foo.getSetId().equals(foo2.getSetId())) {
                   foosWithSameSetId.add(foo2);
               }
           }
        map.put(foo.getSetId(), foosWithSameSetId);
        foosWithSameSetId.clear();
       }
    }
  return map;
 }

Приведенный выше код не является оптимальным, сложность по времени является квадратичной c, а также не потокобезопасен. Может кто-нибудь сказать мне о лучшем способе разделить Список или Набор на подмножества объектов, имеющих одинаковое поле, в данном случае setId.

Answer 1

Во-первых, нет необходимости во вложенном l oop. Вы просто получите или создадите набор текущих foo setId и добавите к нему foo:

for (Foo foo : foos) {
    map.computeIfAbsent(foo.getSetId(), i -> new ArrayList<>()).add(foo);
}

Что будет эквивалентно:

for (Foo foo : foos) {
    List<Foo> list = map.get(foo.getSetId());
    if(null == list) list = new ArrayList<>();
    list.add(foo);
}

Теперь вам нужно учитывать сложность времени для реализации вашей карты .

В качестве альтернативы потоковый сборщик groupingBy может добавить краткости вашему коду:

return foos.stream().collect(
        Collectors.groupingBy(Foo::getSetId, TreeMap::new, Collectors.toList()));

Answer 2

Ответ ernest_k правильный и четкий. Вот еще код, полный пример.

Сначала определите класс для Person.

package work.basil.example;

import java.time.LocalDate;
import java.util.Objects;

public class Person
{
    // ----------|  Member fields  |----------------------
    public String name;
    public LocalDate birthdate;

    // ----------|  Constructor  |----------------------
    public Person ( String name , LocalDate birthdate )
    {
        this.name = Objects.requireNonNull( name );
        this.birthdate = Objects.requireNonNull( birthdate );
    }

    // ----------|  Object  |----------------------

    @Override
    public String toString ( )
    {
        return "Person{ " +
                "name='" + name + '\'' +
                " | birthdate=" + birthdate +
                " }";
    }

    @Override
    public boolean equals ( Object o )
    {
        if ( this == o ) return true;
        if ( o == null || getClass() != o.getClass() ) return false;
        Person person = ( Person ) o;
        return name.equals( person.name ) &&
                birthdate.equals( person.birthdate );
    }

    @Override
    public int hashCode ( )
    {
        return Objects.hash( name , birthdate );
    }
}

Заполните некоторые примеры данных. Синтаксис Set.of, добавленный к Java 9, дает нам простой синтаксис литералов.

Set < Person > persons = Set.of(
        new Person( "Alice" , LocalDate.of( 1990 , Month.JANUARY , 23 ) ) ,
        new Person( "Bob" , LocalDate.of( 2000 , Month.FEBRUARY , 24 ) ) ,
        new Person( "Carol" , LocalDate.of( 1990 , Month.MARCH , 25 ) )
);

Параллелизм

Определите Map, который мы хотим заполнить. Вы упомянули параллелизм как проблему, то есть совместное использование этой карты между потоками. Поэтому мы должны использовать один из двух классов, связанных с Java, которые реализуют интерфейс ConcurrentMap.

Вот таблица graphi c, которую я сделал и показывающая атрибуты различных Map реализации в комплекте с Java.

Здесь мы решили использовать ConcurrentHashMap. Альтернатива, ConcurrentSkipListMap может быть лучше, если у вас есть большое количество объектов, или если вы хотите сохранить ключи (Year в нашем случае) в определенном порядке.

Map < Year, List < Person > > yearToListOfPersonsMap = new ConcurrentHashMap <>();

Типы данных

Обратите внимание на правильное использование типов данных. Java предлагает класс Year для представления всего года. Поэтому мы должны использовать это. Это делает наш код более самодокументируемым.

В классе Person мы представляем дату рождения, используя LocalDate. Этот класс предназначен только для даты без времени и без часового пояса.

Мультикарта

Мы извлечем год из даты рождения каждого человека в качестве ключа к нашей карте. Значением является List из Person объектов, к которым мы добавляем рассматриваемый объект person.

Если вы хотите исключить любые возможные дубликаты Person объектов из коллекции, вы можете использовать Set здесь, а не List.

Метод Map::computeIfAbsent, добавленный в Java 8, выполняет работу так называемой multimap , карты, где ключ ведет к набору значения, а не одно значение. В качестве альтернативы, вы можете использовать реализацию нескольких карт сторонних производителей, таких как Google Guava .

for ( Person person : persons )
{
    yearToListOfPersonsMap.computeIfAbsent(
            Year.from( person.birthdate ) ,
            ( ( Year key ) -> new ArrayList <>() )
    ).add( person )
    ;
}

Дамп в консоль.

System.out.println( "yearToListOfPersonsMap = " + yearToListOfPersonsMap );

yearToListOfPersonsMap = {2000 = [Person {name = 'Bob' | дата рождения = 2000-02-24}], 1990 = [Персона {имя = 'Алиса' | дата рождения = 1990-01-23}, Персона {имя = 'Кэрол' | дата рождения = 1990-03-25}]}

Answer 3

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