为什么在函数式编程中计算速度更快/效率更高？

下面是在其中一个答案提出的申索：https://softwareengineering.stackexchange.com/a/136146/18748 为什么在函数式编程中计算速度更快/效率更高？

试试你的手在功能性语言或两个。尝试使用递归执行因子在二郎山，看你的下巴砸在地板上时20000！ 5秒内返回（站点没有堆栈溢出）

为什么它比在Java/C/C++/Python（any）中使用递归/迭代更高效？什么是使这种情况发生的基础数学/理论概念？不幸的是，我从未接触过我的本科生的函数式编程（从'C'开始），所以我可能只是不知道'为什么'。

来源

2013-03-11 PhD

主持人：如果认为不合适，请将其移至合适的论坛/网站。 – PhD 2013-03-11 22:31:56

http://en.wikipedia.org/wiki/Tail-call_optimization – 2013-03-11 22:32:17

这不是更快，这是hogwash。然而，_write_通常更快。 – 2013-03-11 22:33:32

递归的解决办法可能是在Java或C++慢，笨重，但我们没有做的事情在Java和C++这样，所以。 :)

至于为什么，函数式语言总是会使用非常繁重的递归（因为默认情况下，它们必须跳过箍环，或者根本不允许修改变量，这些变量本身会使大多数形式的迭代无效或完全不可能）。所以他们必须有效地优化它，才能具有竞争力。

几乎所有的人实施所谓的“尾调用消除”的优化，它采用了下一次调用当前调用的堆栈空间并打开“呼叫”变成了“跳跃”。这个小小的变化基本上将递归转化为迭代，但不提醒FPer。当涉及程序语言的迭代和功能性的递归时，两者将证明性能相当。（如果其中任何一个仍然更快，但它会迭代。）

其余的是库和数字类型等。体面的数学代码==>体面的数学表现。没有什么保持程序或面向对象的语言，从同样的优化，除此之外大多数人不想那么多。另一方面，功能程序员喜欢脐眼，他们很容易计算斐波纳契数列和20000！以及我们大多数人永远不会使用的其他数字。

来源

2013-03-11 22:43:22 cHao

本质上说，函数式编程语言使递归便宜。

特别是通过tail call optimization.

来源

2013-03-11 22:41:34

Tail-call optimization

Lazy evaluation：“当使用延迟评价，表达不只要它被绑定到变量评价，但是当评价者被强制以产生表达式的值”

这两个概念在本question about various ways of implementing factorial in Clojure示出。您还可以在Stuart Halloway和Aaron Bedra的书Programming Clojure中找到关于懒惰序列和TCO的详细讨论。

以下功能，从编程的Clojure通过，创建与斐波那契数序列的第一1M成员懒惰序列，实现了一个十万分之一构件：

user=> (time (nth (take 1000000 (map first (iterate (fn [[a b]] [b (+ a b)]) [0N 1N]))) 100000)) 
"Elapsed time: 252.045 msecs" 
25974069347221724166155034.... 
(20900 total digits)

（512MB堆，英特尔酷睿i7 ，2.5GHz的）

来源

2013-03-11 23:01:52

请注意，尽管Clojure是一种严格（不懒惰）的语言，并且不会实现完整的尾部调用优化，因为它在JVM上运行... – 2013-03-11 23:16:00

在JVM上，您必须伪装它'，直到您使用[ lazy-seq]（http://clojuredocs.org/clojure_core/clojure.core/lazy-seq）和[recur]（http://clojuredocs.org/clojure_core/clojure.core/recur） – 2013-03-11 23:27:20

@DonStewart For factorial，你不需要全面的TCO，只需要尾部递归消除。我无法想象Clojure不这样做。 – Ingo 2013-03-12 00:52:58

这不快（比什么？），并且它与尾部呼叫优化无关（仅在这里引入流行词是不够的，还应该解释为什么尾部呼叫优化应该比循环更快），但事实根本不是这样！

请注意我不是一个功能性编程仇恨，相反！但是传播神话并不适用于函数式编程。

顺便说一句，这里有任何一个实际上尝试需要多长时间来计算（和打印，这应该消耗至少50％的CPU周期所需）20000！？

我所做的：

main _ = println (product [2n..20000n])

这是一个JVM语言编译成Java，它使用Java大整数（已知慢）。它也遭受JVM启动成本的影响。这并不是最快的方法（例如显式递归可以节省列表构造）。

结果是：

181920632023034513482764175686645876607160990147875264 
... 
... many many lines with digits 
...   
000000000000000000000000000000000000000000000000000000000000000 

real 0m3.330s 
user 0m4.472s 
sys  0m0.212s

（在英特尔®酷睿™i3 CPU中号350 @ 2.27GHz×4）

我们可以安全地假设，同样用C符合GMP不会甚至可以使用这个时间的50％。

因此，官能更快是神话，以及官能较慢。这甚至不是一个神话，只要人们没有说比较快/慢就说不出来。

来源

2013-03-12 00:48:40 Ingo

原文中提到的语言是“Java，C/C++，JavaScript/jQuery和... Objective-C”。我的观点是，TCO和/或懒惰评估是Clojure的特性，可以支持在其他环境中可能证明具有挑战性的非常大的计算。我已经提供了一个例子，就像OP的链接文章中的其他例子一样。 – 2013-03-12 03:18:54

为什么在函数式编程中计算速度更快/效率更高？

回答

相关问题