有没有一种功能算法比命令式算法更快？

Question

我正在寻找一种函数式算法（或其算法的论据），它比命令式算法更快。

我喜欢函数式代码，因为它具有表现力，并且通常比命令式代码更容易阅读。但我也知道，这种表现力可能会造成运行时开销。并不总是由于尾递归等技术 - 但它们经常较慢。

编程时，我不考虑函数式代码的运行时成本，因为现今的电脑非常快，开发时间比运行时间更昂贵。此外，对我而言，可读性比性能更重要。尽管如此，我的程序足够快，所以我很少需要用命令式方式解决问题。

有些算法在实践中应该采用命令式风格来实现（例如排序算法），否则在大多数情况下，他们将太慢或需要大量内存。 相比之下，由于诸如模式匹配之类的技术，使用函数式语言编写的整个程序（如解析器）可能比使用命令式语言编写的程序快得多，这是由于编译器优化代码的可能性。

但是，是否有任何算法在函数式风格下速度更快，或者是否有设置此类算法参数的可能性呢？

- kiritsuku

---

“functional”和“imperative”算法的意思是什么？选取任何一种“imperative（命令式）”算法，对其进行SSA转换，将基本块转化为一组相互递归的函数，然后你就能得到完全相同性能特征的纯粹“functional（函数式）”版本。反向转换则更加简单。 - SK-logic

函数式算法更易于推理，就像C语言比汇编语言更易于推理一样。因此，尽管编译后的C语言原则上永远不会比汇编语言更快，但C语言并非“只是一种时尚潮流”。 - Rex Kerr

你在建立一个虚假的二分法。算法并不分为“功能性”和“命令式”。 - Apocalisp

“开发时间”并不比“运行时间”更昂贵。这是因为对于任何体面的程序来说，代码执行所需的时间要比编写/维护时间多几个数量级。特别是如果你考虑到大量用户（其中任何一个人的时间可能比你的时间更有价值）。 - Lawrence Dol

@Raphael：我应该是“不是自动的”。但是，为了论证，假设您的情况等于900个人时（4054.5）：只需要1000个客户执行6,480次就可以在时间方面达到盈亏平衡。问题更多的是谁愿意支付以及支付多少。客户为了运行低效软件而支付多少新硬件费用？现在，为什么我今天对我的文字处理器的要求与10年前一样，但它现在需要更长的时间才能在我的PC上加载，而我的PC在各个方面都快了1000倍呢？ - Lawrence Dol

Answer 1

这是一个简单的推论。我不能保证术语的准确性，但它似乎具有道理。

• 一个要执行的功能程序需要被转换成一些机器指令。
• 所有（我听说过的）机器都是命令式的。
• 因此，对于每个功能程序，都有一个相当于它的命令式程序（粗略地说，是汇编语言）。

所以，在我们拥有“函数计算机”之前，你可能只能满足于“表达能力”了。

- Nikita Rybak

---

@Nikita：不要从账户中撤回Lisp机器！;-) - YasirA

@Yasir：实际上，即使是Lisp机器也遵循命令式模型。它有一个状态（电子位置等），随时间变化。因此，很可能可以用术语描述它在相同硬件上产生等效命令式程序的某个级别：不可否认，您可能必须大力破解机器以提供该程序以供执行。但是，如果您可以在功能计算机的柏拉图理念上执行计算，则只需从所有计算机状态的无穷集合中直接获取包含结果的计算机，那么您就可以开始工作了;-) - Steve Jessop

@Antoras：编译器实现的质量取决于投入的时间，与语言关系不大。在此方面，命令式语言处于领先地位...尽管像gcc这样的编译器最近改用了SSA中间表示，因为它更容易进行推理 :) - Matthieu M.

@Knut 或者我们可以将它们归为“红色”和“蓝色”，这实际上并没有什么区别。坦白地说，正如 Apocalisp 所指出的那样，整个二分法都是虚构的。 - Nikita Rybak

如果你想要创建一个“功能性”的CPU，这就有所不同。 - Knut Arne Vedaa

Answer 2

简短的回答是：

任何可以轻松并行处理的内容，因为没有副作用，都会在多核处理器上更快。

例如，使用不可变集合时，快速排序可以很好地扩展：http://en.wikipedia.org/wiki/Quicksort#Parallelization 其他一切相等的情况下，如果您有两个算法可以合理地描述为等效的，除了一个使用纯函数和不可变数据，而第二个依赖于原位变异，则第一个算法将很容易扩展到多个核心。

甚至可能您的编程语言可以为您执行此优化，例如scalaCL插件，它将编译代码以在GPU上运行。（我现在在想SIMD指令是否使其成为“功能”处理器）

因此，在具有并行硬件的情况下，第一个算法将表现更好，并且您拥有的核心数越多，差异就越大。

- Kevin Wright

---

虽然这是真的，但这并没有回答问题。如果正确实现，可以使用并行快速排序。原地快速排序甚至不可用（交换修改状态），但可以并行运行。 - phkahler

@phkahler 我认为命令式编程的本质就是顺序执行命令。这难道不意味着任何并行操作都不能是命令式的吗？ - AnnanFay

@Annan：并行与命令式/函数式讨论不同。每个线程仍然是命令式的。 - phkahler

Answer 3

对于纯函数式编程，有一些纯函数式数据结构是可以受益的。

Chris Okasaki写了一本关于纯函数式数据结构的好书，从函数式语言的角度介绍了数据结构。

另外还有一篇有趣的文章Announcing Intel Concurrent Collections for Haskell 0.1，讨论了并行编程，他们指出：

恰好CnC概念中的步骤是纯函数。步骤只读取其输入并生成标签和项作为输出。这种设计被选择是为了将CnC带到那个难以捉摸但美妙的地方，即确定性并行性。这个决策与语言偏好无关。（实际上，主要的CnC实现是针对C++和Java的。）

然而，Haskell和CnC会是一个非常好的匹配！Haskell是唯一一个我们可以（1）强制步骤是纯的，（2）直接认识到（并利用！）步骤和图执行都是纯的主要语言。

加上Haskell非常可扩展，因此CnC“库”几乎可以感觉像一个特定于领域的语言。

虽然它没有提到性能-他们承诺在未来的文章中讨论一些实现细节和性能问题，但是Haskell的"纯度"很适合并行编程。

- YasirA

Answer 4

有人认为所有程序的本质都可以归结为机器码。

因此，如果我反汇编一份命令式程序的机器码并调整汇编器，可能会得到一个更快的程序。或者，我可以想出一种“汇编算法”，利用某些特定的CPU功能，从而比命令式语言版本更快。

这种情况是否导致我们应该在所有地方都使用汇编语言？不是的，我们决定使用命令式语言是因为它们更简单。只有当我们真正需要时，我们才会用汇编语言编写代码块。

理想情况下，我们应该使用函数式编程算法，因为它们更容易编写，而在真正需要时再使用命令式代码。

- Willem

---

不要仅局限于机器代码。当您关注CPU优化时，一切都会发生变化，而当您涉及量子尺度时（这时就变得非常奇怪了），一切又将再次改变。 - Kevin Wright

Answer 5

嗯，我猜你的意思是问是否有一种函数式编程语言实现的算法比同样算法在命令式语言中的实现更快。所谓“更快”，是指在某些输入上根据我们认为可信的某些度量标准下，在执行时间或内存占用方面表现更好。

我不排除这种可能性。:)

- Artyom Shalkhakov

Answer 6

为了阐述Yasir Arsanukaev的答案，纯函数数据结构在某些情况下可能比可变数据结构更快，因为它们共享其结构的一部分。因此，在命令式语言中可能需要复制整个数组或列表的地方，您可以通过只更改（和复制）数据结构的一小部分来完成工作。函数语言中的列表就是这样--多个列表可以共享相同的尾部，因为没有任何东西可以被修改。（这在命令式语言中也可以做到，但通常不会这样做，因为在命令式范式中，人们通常不习惯使用不可变数据。）

此外，函数语言中的惰性求值（特别是默认为惰性的Haskell）也非常有优势，因为它可以在代码的结果实际上不会被使用时消除代码执行。（然而，在命令式语言中，可以非常小心地避免首先运行此代码。）

- Ken Bloom