Kotlin中filter、subtract、groupBy拆分列表哪种效率最高？

嘿，这个问题问得特别到位！咱们来仔细唠唠这几种Scala列表拆分方案的性能，还有其他更优的实现方式～

假设我们操作的是Scala标准库的不可变List，且断言predicate是无副作用的纯函数：

1. filter + filterNot #

val trueList = list.filter(predicate) 
val falseList = list.filterNot(predicate)

• 逻辑非常直观：遍历列表两次，第一次挑出符合断言的元素，第二次挑出不符合的。
• 时间复杂度：O(2n)（n是列表长度）。
• 优缺点：代码简洁易懂，但两次遍历的开销会在列表极大或predicate计算成本很高时被放大。

2. filter + subtract #

val trueList = list.filter(predicate) 
val falseList = list.subtract(trueList)

• 先做一次filter（O(n)），然后subtract操作会遍历原列表，逐个检查元素是否不在trueList中。如果trueList是普通List，每次存在性检查的时间是O(k)（k是trueList的长度），最坏情况（比如所有元素都符合断言）下，整体时间复杂度会飙升到O(n²)。
• 还有个隐形坑：subtract会自动去重！如果原列表有重复元素，拆分结果会和预期不符。比如原列表是List(1,1,2)，断言是_ > 1，trueList是List(2)，subtract后得到List(1)，但实际应该是List(1,1)。
• 结论：你说这个方案性能最差，完全正确！它不仅性能拉胯，还可能导致逻辑错误，非常不推荐使用。

3. groupBy #

val groupBy = list.groupBy(predicate) 
val trueList = groupBy(true) 
val falseList = groupBy(false)

• 只遍历列表一次，把元素按断言结果（true/false）分组，时间复杂度O(n)。
• 优缺点：一次遍历完成拆分，性能最优；代码也很简洁，且能完整保留原列表的重复元素。唯一的小缺点是需要从返回的Map中手动取出两个分组，但操作成本可以忽略。

毫无疑问是groupBy，它的时间复杂度是O(n)，只需要一次遍历。而filter+filterNot需要两次遍历（O(2n)），filter+subtract最坏情况是O(n²)，完全不在一个量级。

不过还要提一句：Scala标准库其实提供了更地道的工具——partition方法，它专门用来做这种“按断言拆分列表”的操作：

val (trueList, falseList) = list.partition(predicate)

partition的底层实现和手动一次遍历拆分的逻辑一致，时间复杂度也是O(n)，代码比groupBy更简洁，可读性拉满，是实际开发中的首选方案！

除了上面提到的，你还可以手动用foldLeft实现一次遍历拆分：

// 初始值是两个空列表，遍历每个元素时按断言分配到对应列表
val (trueListReversed, falseListReversed) = list.foldLeft((List.empty[T], List.empty[T])) {
  case ((trues, falses), elem) =>
    if (predicate(elem)) (elem :: trues, falses) else (trues, elem :: falses)
}
// 如果需要保持原列表的顺序，反转一下结果
val (trueList, falseList) = (trueListReversed.reverse, falseListReversed.reverse)

这个方法的性能和partition、groupBy一样都是O(n)，如果不需要保持元素顺序，甚至可以省掉反转步骤，性能还能再提一点。

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