我正在寻找功能风格的算法（或这种算法的参数），这比命令式更快 .
我喜欢功能代码，因为它具有表现力，而且比它的命令性吊坠更容易阅读 . 但我也知道这种表现力可能会花费运行时开销 . 并不总是由于尾递归等技术 - 但往往它们更慢 .
编程时我不考虑功能代码的运行时成本，因为现在PC非常快，开发时间比运行时更昂贵 . 此外，对我而言，可读性比性能更重要 . 然而，我的程序足够快，所以我很少需要以命令式方式解决问题 .
有些算法在实践中应该以命令式（如排序算法）实现，否则在大多数情况下它们太慢或需要大量内存 . 相反，由于模式匹配等技术，整个程序（如用函数式语言编写的解析器）可能比用命令式语言编写的更快，因为编译器可能会优化代码 .
但是，是否有任何算法在功能样式上更快或者是否有可能设置这种算法的参数？
6 回答
有人可能会争辩说所有程序都归结为机器代码 .
因此，如果我拆解机器代码（命令式程序）并调整汇编程序，我可能最终得到一个更快的程序 . 或者我可以想出一个利用某些特定CPU功能的“汇编算法”，因此它确实比命令式语言版本更快 .
这种情况是否会导致我们应该在任何地方使用汇编程序？不，我们决定使用命令式语言，因为它们不那么繁琐 . 我们在汇编程序中编写部分因为我们真的需要 .
理想情况下，我们也应该使用FP算法，因为它们编码不那么麻烦，并且在我们真正需要时使用命令式代码 .
好吧，我猜你的意思是问一下，在函数式编程语言中是否存在一种算法的实现，它比同一算法的另一种实现更快，但是在命令式语言中 . “更快”我的意思是它在执行时间方面表现更好根据我们认为值得信赖的一些测量，某些输入的内存占用 .
我不排除这种可能性 . :)
一个简单的推理 . 我不保证术语，但似乎有道理 .
需要将要执行的功能程序转换为一组机器指令 .
所有机器（我听说过）都是必不可少的 .
因此，对于每个功能程序，都有一个命令式程序（粗略地说，用汇编语言），相当于它 .
所以，在我们获得“功能性计算机”之前，您可能必须对“表现力”感到满意 .
简短的回答：
任何可以轻松并行的东西，因为它没有副作用，在多核处理器上会更快 .
例如，QuickSort在与不可变集合一起使用时可以很好地扩展：http://en.wikipedia.org/wiki/Quicksort#Parallelization
在其他条件相同的情况下，如果你有两个可以合理地描述为等价的算法，除了一个在不可变数据上使用纯函数，而第二个算法依赖于就地突变，那么第一个算法将轻松扩展到多个核心 .
甚至可能是您的编程语言可以为您执行此优化的情况，就像scalaCL插件将编译代码以在GPU上运行一样 . （我现在想知道SIMD指令是否是一个“功能”处理器）
因此，给定并行硬件，第一个算法将表现得更好，并且您拥有的核心越多，差异就越大 .
FWIW有Purely functional data structures，它受益于函数式编程 .
Chris Okasaki在Purely Functional Data Structures上也有一本很好的书，它从功能语言的角度介绍了数据结构 .
另一篇有趣的文章Announcing Intel Concurrent Collections for Haskell 0.1，关于并行编程，他们注意到：
它没有谈到性能 - 他们承诺在未来的帖子中讨论一些实现细节和性能，但Haskell的“纯粹”非常适合并行编程 .
要详细说明Yasir Arsanukaev的答案，纯粹的功能数据结构在某些情况下可能比可变数据结构更快，因为它们共享其结构的一部分 . 因此，在您可能必须使用命令式语言复制整个数组或列表的地方，您可以通过一小部分复制来逃避，因为您只能更改（和复制）数据结构的一小部分 . 函数式语言中的列表是这样的 - 多个列表可以共享相同的尾部，因为无法修改任何内容 . （这可以用命令式语言完成，但通常不会用于讨论不可变数据 . ）
此外，函数式语言中的惰性求值（特别是默认为惰性的Haskell）也非常有利，因为它可以在代码的结果实际不被使用时消除代码执行 . （但是，可以非常小心，不要在命令式语言中首先运行此代码 . ）