Подтвердить что ты не робот

Группировать и уменьшать список объектов

У меня есть список объектов со многими дублирующимися и некоторыми полями, которые необходимо объединить. Я хочу свести это к списку уникальных объектов, используя только потоки Java 8 (я знаю, как это сделать с помощью old-skool, но это эксперимент.)

Это то, что я имею прямо сейчас. Мне это не очень нравится, потому что построение карт кажется посторонним, а коллекция values ​​() - это представление карты поддержки, и вам нужно обернуть ее в новый ArrayList<>(...), чтобы получить более конкретную коллекцию. Есть ли лучший подход, возможно, используя более общие операции сокращения?

    @Test
public void reduce() {
    Collection<Foo> foos = Stream.of("foo", "bar", "baz")
                     .flatMap(this::getfoos)
                     .collect(Collectors.toMap(f -> f.name, f -> f, (l, r) -> {
                         l.ids.addAll(r.ids);
                         return l;
                     })).values();

    assertEquals(3, foos.size());
    foos.forEach(f -> assertEquals(10, f.ids.size()));
}

private Stream<Foo> getfoos(String n) {
    return IntStream.range(0,10).mapToObj(i -> new Foo(n, i));
}

public static class Foo {
    private String name;
    private List<Integer> ids = new ArrayList<>();

    public Foo(String n, int i) {
        name = n;
        ids.add(i);
    }
}
4b9b3361

ОТВЕТЫ

Ответ 1

Если вы сломаете группировку и уменьшаете количество шагов вверх, вы можете получить что-то более чистое:

Stream<Foo> input = Stream.of("foo", "bar", "baz").flatMap(this::getfoos);

Map<String, Optional<Foo>> collect = input.collect(Collectors.groupingBy(f -> f.name, Collectors.reducing(Foo::merge)));

Collection<Optional<Foo>> collected = collect.values();

Это предполагает несколько удобных методов в вашем классе Foo:

public Foo(String n, List<Integer> ids) {
    this.name = n;
    this.ids.addAll(ids);
}

public static Foo merge(Foo src, Foo dest) {
    List<Integer> merged = new ArrayList<>();
    merged.addAll(src.ids);
    merged.addAll(dest.ids);
    return new Foo(src.name, merged);
}

Ответ 2

Как уже отмечалось в комментариях, карта является очень естественной вещью для использования, когда вы хотите идентифицировать уникальные объекты. Если вам нужно всего лишь найти уникальные объекты, вы можете использовать метод Stream::distinct. Этот метод скрывает тот факт, что есть карта, но, по-видимому, она использует внутреннюю карту, как намекала этот вопрос, которая показывает, что вы должны реализовать метод hashCode или distinct может вести себя неправильно.

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

Легко использовать потоки для обработки значений карты и превратить ее обратно в ArrayList. Я показываю, что в этом ответе, а также для того, чтобы избежать появления Optional<Foo>, который появляется в одном из других ответов.

public void reduce() {
    ArrayList<Foo> foos = Stream.of("foo", "bar", "baz").flatMap(this::getfoos)
            .collect(Collectors.collectingAndThen(Collectors.groupingBy(f -> f.name,
            Collectors.reducing(Foo.identity(), Foo::merge)),
            map -> map.values().stream().
                collect(Collectors.toCollection(ArrayList::new))));

    assertEquals(3, foos.size());
    foos.forEach(f -> assertEquals(10, f.ids.size()));
}

private Stream<Foo> getfoos(String n) {
    return IntStream.range(0, 10).mapToObj(i -> new Foo(n, i));
}

public static class Foo {
    private String name;
    private List<Integer> ids = new ArrayList<>();

    private static final Foo BASE_FOO = new Foo("", 0);

    public static Foo identity() {
        return BASE_FOO;
    }

    // use only if side effects to the argument objects are okay
    public static Foo merge(Foo fooOne, Foo fooTwo) {
        if (fooOne == BASE_FOO) {
            return fooTwo;
        } else if (fooTwo == BASE_FOO) {
            return fooOne;
        }
        fooOne.ids.addAll(fooTwo.ids);
        return fooOne;
    }

    public Foo(String n, int i) {
        name = n;
        ids.add(i);
    }
}

Ответ 3

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

К сожалению, нет метода Stream API, который бы позволял вам делать это легко и эффективно. Одним из возможных решений является создание пользовательского коллектора следующим образом:

public static List<Foo> withCollector(Stream<Foo> stream) {
    return stream.collect(Collector.<Foo, List<Foo>>of(ArrayList::new,
             (list, t) -> {
                 Foo f;
                 if(list.isEmpty() || !(f = list.get(list.size()-1)).name.equals(t.name))
                     list.add(t);
                 else
                     f.ids.addAll(t.ids);
             },
             (l1, l2) -> {
                 if(l1.isEmpty())
                     return l2;
                 if(l2.isEmpty())
                     return l1;
                 if(l1.get(l1.size()-1).name.equals(l2.get(0).name)) {
                     l1.get(l1.size()-1).ids.addAll(l2.get(0).ids);
                     l1.addAll(l2.subList(1, l2.size()));
                 } else {
                     l1.addAll(l2);
                 }
                 return l1;
             }));
}

Мои тесты показывают, что этот сборщик всегда быстрее, чем собирать карту (до 2x в зависимости от среднего количества повторяющихся имен), как в последовательном, так и в параллельном режимах.

Другим подходом является использование библиотеки StreamEx, которая предоставляет кучу методов частичного сокращения, включая collapse:

public static List<Foo> withStreamEx(Stream<Foo> stream) {
    return StreamEx.of(stream)
            .collapse((l, r) -> l.name.equals(r.name), (l, r) -> {
                l.ids.addAll(r.ids);
                return l;
            }).toList();
}

Этот метод принимает два аргумента: a BiPredicate, который применяется для двух смежных элементов и должен возвращать true, если элементы должны быть объединены, и BinaryOperator, который выполняет слияние. Это решение немного медленнее в последовательном режиме, чем у пользовательского коллектора (параллельно результаты очень похожи), но он все же значительно быстрее, чем toMap, и он более простой и несколько более гибкий, поскольку collapse является промежуточной операцией, поэтому вы можете собирать по-другому.

Опять оба этих решения работают только в том случае, если известно, что foos с тем же именем являются смежными. Плохая идея сортировать входной поток по имени foo, а затем использовать эти решения, потому что сортировка резко снизит производительность, делая ее медленнее, чем решение toMap.

Ответ 4

Как уже указывалось другими, промежуточный Map неизбежен, так как это способ найти объекты для слияния. Кроме того, вы не должны изменять исходные данные во время сокращения.

Тем не менее, вы можете достичь обоих без создания нескольких экземпляров Foo:

List<Foo> foos = Stream.of("foo", "bar", "baz")
                 .flatMap(n->IntStream.range(0,10).mapToObj(i -> new Foo(n, i)))

                 .collect(collectingAndThen(groupingBy(f -> f.name),
                    m->m.entrySet().stream().map(e->new Foo(e.getKey(),
                       e.getValue().stream().flatMap(f->f.ids.stream()).collect(toList())))
                    .collect(toList())));

Это предполагает, что вы добавляете конструктор

    public Foo(String n, List<Integer> l) {
        name = n;
        ids=l;
    }

в ваш класс Foo, как и должно быть, если Foo действительно должен иметь возможность содержать список идентификаторов. Как побочная заметка, наличие типа, который служит как единый элемент, так и контейнер для объединенных результатов, кажется мне неестественным. Именно поэтому код оказывается настолько сложным.

Если исходные элементы имели один id, использование чего-то вроде groupingBy(f -> f.name, mapping(f -> id, toList()), а затем сопоставление записей (String, List<Integer>) с объединенными элементами было достаточно.

Так как это не так, и Java 8 не имеет коллектора flatMapping, шаг flatmapping перемещается на второй шаг, делая это выглядят намного сложнее.

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