Scala listOfLists递归方法优化求助：如何使用_*语法提升实现效率

原有实现的核心问题 #

• 重复执行strings.toList：每次递归都将可变参数转为List，产生不必要的O(n)开销
• 切片逻辑效率低：takeRight需要遍历列表取后N个元素，时间复杂度为O(n)
• 列表追加开销大：List是不可变单向链表，:+ 往末尾追加元素需要遍历整个列表，时间复杂度O(n)
• 冗余的计数变量：不需要用accumulator计数，直接跟踪当前剩余的子列表即可，逻辑更简洁

疑问解答 #

1. _*语法的使用场景 #

_*是Scala中用于将Seq类型展开为可变参数（varargs）的语法，仅在你需要给接收可变参数的方法传入Seq类型参数时使用。你当前的场景不需要反复处理可变参数，仅需在方法入口一次性转成List即可，如果你要写非尾递归的实现，可以参考如下用法：

// 非尾递归实现，仅作语法演示，参数较多时会栈溢出
def listOfLists(strings: String*): List[List[String]] = {
  if (strings.isEmpty) Nil
  else strings.toList :: listOfLists(strings.tail:_*)
}

这里调用自身时，就用strings.tail:_*将Seq类型的strings.tail展开为可变参数，符合题目的语法提示。

2. 切片逻辑的优化方案 #

你需要的是每次去掉列表的首个元素，List内置的tail方法可以直接获取去掉首元素的子列表，时间复杂度为O(1)，完全不需要计算长度再调用takeRight。

优化后的尾递归实现 #

import scala.annotation.tailrec

def listOfLists(strings: String*): List[List[String]] = {
  // 一次性将可变参数转为List，避免重复转换开销
  val inputList = strings.toList

  @tailrec
  def rec(current: List[String], acc: List[List[String]]): List[List[String]] = {
    current match {
      // 当前列表非空，将当前列表加入累加器，递归处理剩余子列表
      case _ :: _ => rec(current.tail, current :: acc)
      // 列表为空时反转累加器返回（因为前面是往前拼的，顺序是反的）
      case Nil => acc.reverse
    }
  }

  rec(inputList, Nil)
}

这个实现的时间复杂度为O(n)，仅做了一次列表转换、一次遍历累加、一次最终反转，所有操作都是线性开销，比原有实现效率高很多。

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