Scala中排序栈弹出同值元素的优化实现及并行化可行性问询

Scala推崇不可变数据结构与函数式编程风格，相比可变Stack，可以利用标准库的span方法更简洁高效地实现需求——该方法能直接从已排序列表头部分割出所有与目标值相同的元素，同时保留剩余列表，全程无副作用：

val list = List(1,1,2,3,4,5,6,7,8,9)

// 从列表头部提取所有等于目标值x的元素，返回(匹配元素列表, 剩余列表)
def takeAllSameHead(list: List[Int], x: Int): (List[Int], List[Int]) = {
  val (matches, rest) = list.span(_ == x)
  (matches, rest)
}

val (taken, remaining) = takeAllSameHead(list, 1)
println(taken)       // 输出: List(1, 1)
println(remaining)   // 输出: List(2, 3, 4, 5, 6, 7, 8, 9)

如果需要一次性完成所有相同id元素的分组，可以用尾递归函数批量处理：

@annotation.tailrec
def processAll(list: List[Int], result: List[List[Int]] = Nil): List[List[Int]] = list match {
  case Nil => result.reverse
  case head :: _ =>
    val (group, rest) = list.span(_ == head)
    processAll(rest, group :: result)
}

println(processAll(list)) 
// 输出: List(List(1, 1), List(2), List(3), List(4), List(5), List(6), List(7), List(8), List(9))

你之前使用的可变Stack是线程不安全的，直接通过Futures操作同一个可变实例会引发竞态条件，导致数据错乱，因此不能直接基于它做并行化。但可以基于不可变数据结构设计并行方案：

• 每个列表的分组处理完全独立，可并行执行：因为不可变数据没有共享可变状态，每个线程处理自己的列表片段，不会互相干扰。
• 先并行预处理所有列表，得到每个列表的分组序列，再统一执行后续的join逻辑。

示例代码（并行预处理多列表）：

import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

// 模拟20个已排序的输入列表
val multipleLists = List(
  List(1,1,2,3),
  List(1,2,2,4),
  List(1,1,1,3)
  // 剩余列表省略...
)

// 并行处理每个列表，生成分组结果的Future
val groupedFutures: List[Future[List[List[Int]]]] = multipleLists.map(list => Future {
  processAll(list)
})

// 等待所有并行任务完成，汇总所有分组结果
val allGrouped = Future.sequence(groupedFutures)

// 后续基于分组结果执行按id的join逻辑
allGrouped.foreach(groups => {
  // 将分组映射为(id -> 元素列表)，再按id合并
  val idToGroups = groups.flatMap(_.map(group => group.head -> group)).groupBy(_._1)
  println(idToGroups)
})

也可以用Scala并行集合简化并行处理：

// 自动并行处理所有列表的分组
val groupedPar = multipleLists.par.map(processAll)

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