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