Как быстро сравнить объекты в одном массиве с объектами в другом за время, не большее O(n^1.5)?

Question

Решаю сложную (для меня) задачу. Вывел подзадачу - на вход дают два массива некоторых объектов. На выходе - нужно дать массив перезаписанных объектов:

  public List <Experiment> merge(List <Experiment> first, List <Experiment> second){
     return ...
    }

Class Experiment{
private String code; //номер объекта - неизменяемый
int value;  
//Дальше идут конструкторы, переопределённый equals и hashocode, 
}

Перезаписываем так: там где коды одинаковые - засовываем новый объект, в котором value = value1+value2 (у объектов с value1 и value2 - коды одинаковые, value - принадлежит объекту в исходящем массиве, value1 - объекту в первом входящем массиве, value2 - объекту во втором входящем массиве). Делаем допущение, что в отдельном массиве нет объекта с одинаковым code.

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

Наивный алгоритм (примерно не дебажил):

     public List <Experiment> merge(List <Experiment> first, List<Experiment> second){
    List <Experiment> out = new ArrayList();
    for(Experiment fe : first){
        outer:
        for(Experiment se : second){
            if(fe.code.equals(se.code)){
                out.add(new Experiment(fe.code, fe.value+se.value));
                second.remove(se); //Удаляем из второго массива тот, у которого код совпал с первым
                continue outer;
            }
        }
        out.add(fe); //Добавляем из первого массива, если код объекта уникален
}
    out.addAll(second); //добавляем весь второй массив (оставшиеся после сраквнения элеенты)
    return out;
}

Наивный алгоритм - с обходом каждого и проверки каждого, не интересен. Потому что будет работать за O(n^2);

Вопрос: подскажите идею для алгоритма, который сравнит объекты и перезапишет их, такой чтобы работал за O(n^1.5) или меньше. Желательно, такой, чтобы его можно было бы распаралеллить средствами Java 8 или просто критическими секциями.

Answer 1

Map<String, Experiment> для второго массива - O(n).

Предположение: значение code уникально в каждом списке.

Map<String, Experiment> mapSecond = new HashMap<>();
for (Experiment se : second) {
  mapSecond.put(se.code, se.value);
}
for (Experiment fe : first) {
  Experiment se = mapSecond.get(fe.code);
  if (se != null) {
    ...
  }
}

Answer 2

Основываясь на предположении, что code - уникально, действительно стоит задействовать Map:

public List<Experiment> merge(List<Experiment> first, List<Experiment> second) {
    Map<String, Experiment> secondMap = second.stream()
            .collect(Collectors.toMap(item -> item.code, item -> item)); // создаем map второго списка для быстрого доступа к его элементам.

    return IntStream.range(0, first.size()) 
            .boxed()
            .map(i -> { // проходим по элементам первого списка
                Experiment itemFirst = first.get(i);
                Experiment itemSecond = secondMap.getOrDefault(itemFirst.code, null); // учитывая замапленные элементы второго.
                return itemSecond == null ? new Experiment(itemFirst.code, itemFirst.value) : new Experiment(itemFirst.code, itemFirst.value + itemSecond.value);
                // и наполняем результирующий список.
            })
            .collect(Collectors.toList());
}

Вариант 2, более компактный:

public List<Experiment> merge(List<Experiment> first, List<Experiment> second) {
    Map<String, Experiment> secondMap = second.stream()
            .collect(Collectors.toMap(item -> item.code, item -> item));
    // в предположении, что создание нового элемента может быть сложнее,
    // чем просто value1+value2, оставим в значениях Map не int value, а элемент целиком
    return first.stream()
            .map(itemFirst->{ // проходя повсем элементам первого списка
                Experiment itemSecond = secondMap.getOrDefault(itemFirst.code, null);
                // ищем в map второго списка подходящий
                return itemSecond == null ? new Experiment(itemFirst.code, itemFirst.value) : new Experiment(itemFirst.code, itemFirst.value + itemSecond.value);
                // и на его основе создаем элемент для выходного списка
            })
            .collect(Collectors.toList());
}

БЛОГ НА HUSL

Как быстро сравнить объекты в одном массиве с объектами в другом за время, не большее O(n^1.5)?

Ответы (2 шт):