Самый быстрый способ объединить 2 коллекции в Java на основе ключа

#join #collections #java-11

#Присоединиться #Коллекции #java-11

Вопрос:

Я ищу самый быстрый способ объединить две несортированные коллекции на основе общего id ключа.

Ниже O(N^2) реализация

 for (Person per : pers) {  for (Data data : datas) {  if (per.getId().equals(data.getId())) {  per.getData().add(data);  }  }   }

Я ищу максимально быстрый способ (и наименьший объем памяти) для достижения этого результата, возможно, O(N). Дубликаты должны быть удалены из per.getData(). На данный момент per.getData () — это набор хэшей

Есть идеи, как это можно оптимизировать ? Я использую java 11

1. » Я ищу как можно более быстрый способ (и как можно меньший объем памяти) » Это противоречивые требования. Почти всегда вы обнаружите, что существует компромисс между производительностью и памятью. Выбери одну.

Ответ №1:

Выполните один проход по лицам, чтобы собрать их в карту для последующего поиска O(1), затем выполните один проход по данным, добавив их к человеку:

 Maplt;Object, Persongt; people = pers.stream()  .collect(Collectors.toMap(Person::getId, p -gt; p)); datas.forEach(d -gt; people.get(d.getId()).add(d));

Если данные могут иметь совпадающего пользователя, отфильтруйте несопоставимые данные:

 datas.stream()  .filter(d -gt; people.containsKey(d.getId()))  .forEach(d -gt; people.get(d.getId()).add(d));

Оба способа-O(m n) (m людей, n данных), потому что все операции с картой-O(1).

Вы упомянули, что дубликаты должны быть удалены из данных человека. Будучи хэш-набором (или любым набором), дубликаты автоматически удаляются, если equals() hashCode() данные правильно закодированы и закодированы.

1. Это работает. Спасибо! Интересно, есть ли способ добавить все сразу вместо каждого ?

2. @эй, нет, волшебного способа нет: место назначения каждого файла должно быть найдено индивидуально. Любая попытка сделать это одним процессом приведет к усложнению времени.

Ответ №2:

Вот линейный подход (O(n)), который лучше, чем O(n^2), но будет использовать память.

Создайте хэш-картуlt;PersonID, personObjectgt;, затем выполните цикл для людей и вставьте их в карту.
Зацикливайтесь на данных и проверяйте, присутствуют ли данные в хэш-карте. Если он существует, получите объект personObject и добавьте объект DataObject в его хэш-набор.

 HashMaplt;Integer, Persongt; mp = new HashMaplt;gt;(); for (Person per : pers) {  mp.put(per.getId(), per); } for (Data data : datas) {  if (mp.get(data.getId()) != null) {  Person person = mp.get(data.getId());  person.getData().add(data);  mp.put(person.getId(), person);  } }

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