纯函数式编程的效率 [英] Efficiency of purely functional programming

问题描述

有谁知道什么是最糟糕的渐近放缓纯粹编程功能，而不是势在必行（即允许副作用）时可能发生的呢？

Does anyone know what is the worst possible asymptotic slowdown that can happen when programming purely functionally as opposed to imperatively (i.e. allowing side-effects)?

从由itowlson 的评论澄清：是否有的量，最好的已知的非破坏性的算法是渐近比最好的已知破坏性算法更糟任何问题，如果是的话多少

Clarification from comment by itowlson: is there any problem for which the best known non-destructive algorithm is asymptotically worse than the best known destructive algorithm, and if so by how much?

推荐答案

据<一href="http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Pure%20Versus%20Impure%20LISP.pdf">Pippenger [1996] ，比较一个Lisp系统，纯粹是功能性（并有严格的评估的语义，而不是懒惰）时，一个可以产生变异的数据，对于运行在O（不纯Lisp语言编写的算法的ñ 的）可以被转换成在运行于O（纯Lisp的一种算法的 N 的日志的 N 的）时间（基于的本 - 阿姆拉姆和Galil的[1992] 有关模拟只用指针随机存取存储器）。 Pippenger还规定，有算法，这是最好的，你可以做的;有问题这是O（ N 的）的不纯系统是Ω（ N 的日志的 N 的）在纯净的系统。

According to Pippenger [1996], when comparing a Lisp system that is purely functional (and has strict evaluation semantics, not lazy) to one that can mutate data, an algorithm written for the impure Lisp that runs in O(n) can be translated to an algorithm in the pure Lisp that runs in O(n log n) time (based on work by Ben-Amram and Galil [1992] about simulating random access memory using only pointers). Pippenger also establishes that there are algorithms for which that is the best you can do; there are problems which are O(n) in the impure system which are Ω(n log n) in the pure system.

有必须作出关于本文中的几个注意事项。最显著的是，它并没有解决偷懒函数式语言，如哈斯克尔。 鸟，琼斯和德穆尔[1997] 证明由Pippenger构建的问题是可以解决在一个慵懒的函数式语言在O（ N 的），但他们没有建立（而据我所知，没有人有）是否或者不是一个懒惰的函数式语言可以解决在同一个渐近的运行时间的所有问题，与突变的语言。

There are a few caveats to be made about this paper. The most significant is that it does not address lazy functional languages, such as Haskell. Bird, Jones and De Moor [1997] demonstrate that the problem constructed by Pippenger can be solved in a lazy functional language in O(n) time, but they do not establish (and as far as I know, no one has) whether or not a lazy functional language can solve all problems in the same asymptotic running time as a language with mutation.

由Pippenger构成的问题需要Ω（的 N 的日志的 N 的）被特别构造为实现这种结果，并且不必重新$实用，实际p $ psentative - 世界的问题。还有一些对有点出乎意料的问题，有一些限制，但必要的证明工作;尤其，该问题要求结果被计算的上线，而不能访问未来输入，并且该输入包括从一个无限组可能的原子，而不是一个固定的尺寸集的序列原子的。而本文只而设置（下限）结果的线性运行时间不纯的算法;对于需要更大的运行时间的问题，它是可能的额外为O（log的 N 的）因素见于线性问题可能能够在必要的算法额外的操作的过程中被吸收以更大的运行时间。这些澄清和公开的问题是由本 - 阿姆拉姆[1996] 简要探讨。

The problem constructed by Pippenger requires Ω(n log n) is specifically constructed to achieve this result, and is not necessarily representative of practical, real-world problems. There are a few restrictions on the problem that are a bit unexpected, but necessary for the proof to work; in particular, the problem requires that results are computed on-line, without being able to access future input, and that the input consists of a sequence of atoms from an unbounded set of possible atoms, rather than a fixed size set. And the paper only establishes (lower bound) results for an impure algorithm of linear running time; for problems that require a greater running time, it is possible that the extra O(log n) factor seen in the linear problem may be able to be "absorbed" in the process of extra operations necessary for algorithms with greater running times. These clarifications and open questions are explored briefly by Ben-Amram [1996].

在实践中，许多算法可以在纯函数语言在相同的效率实现为在使用可变的数据结构的语言。有关技术的一个很好的参考，以用于有效地实现纯功能性的数据结构，见克里斯Okasaki的纯功能数据结构[1998年Okasaki ] （这是他的论文的扩展版本[Okasaki 1996] ）

In practice, many algorithms can be implemented in a pure functional language at the same efficiency as in a language with mutable data structures. For a good reference on techniques to use for implementing purely functional data structures efficiently, see Chris Okasaki's "Purely Functional Data Structures" [Okasaki 1998] (which is an expanded version of his thesis [Okasaki 1996]).

任何人谁需要落实纯粹功能的数据结构，算法应为Okasaki。你总是可以得到在最坏的一个O（日志的 N 的），每运行减速通过模拟一个平衡二叉树可变的内存，但在很多情况下，你可以做的比这好得多，而且Okasaki介绍了很多实用的技巧从摊销技术来实时那些做摊销的工作逐步。纯功能性数据结构可能会有点难以处理和分析，但它们提供许多优惠，如引用透明是在编译器优化有益的，并行和分布式计算，并在实施类似的版本，撤消和回退功能。

Anyone who needs to implement algorithms on purely-functional data structures should read Okasaki. You can always get at worst an O(log n) slowdown per operation by simulating mutable memory with a balanced binary tree, but in many cases you can do considerably better than that, and Okasaki describes many useful techniques, from amortized techniques to real-time ones that do the amortized work incrementally. Purely functional data structures can be a bit difficult to work with and analyze, but they provide many benefits like referential transparency that are helpful in compiler optimization, in parallel and distributed computing, and in implementation of features like versioning, undo, and rollback.

另请注意，这一切只讨论渐近的运行时间。许多技术实现纯功能性数据结构给你一定的常数因子放缓，由于需要为他们付出更多的簿记，和有问题的语言实现细节。纯功能性数据结构的好处可能超过这些常数因子的速度变慢，所以你一般都需要根据所涉及的问题作出权衡。

Note also that all of this discusses only asymptotic running times. Many techniques for implementing purely functional data structures give you a certain amount of constant factor slowdown, due to extra bookkeeping necessary for them to work, and implementation details of the language in question. The benefits of purely functional data structures may outweigh these constant factor slowdowns, so you will generally need to make trade-offs based on the problem in question.

• 本 - 阿姆拉姆，阿米尔和加利尔，兹维1992年。关于指针与地址 ACM学报，39（3），页617-648，1992年7月
• 本 - 阿姆拉姆，阿米尔1996年。关于纯不纯Lisp语言Pippenger的比较注未发表的手稿，哥本哈根，丹麦打底裤，大学
• 在伯德，理查德·琼斯，杰兰特和德停泊，Oege 1997年的更多欲速则不达：懒惰与急于评价 [功能编程7，5页541-547，1997年9月
• Okasaki，克里斯 - 1996年纯功能数据结构的博士论文，卡耐基梅隆大学
• Okasaki，克里斯 - 1998年纯功能数据结构剑桥大学preSS，英国剑桥
• Pippenger，尼古拉斯1996年<一href="http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Pure%20Versus%20Impure%20LISP.pdf">"Pure对战不纯Lisp的 ACM研讨会编程语言的原理，104-109页，1996年1月

• Ben-Amram, Amir and Galil, Zvi 1992. "On Pointers versus Addresses" Journal of the ACM, 39(3), pp. 617-648, July 1992
• Ben-Amram, Amir 1996. "Notes on Pippenger's Comparison of Pure and Impure Lisp" Unpublished manuscript, DIKU, University of Copenhagen, Denmark
• Bird, Richard, Jones, Geraint, and De Moor, Oege 1997. "More haste, less speed: lazy versus eager evaluation" Journal of Functional Programming 7, 5 pp. 541–547, September 1997
• Okasaki, Chris 1996. "Purely Functional Data Structures" PhD Thesis, Carnegie Mellon University
• Okasaki, Chris 1998. "Purely Functional Data Structures" Cambridge University Press, Cambridge, UK
• Pippenger, Nicholas 1996. "Pure Versus Impure Lisp" ACM Symposium on Principles of Programming Languages, pages 104–109, January 1996

这篇关于纯函数式编程的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！