scala – 如何将函数insert-sort代码更改为tail递归

发布时间：2020-12-16 09:58:13 所属栏目：安全来源：网络整理

导读：最近我通过函数式编程风格实现了insert_sort算法,它变得更加简洁和声明.问题是如何将其更改为尾递归,如果列表的大小增加到10000,代码将抛出异常. def InsertSort(xs: List[Int]): List[Int] = xs match { case Nil = Nil case x::rest = def insert (x: Int,

最近我通过函数式编程风格实现了insert_sort算法,它变得更加简洁和声明.问题是如何将其更改为尾递归,如果列表的大小增加到10000,代码将抛出异常.

def InsertSort(xs: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x::rest => 
       def insert (x: Int,sorted_xs:List[Int]) :List[Int] = sorted_xs match{
           case Nil => List(x)
           case y::ys => if  (x <= y) x::y::ys else y::insert(x,ys)
       }
       insert(x,InsertSort(rest))
 }

解决方法

刚刚介绍累加器：

@tailrec def InsertSort(xs: List[Int],acc: List[Int] = Nil): List[Int] = 
  if (xs.nonEmpty) {
    val x :: rest = xs
    @tailrec 
    def insert(x: Int,sorted_xs: List[Int],acc: List[Int] = Nil): List[Int] =
      if (sorted_xs.nonEmpty) { 
        val y :: ys = sorted_xs
        if (x <= y) acc ::: x :: y :: ys else insert(x,ys,acc :+ y)
      } else acc ::: List(x)
    InsertSort(rest,insert(x,acc))
  } else acc

:::和：将O(n)作为默认的List实现,因此最好使用一些更合适的集合(如ListBuffer).您也可以使用foldLeft而不是显式递归来重写它.

更快的选项(使用foldLeft,不含:)：

@tailrec
 def insert(sorted_xs: List[Int],x: Int,acc: List[Int] = Nil): List[Int] =
   if (sorted_xs.nonEmpty) { 
     val y::ys = sorted_xs
     if (x <= y) acc.reverse ::: x :: y :: ys else insert(ys,x,y :: acc)
   } else (x :: acc).reverse

 scala> List(1,5,3,6,9,7).foldLeft(List[Int]())(insert(_,_))
 res22: List[Int] = List(1,7,9)

最后是span(比如@ roterl的答案,但是跨度更快一点 – 它只遍历集合,直到找到> x)：

def insert(sorted_xs: List[Int],x: Int) = if (sorted_xs.nonEmpty) { 
    val (smaller,larger) = sorted_xs.span(_ < x)
    smaller ::: x :: larger
 } else x :: Nil

 scala> List(1,7).foldLeft(List[Int]())(insert)
 res25: List[Int] = List(1,9)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!