algorithm - 纯函数式编程的效率

Question

有谁知道纯功能编程而不是强制性编程(即产生副作用)时可能发生的最坏的渐近减慢？

从itowlson的评论中澄清:是否存在最知名的无损算法比最知名的破坏性算法渐近恶化的问题？

Answer 1

根据Pippenger [1996]的说法，将纯功能(并且具有严格的评估语义，而不是惰性的)Lisp系统与可以变异数据的Lisp系统进行比较时，可以将针对以O(n)运行的不纯Lisp编写的算法转换为一种算法。在运行时间为O(n log n)的纯Lisp中(基于Ben-Amram and Galil [1992]关于仅使用指针模拟随机访问内存的工作)。皮蓬格(Pippenger)还确定了某些算法，这是您可以做的最好的事情。在不纯系统中存在O(n)的问题，在纯系统中存在Ω(n log n)的问题。

关于本文有一些警告。最重要的是，它不解决惰性函数语言，例如Haskell。 Bird, Jones and De Moor [1997]证明了由Pippenger构造的问题可以在O(n)时间内用一种惰性函数语言解决，但是它们无法确定(据我所知，没有人知道)一种惰性函数语言是否可以解决所有问题与带有变异的语言在相同的渐近运行时间中出现问题。

皮蓬格(Pippenger)构造的问题需要Ω(n log n)才能达到该结果，并且不一定代表实际的实际问题。对这个问题有一些限制，这是出乎意料的，但是对于证明工作是必不可少的。特别地，该问题要求结果是在线计算的，而无法访问将来的输入，并且该输入由来自无限可能原子集合的原子序列组成，而不是固定大小的集合。并且本文仅针对线性运行时间的不纯算法建立(下界)结果。对于需要更长运行时间的问题，可能会在运行时间较长的算法所需的额外操作过程中，“吸收”线性问题中出现的额外O(log n)因子。 Ben-Amram [1996]简要探讨了这些澄清和开放性问题。

实际上，可以用纯功能语言以与具有可变数据结构的语言相同的效率来实现许多算法。有关有效用于实现纯功能数据结构的技术的良好引用，请参见Chris Okasaki's "Purely Functional Data Structures" [Okasaki 1998](这是他的论文[Okasaki 1996]的扩展版本)。

任何需要在纯功能数据结构上实现算法的人都应该阅读Okasaki。通过用平衡的二叉树模拟可变内存，您每次操作总是最糟糕的情况是O(log n)变慢，但是在许多情况下，您可以做得更好，而且Okasaki描述了许多有用的技术，从摊销技术到实物化，逐步进行摊销的时间。纯功能数据结构可能很难使用和分析，但是它们提供了很多好处，例如引用透明性，有助于编译器优化，并行和分布式计算以及实现诸如版本控制，撤消和回滚之类的功能。

还要注意，所有这些都仅讨论渐近的运行时间。许多实现纯功能数据结构的技术会给您一定程度的恒定因子减慢，这是因为它们需要额外的簿记工作以及相关语言的实现细节。纯功能数据结构的好处可能胜过这些恒定因素的放缓，因此您通常需要根据所讨论的问题进行权衡。

引用

Ben-Amram，Amir和Galil，Zvi，1992年。"On Pointers versus Addresses" ACM杂志，39(3)，第617-648页，1992年7月

Ben-Amram，阿米尔，1996年。"Notes on Pippenger's Comparison of Pure and Impure Lisp"丹麦哥本哈根大学DIKU未出版手稿

Bird，Richard，Jones，Geraint和De Moor，Oege，1997年。"More haste, less speed: lazy versus eager evaluation"函数式编程杂志，第7卷，第5页，第541-547页，1997年9月

冈崎，克里斯(Chris)，1996年。"Purely Functional Data Structures"卡内基梅隆大学博士学位论文

冈崎，克里斯(Chris 1998)。"Purely Functional Data Structures"剑桥大学出版社，英国剑桥

Pippenger，尼古拉斯，1996年。"Pure Versus Impure Lisp" ACM编程语言原理专题讨论会，第104-109页，1996年1月