代码之家 › 专栏 › 技术社区 › fps

Stream.flatMap()的递归使用

java-stream java-8 java

fps · 技术社区 · 9 年前

考虑以下类别:

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());

这是helper类:

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]

到现在为止,一直都还不错。结果是绝对正确的。

然而 after reading this question ,我对 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() 这边有没有更好的方法来实现这一点?

2 回复 | 直到 7 年前

Community Egal 7 年前

嗯,我用了相同的模式 Tree 在课堂上,我没有错误的感觉。唯一的区别是 树 类本身提供了 children() 和 allDescendants() 方法,两者都返回 Stream 后者在前者的基础上建立。这与 âShould I return a Collection or a Stream?â 和 âNaming java methods that return streamsâ .

从 流动 s的观点 flatMap 不同类型的子级(即,当遍历属性时)和 平面地图 给同一类型的孩子。如果返回的流再次包含相同的元素,也没有问题,因为流的元素之间没有关系。原则上,您可以使用 平面地图 作为一个 filter 操作,使用模式 flatMap(x -> condition? Stream.of(x): Stream.empty()) 。也可以使用它复制元素,如 this answer .

Tagir Valeev 9 年前

你使用 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 允许使用集合字段而不是字段的getter的方法。如果方法的用户不需要知道任何有关基础集合的信息,或者不需要能够更改它,那么返回流是方便和安全的。

我会注意到,在您的数据结构中有一个风险,您应该意识到:一个订单可能是其他几个订单的一部分,甚至可能是其自身的一部分。这意味着导致无限递归和堆栈溢出是非常简单的:

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

有很多好的模式可以避免这些问题,所以请询问您是否需要在这方面的帮助。

你指出你不能改变 顺序 班在这种情况下,我建议您扩展它以创建自己的安全版本:

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 并添加 顺序 而不是 SafeOrder 。如果你感兴趣的话,还有一些模式可以防止这种情况。