为何Groovy的minus()方法处理数值列表时性能低下？

场景与初始化代码 #

现有两个大小为n、元素均为唯一整数的列表left和right，目标是计算它们的交集与差集，理论上可实现*O(n)或O(nlog(n))*的时间复杂度。列表初始化代码如下：

Integer n = 10_000
Integer overlap = (Integer) (0.1 * n)
List left = (1..n).toList().shuffled()
List right = (n-overlap+1..2*n-overlap).toList().shuffled()

两种交集与差集实现方式 #

高性能实现 #

以下实现方式性能表现良好：

Set setLeft = left

Set onlyInRight = right.findAll { !(it in setLeft) }
Set inBoth = right.findAll { !(it in onlyInRight) }
Set onlyInLeft = left.findAll { !(it in inBoth) }

高可读性但低性能实现 #

另一种写法可读性更强，但实际测试性能极差，时间复杂度接近O(n²)：

List inBoth = left.intersect(right)
List onlyInLeft = left - inBoth
List onlyInRight = right - inBoth

问题根源 #

查看Groovy中minus()方法的源码后发现，该方法处理Number类型元素时采用了嵌套循环实现，导致时间复杂度达到O(n²)，而预期的高效实现应该是基于集合的遍历删除逻辑。由此推测，将数值包装为实现Comparable接口的自定义值类，可能会触发更高效的实现逻辑，从而提升性能。

待解答的疑问 #

• Groovy针对Number类型的minus()方法采用嵌套循环实现的设计原因是什么？
• 采用自定义值类包装数值来优化性能的思路中，有哪些容易遗漏的细节？

内容的提问来源于stack exchange，提问作者IWilms