有没有一种方法可以检查流中是否包含所有集合元素？

Question

有没有一种方法可以检查流中是否包含所有集合元素？

javacollectionsjava-8java-streamcontains

12

比如说，我需要类似这样的东西：

Collection<String> collection = /* ... */;
Stream<Object> stream = /* ... */;
boolean containsAll = stream.map(Object::toString).containsAll(collection);

当然，我可以使用collect()方法将流的所有元素累加到另一个Collection中，并调用Collection.containsAll()，但是如果流太大而且处理其所有元素效率低下怎么办？

- Nolequen

1

我个人认为，最好使用以下代码：

Set<String> temp = source.stream().map(Object::toString).collect(toSet()); boolean containsAll = temp.containsAll(collection);

- Ousmane D.

@OusmaneD。如果OP假设的数据流太大怎么办？想象一下当“stream”是惰性生成的，而且并非所有元素都被保留在内存中的情况。例如，使用“Files::lines”，即使不能将巨大的文件全部装入内存，您也可以处理它们。在这种情况下，收集到集合中会导致“OutOfMemoryError”。 - ETO

3个回答

4

无论 Stream 有多大，如果它不包含 Collection 的所有元素，则必须处理其所有元素。

如果 Stream 的一个小前缀包含了 Collection 的所有元素，并且 Collection 远比 Stream 小，您可以节省处理时间。

boolean containsAll = 
    stream.map(Object::toString)
          .filter(s -> collection.contains(s)) // it would be wise to convert collection to a Set
          .limit(collection.size())
          .count() == collection.size();

请注意，如果Stream中可能含有Collection的相同元素的多个副本，您可能需要在filter()之后添加一个.distinct()操作。

- Eran

我真的不明白在这种情况下不使用collect而选择其他操作（如count）的好处。由于流处理对完整元素的处理无论如何都会发生（最坏情况），是否有可能进行优化以避免使用那么多内存？ - Naman

@Naman 如果流中有1000000个元素，但集合的所有元素都出现在前50个元素中，它会处理所有元素吗？当然，如果集合的所有元素都没有出现在流中（或者最后一个元素出现在流的末尾附近），这种解决方案就无法帮助。 - Eran

如果流中有一些空条目怎么办？如果流和集合已排序，处理_containsAll_会更快吗？ - Paul

@Eran 通过_containsAll_，我指的是你的方法，即查找集合是否包含流的所有元素。感谢澄清。 - Paul

@Paul，我误解了你的问题。如果流和集合已排序，则即使流不包含集合的所有元素，也应该可以制定有效的解决方案（而不必处理整个流），因为我们可以识别出在其中没有更多属于集合的元素的流中的点。这可以通过使用takeWhile来完成。 - Eran

3

从Collection<String>创建一个Set，以使搜索操作更快，时间复杂度为O(1)。

Set<String> set = new HashSet<>(collection);

然后使用allMatch来检查流中的每个项目是否都包含在集合中。

boolean containsAll = stream.map(Object::toString)
                            .allMatch(s -> set.contains(s));

另一种方法：

通过不包含在集合中的过滤器，并使用limit（1）进行优化。

boolean isContains = stream.map(Object::toString)
                           .filter(s -> !set.contains(s))
                           .limit(1)
                           .count() > 0;

- Eklavya

这不是 OP 所要求的。如果集合包含 ("foo", "baa")，而您的流中包含 100 个 "foo"，则您的函数将返回错误的解决方案。 - kaiser

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ETO · Accepted Answer

这应该就能解决问题：

Set<String> set = new HashSet<>(collection);
boolean containsAll = set.isEmpty() || stream.map(Object::toString)
                                             .anyMatch(s -> set.remove(s) && set.isEmpty());

这个解决方案可能看起来有点困惑，但思路是直截了当的：

为了避免对collection进行多次迭代，我们把它包装成一个HashSet。（如果你的stream是并行的，则必须使用一个并发哈希集。更多细节请参见此贴）。
如果collection（或set）为空，则返回true而不处理stream。
对于stream的每个条目，我们尝试将其从set中移除。如果Set::remove的结果为true（因此它被set包含），并且在删除后set为空，则可以得出结论stream包含了最初的collection的所有元素。
终端操作Stream::anyMatch是一种短路操作。因此，一旦set为空，它就会停止迭代stream。在最坏的情况下，我们将处理整个流。

Set<String> set = new HashSet<>(collection);
boolean containsAll = set.isEmpty() || stream.map(Object::toString)
                                             .filter(set::remove)
                                             .anyMatch(__ -> set.isEmpty());

如果`collection`可以包含重复项，并且有要求检查`stream`是否包含所有这些重复项，那么我们需要维护一个并发计数器的映射表。

Map<String, AtomicLong> map = new ConcurrentHashMap<>();
collection.forEach(s -> map.computeIfAbsent(s, __ -> new AtomicLong()).incrementAndGet());
boolean containsAll = map.isEmpty() || stream.map(Object::toString)
                                             .filter(map::containsKey)
                                             .filter(s -> map.get(s).decrementAndGet() == 0)
                                             .filter(s -> map.remove(s) != null)
                                             .anyMatch(__ -> map.isEmpty());

代码稍作修改，但思路相同。