java - 用于过滤 Java Stream 的最有效集合？

Question

我将几个 Thing 存储在一个集合中。单个 Thing 是唯一的，但它们的类型不是。它们的存储顺序也无关紧要。

我想使用 Java 8 的 Stream API 通过以下代码在其中搜索特定类型:

Collection<Thing> things = ...;
// ... populate things ...
Stream<Thing> filtered = things.stream.filter(thing -> thing.type.equals(searchType));

是否有特定的 Collection 可以使 filter() 更高效？

我倾向于认为不是，因为过滤器必须遍历整个集合。

另一方面，如果集合是由 Thing.type 索引的某种树，那么 filter() 可能会利用那个事实。有什么办法可以实现吗？

Answer 1

像过滤器这样的流操作并不是专门用于在特殊情况下利用的。例如，IntStream.range(0, 1_000_000_000).filter(x -> x > 999_999_000) 实际上会迭代所有输入数字，它不能只“跳过”第一个 999_999_000。所以你的问题被简化为找到迭代效率最高的集合。

迭代通常在Spliterator.forEachRemaining方法(非短路流)和Spliterator.tryAdvance方法(短路流)中执行，因此您可以查看相应的 spliterator 实现并检查它的效率。在我看来，最有效的是数组(裸数组或使用 Arrays.asList 包装到列表中):它的开销最小。 ArrayList 也相当快，但对于短路操作，它会在每次迭代时检查 modCount(以检测并发修改)，这会增加非常轻微的开销。其他类型，如 HashSet 或 LinkedList 相对较慢，但在大多数应用程序中，这种差异实际上微不足道。

请注意，应谨慎使用并行流。例如，LinkedList 的拆分非常差，您可能会遇到比顺序情况更差的性能。