performance - 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 是一个 Set，在这种情况下它是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，您可能希望交换哪个是集合以及哪个正在迭代。