java - 流过滤器的时间复杂度

Question

我有这样的代码:

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)，有没有一种优雅的方式用流来做到这一点？

Answer 1

它是O(n)。流过滤在内部使用迭代。

您可以按如下方式将其转换为 map :

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)。因此，如果您只需要执行一次，请使用过滤器。如果您需要多次查询同一个列表，那么将其转换为 map 可能是有意义的。

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