0

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

  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 или просто критическими секциями.

2 ответа 2

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());
}
2
  • Очень хорошо, спасибо. Подождем другие ответы. Я идею уловил 22 янв 2021 в 15:04
  • Мне ваш вариант больше понравился потому что здесь есть лямбда выражения. 23 янв 2021 в 20:25
2

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) {
    ...
  }
}
4
  • вы похоже понимаете - а я нуль. Можете хоть ссылочку дать на аналогичную задачу или где гуглить показать. Потому что один коллега мне уже сегодня говорил, "используй хэшмапу". Но я ровным счётом не понял что к чему. 22 янв 2021 в 14:39
  • Или хотя бы в общих словах (без кода) подскажите, как алгоритм должен работать. 22 янв 2021 в 14:40
  • @Andrew Kachalin Первая часть складывает элементы второго списка в map. Вторая часть для каждого элемента первого списка проверяет, есть ли такой код в мапе, возвращая значение value в случае успеха. Что делать с этим значением, Вы же уже знаете. По сути это не отличается от Ваших циклов, только поиск быстрый
    – MBo
    22 янв 2021 в 15:00
  • Очень хорошо, спасибо. Подождем другие ответы. Я идею уловил. 22 янв 2021 в 15:03

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.