流过滤器的时间复杂度 [英] Time complexity of stream filter

问题描述

我有这样的代码：

List<Listing> Listings = new ArrayList<>();
Listings.add(listing1);
Listings.add(listing2);
...
...
...

Listing listing= listings.stream()
                .filter(l -> l.getVin() == 456)
                .findFirst();

我的问题是过滤过程的时间复杂度是多少？如果它是O（n），我的直觉是将它转换为HashSet，就像数据结构一样，这样时间复杂度可能变为O（1），是否有一种优雅的方法来实现 with streams ？

My question is what is the time complexity of the filter process? If it is O(n), my intuition is to convert it into HashSet like data structures so that the time complexity could become O(1), Is there an elegant way to do this with streams?

推荐答案

O（n）。流过滤在内部使用迭代。

It is O(n). The stream filtering uses iteration internally.

您可以将其转换为地图，如下所示：

You could convert it to a map as follows:

Map<Integer, Listing > mapOfVinToListing = listings.stream().collect(Collectors.toMap(Listing::getVin, Functions.identity()); // Assuming vin is unique per listing
mapOfVinToListing.get(456);// O(1)

但是，转换过程也是O（n）。所以，如果你只需要做这一次，使用过滤器。如果你需要多次查询同一个列表，那么将它转换为地图可能有意义。

But, that conversion process is also O(n). So, if you only need to do this once, use the filter. If you need to query the same list many times, then converting it to a map may make sense.

您也可以尝试使用并行流在某些情况下，它们可能更具性能，但这在很大程度上取决于具体情况。

You might also try using parallel streams. In some cases they may be more performant, but that depends a lot on the exact circumstances.

这篇关于流过滤器的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！