Kotlin 集合操作有效性

Question

我想为一个集合创建一个扩展函数来检查一个集合是否包含定义集合的任何项目。 我想到了两种实现方式：

infix fun <T> Iterable<T>.containsAny(values: Iterable<T>): Boolean = any(values::contains)

或

infix fun <T> Iterable<T>.containsAny(values: Iterable<T>): Boolean = intersect(values).isNotEmpty()

问题是哪种方式更有效，为什么？还有什么更好的解决办法吗？

Answer 1

any 的第一种方式是 O(n*m) 除非参数 Iterable 是一个集合，在这种情况下它是 O( n).

intersect 的第二种方式是 O(n).

所以第二种方法要快得多，除非参数已经是一个 Set 或者两个输入都太小以至于值得重复迭代以避免将接收器 Iterable 复制到 MutableSet。

可以改进 O(n) 方法以允许 any 的提前退出行为：

infix fun <T> Iterable<T>.containsAny(values: Iterable<T>): Boolean =
    any(values.toSet()::contains)

并进一步避免不必要的集合复制：

infix fun <T> Iterable<T>.containsAny(values: Iterable<T>): Boolean =
    any((values as? Set<T> ?: values.toSet())::contains)

如果接收者 Iterable 通常比参数 Iterable 大，你可能想交换哪个是集合，哪个是被迭代。