Skip to main content
 首页 » 操作系统 » linux系统

Clojure怎样偷个懒

怎样偷个懒递归定义由两个部分组成。

● 基础(basis),明确地列举出序列的部分成员。

● 归纳(induction),提供一些规则,规定了如何通过组合序列的成员,来产生更多的成员。

要把递归定义转换为可以工作的代码。

● 简单的递归,让函数以某种方式来调用其自身,从而进行归纳。

● 尾递归,仅当函数执行到末尾时,才去调用其自身。

尾递归使得一种非常重要的优化手段变得可行了。

● 惰性序列,实实在在地消除了递归,并且只有当需要时,才会去计算值。

选择正确的方法非常重要。

递归定义的拙劣实现,会导致代码的性能表现极其糟糕,要么耗尽所有可用的栈空间然后挂掉;要么耗尽所有可用的堆内存然后挂掉;亦或是两者兼具。

在Clojure中,选择惰性化往往是正确的做法。

简单的递归来实现斐波那契数

Clojure怎样偷个懒  Clojure 第1张

对于比较小的n值,stack-consuming-fibo工作正常。

Clojure怎样偷个懒  Clojure 第2张

计算诸如F1000000这样的大斐波那契数时,就会出现问题。

Clojure怎样偷个懒  Clojure 第3张

对于n>1的情况,每次调用stack-consuming-fibo都会招致对其自身的两次调用。

在Java虚拟机的层面,这些调用会被翻译为方法调用,而每次方法调用都会分配一个被称为栈帧(stack frame)的数据结构。

stack-consuming-fibo会创建深度与n成正比的栈帧,这样就迅速耗尽了Java虚拟机的栈空间,并引发了如前所示的 StackOverflowError 异常。而且它创建的栈帧总数是n的指数,因此即使栈没有溢出,其性能也极为糟糕。

Clojure函数调用被标明是消耗栈空间(stack-consuming)的,因为它们使用了栈空间来分配栈帧。

在Clojure中,应该尽量避免采用stack-consuming-fibo这种消耗栈空间型的递归。

尾递归函数式程序可以借助尾递归技术解决栈空间的使用问题。

尾递归函数依然被定义为是递归的,但递归点必须位于尾部,即函数中返回某个值的那个表达式。

语言随后即可进行尾部调用优化(tail-call optimization,TCO),把尾递归转换为迭代,于是就不再消耗栈空间了。

为了让fibo成为尾递归,你需要创建一个函数,它的参数携带了足够多的信息,能够让归纳可以继续前进,而不再需要去做一些额外的“善后”工作,这些额外的工作导致递归点远离了尾部位置。

为了让fibo尾递归,对于fibo而言,它需要知道两个斐波那契数,再加上一个序数 n,当 n 递减为零时,新的斐波那契数也就计算出来了。

Clojure怎样偷个懒  Clojure 第4张

letfn宏

Clojure怎样偷个懒  Clojure 第5张

letfn与let很像,只不过它是专门用来指定局部函数的。

每个声明于letfn中的函数,都可以调用自身或是其他属于同一个letfn块的函数。

第3行声明的fib有三个参数:当前斐波那契数current、下一个斐波那契数next和代表剩余步数的数字n。当不再有剩余步数时,会在第5行返回current,反之,则在第6行继续进行计算,并且把剩余步数减1。最后,在第7行开启了递归,这里使用了基础值0和1,再加上正要求解的斐波那契数的序号n。

Clojure怎样偷个懒  Clojure 第6张

即便已经是尾递归了,在面对很大的n值时,它仍然执行失败了

Clojure怎样偷个懒  Clojure 第7张

这里的问题来自于 Java 虚拟机。虽然诸如 Haskell 这样的函数式语言能够进行TCO,但Java虚拟机却不是为函数式语言设计的。没有哪种直接运行在Java虚拟机上的语言,能够进行自动的TCO。

TCO的缺乏是很不幸的,但对于函数式程序而言,这也算不上是什么致命的问题。Clojure 提供了几个务实的解决方法:使用 recur 进行显式自递归、惰性序列和使用trampoline进行显式互递归。

自递归与recur递归在 Java 虚拟机上有一种可以被优化的特殊情况,就是自递归。它直接调用其自身,而不必通过一系列中间函数。

在Clojure中,可以借助recure把那种在尾部调用其自身的函数,转换为显式自递归。

Clojure怎样偷个懒  Clojure 第8张

recur-fibo和tail-fibo之间的关键区别是第7行,在那儿用recur替代了对fib的调用。现在计算斐波那契数时,recur-fibo就不再消耗栈空间了。

Clojure怎样偷个懒  Clojure 第9张

惰性序列惰性序列是用lazy-seq宏创建出来的。

Clojure怎样偷个懒  Clojure 第10张

仅当需要时,lazy-seq 才会去调用它的 body,当 seq 被直接或是间接的调用时,lazy-seq会为后续的调用缓存结果。

Clojure怎样偷个懒  Clojure 第11张

在第3行,无参版本的那个函数主体,把基础值[0 1]和随后将要计算得到的剩余部分连接起来并返回,而这些剩余部分的值,是通过调用那个有两个参数的版本来计算得到的。在第 5 行,两个参数版本的函数体计算出数列的下一个值 n,然后在第7行,把n和剩余部分的值进行连接。最关键的是第 6 行,这使得它的主体惰性化了。如果没有这一句,第 7 行对lazy-seq-fibo的递归调用会立即生效,这样lazy-seq-fibo将会就会像它的前任们一样,一直递归下去直至栈空间被撑爆。这也说明了一个通用的模式:为了用惰性化来替代递归,可以把函数体中的递归部分用lazy-seq给包裹起来。用小一点的值来试试这个lazy-seq-fibo。

Clojure怎样偷个懒  Clojure 第12张

lazy-seq-fibo对很大的值也仍然有效。下面用到了(rem ... 1000),是为了避免撑爆屏幕,只打印出第一百万个斐波那契数的最后三位数字。

Clojure怎样偷个懒  Clojure 第13张

lazy-seq-fibo采用的方法遵循了规则3,即使用惰性化来实现无限序列。但通常情况下,并不需要自己显式地调用lazy-seq。根据规则5,应该重用已有的序列库函数,来返回惰性序列。

Clojure怎样偷个懒  Clojure 第14张

这个iterate起始于斐波那契数列的第一对数字:[0 1]。通过这种结对的运作方式,就让它携带了刚好足够的信息(两个值),用来计算斐波那契数列的下一个值。斐波那契数正好是每对的第一个值。可以通过对整个序列应用map first,来把它们给提取出来。

Clojure怎样偷个懒  Clojure 第15张

由于建立在返回惰性序列的map和iterate之上,fibo返回的仍然是一个惰性序列。

需要学习递归的、惰性化的思维方式,还有Java虚拟机内部在递归上的限制。

在编写Clojure程序时,对于任何大小会变化的序列和任何大型的序列,都应该优先选择惰性序列而不是loop/recur。

聊聊变现惰性序列只有当它们被变现时才会显著的消耗资源,换句话说,就是作为序列的一部分在内存中被真正地实例化了。

Clojure尽可能的让序列惰性化,并且极力避免变现序列,直至绝对必要的时候。

Clojure怎样偷个懒  Clojure 第16张

lots-o-fibs 的创建几乎立刻就完成了,那是因为它几乎没有做任何事情。如果调用了一个函数,而这个函数确实需要用到lots-o-fibs中的一些值,那么Clojure就会把这些值给计算出来。即使如此,它也仅会计算那些必须的。

Clojure怎样偷个懒  Clojure 第17张

大多数序列函数返回的都是懒惰序列。如果不确定某个函数返回的是不是惰性序列,可以查阅函数的文档。

Clojure怎样偷个懒  Clojure 第18张

然而,REPL却不是惰性的。默认情况下,REPL的打印器会把整个容器都给打印出来。

Clojure怎样偷个懒  Clojure 第19张

输入了前面的这个表达式,REPL将试图变现整个容器,并打印这十亿个斐波那契数。

为了方便使用惰性序列,可以通过设置*print-length*的值,来配置打印器一次最多打印多少项。

Clojure怎样偷个懒  Clojure 第20张

对于超过10个元素的容器,现在打印器就只会打印前10项,并在后面追加一个省略号。

Clojure怎样偷个懒  Clojure 第21张

Clojure怎样偷个懒  Clojure 第22张

丢弃头元素

Clojure怎样偷个懒  Clojure 第23张

这个定义使用了lazy-cat,它和concat非常相像,除了它的参数仅当需要时才会被求值。这是一个非常漂亮的定义,递归地为(斐波那契数列的每个元素)和(斐波那契数列剩余的每个元素)求和以及映射。对于较小的斐波那契数,head-fibo运作良好。

Clojure怎样偷个懒  Clojure 第24张

Clojure怎样偷个懒  Clojure 第25张

顶级变量head-fibo持有着容器的头元素。这样就阻止了垃圾收集器去回收序列中的元素,即便其实早就已经越过了那些元素。

因此,曾经用到的那部分斐波那契数序列都会被缓存起来,这些被head-fibo引用着的值的存活时间,很可能就和整个程序的生命一样长。除非就是希望在遍历序列时对它进行缓存,否则,一定要格外小心,千万不要持有序列头元素的引用。

应该把惰性序列暴露为返回该序列的一个函数,而不是直接用变量来容纳这个序列。倘若这个函数的某个调用者想要显式地进行缓存,那么这个调用者可以随时创建它自己的变量。在使用惰性序列时,丢弃头元素往往是一个好主意。

评论列表暂无评论
发表评论
微信