Рекурсивное использование Stream.flatMap() - программирование
Подтвердить что ты не робот

Рекурсивное использование Stream.flatMap()

Рассмотрим следующий класс:

public class Order {

    private String id;

    private List<Order> orders = new ArrayList<>();

    @Override
    public String toString() {
        return this.id;
    }

    // getters & setters
}

ПРИМЕЧАНИЕ. Важно отметить, что я не может изменить этот класс, потому что я потребляю его из внешнего API.

Также рассмотрим следующую иерархию заказов:

Order o1 = new Order();
o1.setId("1");
Order o11 = new Order();
o11.setId("1.1");
Order o111 = new Order();
o111.setId("1.1.1");
List<Order> o11Children = new ArrayList<>(Arrays.asList(o111));
o11.setOrders(o11Children);

Order o12 = new Order();
o12.setId("1.2");
List<Order> o1Children = new ArrayList<>(Arrays.asList(o11, o12));
o1.setOrders(o1Children);

Order o2 = new Order();
o2.setId("2");
Order o21 = new Order();
o21.setId("2.1");
Order o22 = new Order();
o22.setId("2.2");
Order o23 = new Order();
o23.setId("2.3");
List<Order> o2Children = new ArrayList<>(Arrays.asList(o21, o22, o23));
o2.setOrders(o2Children);

List<Order> orders = new ArrayList<>(Arrays.asList(o1, o2));

Что можно визуально представить таким образом:

1
1.1
1.1.1
1.2
2
2.1
2.2
2.3

Теперь я хочу сгладить эту иерархию заказов в List, чтобы получить следующее:

[1, 1.1, 1.1.1, 1.2, 2, 2.1, 2.2, 2.3]

Мне удалось сделать это рекурсивно, используя flatMap() (вместе со вспомогательным классом) следующим образом:

List<Order> flattened = orders.stream()
    .flatMap(Helper::flatten)
    .collect(Collectors.toList());

Это вспомогательный класс:

public final class Helper {

    private Helper() {
    }

    public static Stream<Order> flatten(Order order) {
        return Stream.concat(
            Stream.of(order), 
            order.getOrders().stream().flatMap(Helper::flatten)); // recursion here
    }
}

Следующая строка:

System.out.println(flattened);

Производит следующий вывод:

[1, 1.1, 1.1.1, 1.2, 2, 2.1, 2.2, 2.3]

Пока все хорошо. Результат абсолютно правильный.

Однако после прочтения этого вопроса у меня возникли некоторые проблемы в отношении использования flatMap() в рекурсивном методе. В частности, я хотел знать, как расширяется поток (если этот термин). Поэтому я изменил класс Helper и использовал peek(System.out::println), чтобы проверить это:

public static final class Helper {

    private Helper() {
    }

    public static Stream<Order> flatten(Order order) {
        return Stream.concat(
            Stream.of(order), 
            order.getOrders().stream().flatMap(Helper::flatten))
        .peek(System.out::println);
    }
}

И результат был:

1
1.1
1.1
1.1.1
1.1.1
1.1.1
1.2
1.2
2
2.1
2.1
2.2
2.2
2.3
2.3

Я не уверен, что это вывод, который должен быть напечатан.

Итак, мне интересно, нормально ли позволить промежуточным потокам содержать повторяющиеся элементы. Кроме того, каковы плюсы и минусы такого подхода? Правильно ли, в конце концов, использовать flatMap() таким образом? Есть ли лучший способ добиться того же?

4b9b3361

ОТВЕТЫ

Ответ 1

Хорошо, я использовал тот же шаблон с общим классом Tree и не имел с ним неправильного чувства. Единственное различие заключается в том, что сам класс Tree предложил методы children() и allDescendants(), возвращая a Stream, а последнее здание на первом. Это связано с "Должен ли я возвращать коллекцию или поток?" и "Именование java-методов, возвращающих потоки" .

С точки зрения Stream нет разницы между flatMap для детей другого типа (т.е. при обходе свойства) и flatMap для детей того же типа. Также нет проблем, если возвращаемый поток снова содержит один и тот же элемент, так как нет никакой связи между элементами потоков. В принципе, вы можете использовать flatMap как операцию filter, используя шаблон flatMap(x -> condition? Stream.of(x): Stream.empty()). Его также можно использовать для дублирования элементов, таких как этот ответ.

Ответ 2

У вас нет проблем с использованием flatMap таким образом. Каждая из промежуточных шагов в потоке совершенно независима (по дизайну), поэтому в вашей рекурсии нет риска. Главное, на что нужно обратить внимание, - это все, что может повлиять на основной список при его потоковой передаче. В вашем случае это не похоже на риск.

В идеале вы сделаете эту рекурсивную часть класса Order:

class Order {
    private final List<Order> subOrders = new ArrayList<>();

    public Stream<Order> streamOrders() {
        return Stream.concat(
            Stream.of(this), 
            subOrders.stream().flatMap(Order::streamOrders));
    }
}

Затем вы можете использовать orders.stream().flatMap(Order::streamOrders), что для меня кажется более естественным, чем использование вспомогательного класса.

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

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

Order o1 = new Order();
o1.setOrders(Arrays.asList(o1));
o1.streamOrders();

Существует множество хороших шаблонов, позволяющих избежать подобных проблем, поэтому, пожалуйста, спросите, нужна ли вам помощь в этой области.

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

class SafeOrder extends Order {
    public SafeOrder(String id) {
        setId(id);
    }

    public void addOrder(SafeOrder subOrder) {
        getOrders().add(subOrder);
    }

    public Stream<SafeOrder> streamOrders() {
        return Stream.concat(Stream.of(this), subOrders().flatMap(SafeOrder::streamOrders));
    }

    private Stream<SafeOrder> subOrders() {
        return getOrders().stream().map(o -> (SafeOrder)o);
    }
}

Это довольно безопасный бросок, потому что вы ожидаете, что пользователи будут использовать addOrder. Не уверены в надежности, поскольку они все равно могут вызвать getOrders и добавить Order, а не SafeOrder. Опять же есть шаблоны, чтобы предотвратить это, если вы заинтересованы.