ska*_*ay- 4 recursion performance haskell lazy-evaluation lazy-initialization
懒惰评估被认为是一种延迟流程直到第一次需要的方式.这往往会避免重复评估,这就是为什么我认为这样做的速度要快得多.像Haskell(和JavaScript ..？)这样的函数语言内置了这个功能.
但是,我不明白为什么和为什么其他"正常"方法(即相同的功能但不使用惰性评估)更慢..这些其他方法如何以及为什么重复进行评估？有人可以通过提供简单的例子并解释每种方法的机制来详细说明这一点吗？
另外,根据Wikipedia关于懒惰评估的页面,这些被认为是这种方法的优点:
但是,我们可以控制所需的计算并避免重复相同的计算吗？(1)我们可以使用ie链接列表来创建无限数据结构(2)我们可以做(3)已经.. ??? 我们可以定义类/模板/对象并使用它们而不是原语(即JavaScript).
另外,在我看来(至少从我见过的案例中),懒惰的评估与递归和使用"头部"和"尾部"(以及其他)概念密切相关.当然,有些情况下递归是有用的,但懒惰的评价不仅仅是......？不仅仅是一种解决问题的递归方法..？Streamjs是一个JavaScript库,它使用递归和一些其他简单的操作(头部,尾部等)来执行惰性求值.
看来我无法理解它...
在此先感谢任何贡献.
我将在Python 2.7和Haskell中展示示例.
比如说,你想要从0到10,000,000的所有数字之间做一个非常低效的总和.你可以用Python中的for循环来做到这一点
total = 0
for i in range(10000000):
total += i
print total
在我的计算机上,执行大约需要1.3秒.如果相反,我改变range到xrange(的发电机形式range,懒惰地产生的数字序列),它需要1.2秒,仅稍快.不过,如果我检查使用(使用内存memory_profiler封装),该版本与range有关的RAM 155MB的用途,而xrange版本使用的内存只有1MB(两个数字不包括〜11MB Python使用).这是一个令人难以置信的巨大差异,我们也可以看到这个工具的来源:
Mem usage Increment Line Contents
===========================================
10.875 MiB 0.004 MiB total = 0
165.926 MiB 155.051 MiB for i in range(10000000):
165.926 MiB 0.000 MiB total += i
return total
这说明在我们开始之前我们使用了10.875MB,total = 0增加了0.004MB,然后for i in range(10000000):在生成整个数字列表时添加了155.051MB [0..9999999].如果我们比较xrange版本:
Mem usage Increment Line Contents
===========================================
11.000 MiB 0.004 MiB total = 0
11.109 MiB 0.109 MiB for i in xrange(10000000):
11.109 MiB 0.000 MiB total += i
return total
所以我们从11MB开始,for i in xrange(10000000):仅增加了0.109MB.这是一个巨大的仅增加一个字母的代码节省内存.虽然这个例子是相当有意思的,但它展示了在需要元素之前如何不计算整个列表可以使内存更高效.
Python有迭代器和生成器,当你需要生成数据序列时,它就像一种"懒惰"编程(虽然没有什么能阻止你将它们用于单个值),但是Haskell在语言的每个值中都有懒惰,甚至是用户定义的.这使您可以利用不适合内存的数据结构等内容,而无需针对该事实编写复杂的方法.典型的例子是斐波那契序列:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
它非常优雅地表达了这个着名的序列,以定义一个生成所有斐波纳契数的递归无限列表.它的CPU效率高,因为所有值都被缓存,所以每个元素只需要计算一次(与天真的递归实现相比)1,但是如果你计算的元素太多,你的计算机最终会耗尽RAM,因为你现在正在存储它庞大的数字列表.这是一个示例,其中延迟编程可以让您拥有CPU效率,但不会提高RAM效率.不过,有一种解决方法.如果你要写
fib :: Int -> Integer
fib n = let fibs = 1 : 1 : zipWith (+) fibs (tail fibs) in fibs !! n
然后这会在接近常量的内存中运行,并且非常快速地运行,但随后的调用fib必须重新计算,因此会丢失memoization fibs.
这里可以找到一个更复杂的例子,其中作者展示了如何在Haskell中使用延迟编程和递归来执行数组动态编程,这一壮举最初认为非常困难且需要变异,但Haskell很容易用"打结"式的递归.它可以实现CPU和RAM的效率,并且可以用比C/C++中预期更少的行来实现.
所有这些都说,有很多情况下懒惰编程很烦人.通常你可以建立大量的thunk而不是随意计算东西(我在看你foldl),并且必须引入一些严格来提高效率.IO当你把文件作为thunk读取到字符串时,它也会咬住很多人,关闭文件,然后尝试对该字符串进行操作.只有在文件关闭后才会对thunk进行评估,从而导致出现IO错误并导致程序崩溃.与任何事情一样,懒惰编程并非没有缺陷,陷阱和陷阱.学习如何使用它并了解其局限性需要时间.
1)通过"天真的递归实现",我的意思是将斐波纳契序列实现为
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
通过这种实现,您可以非常清楚地看到数学定义,它非常符合归纳证明的样式,您可以显示基本案例,然后是一般案例.但是,如果我打电话fib 5,这将"扩展"成类似的东西
fib 5 = fib 4 + fib 3
= fib 3 + fib 2 + fib 2 + fib 1
= fib 2 + fib 1 + fib 1 + fib 0 + fib 1 + fib 0 + fib 1
= fib 1 + fib 0 + fib 1 + fib 1 + fib 0 + fib 1 + fib 0 + fib 1
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 8
相反,当我们想要分享其中一些计算时,这种方式fib 3只计算一次,fib 2只计算一次,等等.
通过在Haskell中使用递归定义的列表,我们可以避免这种情况.在内部,此列表表示如下:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
= 1 : 1 : zipWith (+) (f1:f2:fs) (f2:fs)
^--------------------^ ^ ^
^-------------------|-------|
= 1 : 1 : 2 : zipWith (+) (f2:f3:fs) (f3:fs)
^--------------------^ ^ ^
^-------------------|-------|
= 1 : 1 : 2 : 3 : zipWith (+) (f3:f4:fs) (f4:fs)
^--------------------^ ^ ^
^-------------------|-------|
所以希望你可以看到这里形成的模式,因为列表是构建的,它会将指针保留回生成的最后两个元素,以便计算下一个元素.这意味着对于计算的第n个元素,n-2执行了添加.即使是天真的fib 5,你也可以看到执行的添加量超过了这个数量,并且增加的数量将继续呈指数级增长.通过懒惰和递归使这个定义成为可能,让我们将O(2^n)算法变成O(n)算法,但我们必须放弃RAM来做到这一点.如果在顶级定义了此值,则会在程序的生命周期中缓存值.它确实意味着如果你需要重复引用第1000个元素,你不必重新计算它,只需索引它.
另一方面,定义
fib :: Int -> Integer
fib n =
let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
in fibs !! n
使用fibs每次fib调用的本地副本.我们不会在调用之间获得缓存fib,但我们确实获得了本地缓存,从而使我们的复杂性降低O(n).另外,GHC足够聪明,知道在我们用它来计算下一个元素之后我们不必保持列表的开头,所以当我们遍历fibs寻找n第th个元素时,它只需要保持2-3个元素和一个指向下一个元素的thunk.这在计算它时节省了我们的RAM,并且因为它没有在全局级别定义,所以它不会在程序的生命周期中占用RAM.这是在我们想要花费RAM和CPU周期的时间之间的权衡,并且不同的方法对于不同的情况更好.这些技术通常适用于大部分Haskell编程,而不仅仅适用于此序列!
一般而言,懒惰评估不会更快.当说懒惰评估更有效时,这是因为当你考虑Lambda Calculus(基本上就是你的Haskell程序,一旦编译器完成对它们进行去糖处理)作为一个术语和约简规则系统,然后应用这些规则具有共享评估策略的按名称的规则指定的顺序始终应用与按照按值调用评估指定的顺序遵循规则时相同或更少的减少规则.
这个理论结果一般不会使延迟评估更快的原因是,转换为具有内存访问瓶颈的线性顺序机器模型往往会使所有减少的执行成本更高!最初尝试在计算机上实现此模型导致程序比典型的热切评估语言实现更慢地执行数量级.它已经进行了大量的研究和工程,以有效地实现惰性评估,以使Haskell性能达到目前的水平.最快的Haskell程序利用了一种称为"严格性分析"的静态分析,它试图在编译时确定总是需要哪些表达式,以便可以急切而不是懒惰地评估它们.
在一些情况下,由于仅评估结果所需的术语,因此直接实现算法将在Haskell中执行得更快,但即使是热切的语言也总是有一些用于根据需要评估某些表达式的工具.条件和短路布尔表达式是无处不在的例子,在许多急切的语言中,人们也可以通过将表达式包装在匿名函数或其他类型的延迟形式中来延迟评估.因此,您通常可以使用这些机制(甚至更笨拙的重写)来避免评估在急切的语言中不需要的昂贵的东西.
Haskell懒惰评估的真正优势不是与性能相关的.Haskell使表达式更容易分离,以不同的方式重新组合它们,并且通常将代码推理为好像它是一个数学方程组而不是一组顺序评估的机器指令.通过不指定任何评估顺序,它迫使该语言的开发人员避免依赖于简单评估排序的副作用,例如突变或IO.这反过来导致了许多优雅的抽象,这些抽象通常是有用的,否则可能不会发展成可用性.
现在,Haskell的状态可以编写高级,优雅的算法,可以比几乎任何其他高级类型语言更好地重用现有的高阶函数和数据结构.一旦你熟悉了懒惰评估的成本和好处以及如何控制它的发生,你就可以确保优雅的代码也能很好地运行.但是,将优雅的代码变为高性能状态并不一定是自动的,可能需要比类似但热切评估的语言更多的思考.