是否有一种比命令式算法更快的函数式算法？
我正在寻找一种比命令式更快的函数式算法（或此类算法的参数）。
我喜欢函数式代码，因为它具有表现力，而且比命令式代码更容易阅读。但我也知道这种表达能力会消耗运行时开销。并不总是由于尾递归等技术 - 但它们通常更慢。
在编程时，我不会考虑功能代码的运行时成本，因为现在的 PC 速度非常快，开发时间比运行时更昂贵。此外，对我来说，可读性比性能更重要。尽管如此，我的程序足够快，所以我很少需要以命令式的方式解决问题。
有一些算法在实践中应该以命令式方式实现（例如排序算法），否则在大多数情况下它们太慢或需要大量内存。 相比之下，由于诸如模式匹配之类的技术，整个程序（例如用函数式语言编写的解析器）可能比用命令式语言编写的程序快得多，因为编译器可以优化代码。
但是是否有任何函数式风格更快的算法或者是否有可能设置此类算法的参数？
I'm searching for an algorithm (or an argument of such an algorithm) in functional style which is faster than an imperative one.
I like functional code because it's expressive and mostly easier to read than it's imperative pendants. But I also know that this expressiveness can cost runtime overhead. Not always due to techniques like tail recursion - but often they are slower.
While programming I don't think about runtime costs of functional code because nowadays PCs are very fast and development time is more expensive than runtime. Furthermore for me readability is more important than performance. Nevertheless my programs are fast enough so I rarely need to solve a problem in an imperative way.
There are some algorithms which in practice should be implemented in an imperative style (like sorting algorithms) otherwise in most cases they are too slow or requires lots of memory.
In contrast due to techniques like pattern matching a whole program like a parser written in an functional language may be much faster than one written in an imperative language because of the possibility of compilers to optimize the code.
But are there any algorithms which are faster in a functional style or are there possibilities to setting up arguments of such an algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
简短的回答是：
任何可以轻松并行的事物，因为它没有副作用，在多核处理器上都会更快。
例如，QuickSort 在与不可变集合一起使用时可以很好地扩展：http://en.wikipedia。 org/wiki/Quicksort#Parallelization
在其他条件相同的情况下，如果您有两种可以合理地描述为等效的算法，除了一种在不可变数据上使用纯函数，而第二种依赖于就地突变，那么第一个算法将轻松扩展到多个核心。
甚至可能您的编程语言可以为您执行此优化，就像 scalaCL 插件将编译代码以在您的 GPU 上运行一样。 （我现在想知道 SIMD 指令是否使其成为一个“功能”处理器）
因此，给定并行硬件，第一个算法将执行得更好，并且拥有的内核越多，差异就会越大。
The short answer:
Anything that can be easily made parallel because it's free of side-effects will be quicker on a multi-core processor.
QuickSort, for example, scales up quite nicely when used with immutable collections: http://en.wikipedia.org/wiki/Quicksort#Parallelization
All else being equal, if you have two algorithms that can reasonably be described as equivalent, except that one uses pure functions on immutable data, while the second relies on in-place mutations, then the first algorithm will scale up to multiple cores with ease.
It may even be the case that your programming language can perform this optimization for you, as with the scalaCL plugin that will compile code to run on your GPU. (I'm wondering now if SIMD instructions make this a "functional" processor)
So given parallel hardware, the first algorithm will perform better, and the more cores you have, the bigger the difference will be.
FWIW 有纯函数式数据结构，它们受益于函数式编程。
还有一本关于纯函数数据结构的好书Chris Okasaki，从函数式语言的角度介绍了数据结构。
另一篇有趣的文章 宣布推出 Intel Concurrent Collections for Haskell 0.1，关于并行编程，他们指出：
它没有提及性能——他们承诺在未来的帖子中讨论一些实现细节和性能——但 Haskell 以其“纯粹性”非常适合并行编程。
FWIW there are Purely functional data structures, which benefit from functional programming.
There's also a nice book on Purely Functional Data Structures by Chris Okasaki, which presents data structures from the point of view of functional languages.
Another interesting article Announcing Intel Concurrent Collections for Haskell 0.1, about parallel programming, they note:
It doesn't say about performance – they promise to discuss some of the implementation details and performance in future posts, – but Haskell with its "pureness" fits nicely into parallel programming.
有人可能会说所有程序都可以归结为机器代码。
因此，如果我反汇编（命令式程序的）机器代码并调整汇编器，我也许最终会得到一个更快的程序。或者我可以想出一种利用某些特定 CPU 功能的“汇编算法”，因此它确实比命令式语言版本更快。
这种情况是否可以得出我们应该到处使用汇编程序的结论？不，我们决定使用命令式语言，因为它们不那么麻烦。我们用汇编程序编写片段，因为我们确实需要这样做。
理想情况下，我们还应该使用 FP 算法，因为它们编写起来不那么麻烦，并且在真正需要时使用命令式代码。
One could argue that all programs boil down to machine code.
So, if I dis-assemble the machine code (of an imperative program) and tweak the assembler, I could perhaps end up with a faster program. Or I could come up with an "assembler algorithm" that exploits some specific CPU feature, and therefor it really is faster than the imperative language version.
Does this situation lead to the conclusion that we should use assembler everywhere? No, we decided to use imperative languages because they are less cumbersome. We write pieces in assembler because we really need to.
Ideally we should also use FP algorithms because they are less cumbersome to code, and use imperative code when we really need to.
好吧，我猜你的意思是问是否有一个用函数式编程语言实现的算法比用命令式语言实现相同算法的另一个实现要快。我所说的“更快”是指根据我们认为值得信赖的一些测量，它在某些输入上的执行时间或内存占用方面表现更好。
我不排除这种可能性。 :)
Well, I guess you meant to ask if there is an implementation of an algorithm in functional programming language that is faster than another implementation of the same algorithm but in an imperative language. By "faster" I mean that it performs better in terms of execution time or memory footprint on some inputs according to some measurement that we deem trustworthy.
I do not exclude this possibility. :)
为了详细说明 Yasir Arsanukaev 的答案，在某些情况下，纯函数数据结构可能比可变数据结构更快，因为它们共享其结构的各个部分。因此，在您可能必须使用命令式语言复制整个数组或列表的地方，您可以只进行一小部分复制，因为您只能更改（和复制）数据结构的一小部分。函数式语言中的列表就像这样——多个列表可以共享相同的尾部，因为没有任何内容可以修改。 （这可以用命令式语言完成，但通常不能，因为在命令式范式中，人们通常不习惯谈论不可变数据。）
此外，函数式语言中的惰性求值（特别是Haskell（默认情况下是惰性的）也非常有利，因为当代码的结果实际上不会被使用时，它可以消除代码执行。 （但是，人们可以非常小心，不要首先在命令式语言中运行此代码。）
To elaborate on Yasir Arsanukaev's answer, purely functional data structures can be faster than mutable data structures in some situations becuase they share pieces of their structure. Thus in places where you might have to copy a whole array or list in an imperative language, where you can get away with a fraction of the copying because you can change (and copy) only a small part of the data structure. Lists in functional languages are like this -- multiple lists can share the same tail since nothing can be modified. (This can be done in imperative languages, but usually isn't, because within the imperative paradigm, people aren't usually used to talking about immutable data.)
Also, lazy evaluation in functional languages (particularly Haskell which is lazy by default) can also be very advantageous because it can eliminate code execution when the code's results won't actually be used. (One can be very careful not to run this code in the first place in imperative languages, however.)
一个简单的推理。我不保证术语，但它似乎是有道理的。
因此，在我们获得“功能计算机”之前，您可能必须满足于“表现力”。
A simple reasoning. I don't vouch for terminology, but it seems to make sense.
So, you'll probably have to be satisfied with 'expressiveness', until we get 'functional computers'.