在继续传递风格和记忆之间进行选择

Question

在以函数式语言编写memoization和continuation传递样式(CPS)函数的示例时,我最终使用了Fibonacci示例.然而,Fibonacci并没有真正受益于CPS,因为循环仍然必须经常以指数方式运行,而memoization它的第一次只有O(n)而后一次只有O(1).

结合CPS和记忆化既有的斐波那契数略有好处,但有没有解决,其中CPS是防止你用尽堆栈的最佳方式的例子,并提高了性能并在记忆化是不是一个解决方案？

或者:是否有何时选择其中一个或两者的指南？

Answer 1

关于CPS

虽然CPS在编译器中作为中间语言非常有用,但在源语言级别上,它主要是一种设备:(1)编码复杂的控制流(不是真正与性能相关的)和(2)转换非尾部调用消耗栈空间进入延续分配尾部调用消耗堆空间.例如,当你写(代码未经测试)

let rec fib = function
  | 0 | 1 -> 1
  | n -> fib (n-1) + fib (n-2)

let rec fib_cps n k = match n with
  | 0 | 1 -> k 1
  | n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b)))

之前fib (n-2)分配了新堆栈帧的非尾调用转换为尾调用fib (n-2) (fun b -> k (a+b)),该调用分配闭包fun b -> k (a+b)(在堆上)以将其作为参数传递.

这并不是渐近地减少程序的内存使用量(某些进一步的特定于域的优化可能会,但这是另一个故事).你只是为堆空间交换堆栈空间,这对于堆栈空间受操作系统严重限制的系统很有意义(不是ML的某些实现的情况,例如SML/NJ,它们在堆上跟踪它们的调用堆栈而不是使用系统堆栈),由于额外的GC成本和潜在的位置降低,可能会降低性能.

CPS转换不太可能提高性能(虽然您的实现和运行时系统的细节可能会如此),并且是一种通常适用的转换,允许避免使用深度调用堆栈的递归函数的"堆栈溢出".

关于记忆

Memoization对于引入递归函数的子函数的共享很有用.递归函数通常n通过将其分解为几个严格简单的"子问题"(递归子句)来解决"问题"("计算斐波那契"等),其中一些基本情况可以立即解决问题.

对于任何递归函数(或问题的递归公式),您可以观察子问题空间的结构.这简单的情况下,Fib(k)将Fib(n)需要返回其结果呢？这些实例反过来需要哪些更简单的实例？

在一般情况下,子问题的这个空间是一个图(通常用于终止目的的非循环):有一些节点有几个父节点,这是几个不同的问题,它们是子问题.例如,Fib(n-2)是既子问题Fib(n)和Fib(n-2).此图中的节点共享量取决于特定的问题/递归函数.在Fibonacci的情况下,所有节点都在两个父节点之间共享,因此有很多共享.

没有记忆的直接递归调用将无法观察到此共享.递归函数的调用结构是树,而不是图,并且共享的子问题Fib(n-2)将被多次完全访问(与图中的起始节点到子问题节点的路径一样多).Memoization通过让一些子调用"我们已经计算了这个节点并且这里是结果"直接返回来引入共享.对于具有大量共享的问题,这可以导致(无用的)计算的显着减少:当引入memoization时,Fibonacci从指数变为线性复杂度 - 请注意,还有其他方法来编写函数,而不使用memoization但是不同的子结构,具有线性复杂性.

let rec fib_pair = function
  | 0 -> (1,1)
  | n -> let (u,v) = fib_pair (n-1) in (v,u+v)

使用某种形式的共享(通常通过存储结果的大表)以避免无用的子计算重复的技术在算法社区中是众所周知的,它被称为动态编程.当您意识到问题适合这种处理时(您注意到子问题之间的共享),这可以提供很大的性能优势.

比较有意义吗？

这两者似乎大多是相互独立的.

memoization不适用有很多问题,因为子问题图结构没有任何共享(它是一棵树).相反,CPS转换适用于所有递归函数,但本身并不会带来性能优势(除了由于您正在使用的特定实现和运行时系统而导致的潜在常数因素,尽管它们可能会生成代码慢而不是更快).

通过检查非尾部上下文来提高性能

有一些与CPS相关的优化技术可以提高递归函数的性能.它们包括在递归调用之后查看"剩余要完成"的计算(将以简单的CPS样式转换为函数)并为其找到替代的,更有效的表示,这不会导致系统的闭包分配.考虑例如:

let rec length = function
  | [] -> 0
  | _::t -> 1 + length t

let rec length_cps li k = match li with
  | [] -> k 0
  | _::t -> length_cps t (fun a -> k (a + 1))

您可以注意到非递归调用的上下文,即[_ + 1]具有一个简单的结构:它添加一个整数.fun a -> k (a+1)您可以只存储与此函数的多个应用程序相对应的要添加的整数,而不是将其表示为函数,k而是创建整数而不是函数.

let rec length_acc li k = match li with
  | [] -> k + 0
  | _::t -> length_acc t (k + 1)

此函数在常量而非线性空间中运行.通过将尾部上下文的表示从函数转换为整数,我们消除了使内存使用呈线性的分配步骤.

仔细检查执行添加的顺序将显示它们现在以不同的方向执行:我们首先添加对应于列表开头的1,而cps版本最后添加它们.这个顺序反转是有效的,因为它_ + 1是一个关联操作(如果你有几个嵌套的上下文foo + 1 + 1 + 1,它可以从内部((foo+1)+1)+1,或外部开始计算它们foo+(1+(1+1))).上面的优化可以用于围绕非尾部调用的所有这种"关联"上下文.

基于相同的想法(我不是这种优化的专家)肯定还有其他可用的优化,即查看所涉及的延续的结构,并以比堆上分配的函数更有效的形式表示它们.

这与"defunctionalization"的转换有关,它将连续的表示从函数更改为数据结构,而不改变内存消耗(当在原始程序中分配闭包时,defunctionalized程序将分配数据节点),但允许以一阶语言表示尾递归CPS版本(没有第一类函数),并且在数据结构和模式匹配比闭包分配和间接调用更有效的系统上更高效.

type length_cont =
  | Linit
  | Lcons of length_cont

let rec length_cps_defun li k = match li with
  | [] -> length_cont_eval 0 k
  | _::t -> length_cps_defun t (Lcons k)
and length_cont_eval acc = function
  | Linit -> acc
  | Lcons k -> length_cont_eval (acc+1) k

let length li = length_cps_defun li Linit

type fib_cont =
  | Finit
  | Fminus1 of int * fib_cont
  | Fminus2 of fib_cont * int

let rec fib_cps_defun n k = match n with
  | 0 | 1 -> fib_cont_eval 1 k
  | n -> fib_cps_defun (n-1) (Fminus1 (n, k))
and fib_cont_eval acc = function
  | Finit -> acc
  | Fminus1 (n, k) -> fib_cps_defun (n-2) (Fminus2 (k, acc))
  | Fminus2 (k, acc') -> fib_cont_eval (acc+acc') k

let fib n = fib_cps_defun n Finit