算法 – 如何在Scala中实现尾递归快速排序

发布时间：2020-12-16 18:27:11 所属栏目：安全来源：网络整理

导读：我写了一个递归版本： def quickSort[T](xs: List[T])(p: (T,T) = Boolean): List[T] = xs match{ case Nil = Nil case _ = val x = xs.head val (left,right) = xs.tail.partition(p(_,x)) val left_sorted = quickSort(left)(p) val right_sorted = quickS

我写了一个递归版本：

def quickSort[T](xs: List[T])(p: (T,T) => Boolean): List[T] = xs match{
    case Nil => Nil
    case _ => 
         val x = xs.head
         val (left,right) = xs.tail.partition(p(_,x))
         val left_sorted = quickSort(left)(p)
         val right_sorted = quickSort(right)(p)
         left_sorted ::: (x :: right_sorted)
}

但我不知道如何将其改为尾部复原.任何人都可以给我一个建议吗？

解决方法

可以转换任何递归函数以使用堆而不是堆栈来跟踪上下文.该过程称为 trampolining.

以下是使用Scalaz实现的方法.

object TrampolineUsage extends App {

  import scalaz._,Scalaz._,Free._

  def quickSort[T: Order](xs: List[T]): Trampoline[List[T]] = {
    assert(Thread.currentThread().getStackTrace.count(_.getMethodName == "quickSort") == 1)
    xs match {
      case Nil =>
        return_ {
          Nil
        }
      case x :: tail =>
        val (left,right) = tail.partition(_ < x)
        suspend {
          for {
            ls <- quickSort(left)
            rs <- quickSort(right)
          } yield ls ::: (x :: rs)
        }
    }
  }

  val xs = List.fill(32)(util.Random.nextInt())
  val sorted = quickSort(xs).run
  println(sorted)

  val (steps,sorted1) = quickSort(xs).foldRun(0)((i,f) => (i + 1,f()))
  println("sort took %d steps".format(steps))
}

当然,你需要一个非常大的结构或一个非常小的堆栈来解决非尾递归分治算法的实际问题,因为你可以处理堆栈深度为N的2 ^ N个元素.

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

UPDATE

scalaz.Trampoline是一个(更多)更通用的结构,Free的特例.它被定义为Trampoline类型[A] = Free [Function0,A].实际上可以更通用地编写quickSort,因此它通过Free中使用的类型构造函数进行参数化.此示例显示了如何完成此操作,以及如何使用相同的代码使用堆栈,堆或同时进行绑定.

https://github.com/scalaz/scalaz/blob/scalaz-seven/example/src/main/scala/scalaz/example/TrampolineUsage.scala

（编辑：李大同）

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