Opt*_*Opt 395 algorithm performance functional-programming
有没有人知道什么是最简单的渐近减速,当编程纯粹功能而不是命令性(即允许副作用)时可能发生？
来自itowlson评论的澄清:有没有哪个问题最着名的非破坏性算法渐渐比最着名的破坏性算法更糟糕,如果是这样的话多少呢？
Bri*_*ell 528
根据Pippenger [1996]的说法,当将一个纯函数的Lisp系统(并且具有严格的评估语义,而不是懒惰)与可以改变数据的系统进行比较时,可以翻译为在O(n)中运行的不纯Lisp编写的算法在纯粹的Lisp中运行在O(n log n)时间内的算法(基于Ben-Amram和Galil [1992]关于仅使用指针模拟随机存取存储器的工作).Pippenger还确定有一些算法可以做到最好; 不纯系统中存在O(n)的问题,即纯系统中的Ω(n log n).
关于这篇论文,有几点需要注意.最重要的是它没有解决惰性函数语言,例如Haskell.Bird,Jones和De Moor [1997]证明Pippenger构造的问题可以在O(n)时间内用懒惰的函数式语言解决,但是他们没有建立(据我所知,没有人有)不是一种懒惰的函数式语言可以解决与具有变异的语言相同的渐近运行时间内的所有问题.
由Pippenger构造的问题需要Ω(n log n)专门构造以实现该结果,并且不一定代表实际的现实问题.这个问题有一些限制意外,但证明工作是必要的; 特别是,问题要求结果是在线计算的,不能访问未来的输入,并且输入由来自无限可能原子集的原子序列组成,而不是固定大小集.并且本文仅针对线性运行时间的不纯算法建立(下界)结果; 对于需要更长运行时间的问题,线性问题中看到的额外O(log n)因子可能能够在具有更长运行时间的算法所需的额外操作过程中被"吸收".Ben-Amram [1996]简要探讨了这些澄清和开放式问题.
实际上,许多算法可以用纯函数语言实现,效率与具有可变数据结构的语言相同.有关用于有效实现纯功能数据结构的技术的良好参考,请参阅Chris Okasaki的"Purely Functional Data Structures"[Okasaki 1998](这是他的论文的扩展版本[Okasaki 1996]).
任何需要在纯功能数据结构上实现算法的人都应该阅读Okasaki.通过使用平衡二叉树模拟可变内存,每次操作总是可以减少O(log n)减速,但在许多情况下,你可以做得更好,而Okasaki描述了许多有用的技术,从摊销技术到实际按时递增摊销工作的时间.纯功能数据结构可能有点难以使用和分析,但它们提供了许多好处,如参考透明性,有助于编译器优化,并行和分布式计算,以及版本控制,撤消和回滚等功能的实现.
另请注意,所有这些都只讨论了渐近运行时间.许多用于实现纯功能数据结构的技术会为您提供一定量的常数因子减速,这是因为它们需要额外的簿记工作,以及相关语言的实现细节.纯函数数据结构的好处可能超过这些常数因子减速,因此您通常需要根据所讨论的问题进行权衡.
jkf*_*kff 44
确实有几种算法和数据结构,即使有懒惰,也没有渐近有效的纯函数解(在纯lambda演算中可实现的解).
但是,我们假设在"命令式"语言中,对内存的访问是O(1),而理论上不能如此渐近(即对于无界问题大小)和对大型数据集中的内存的访问总是O(log n) ,可以用函数式语言模拟.
此外,我们必须记住,实际上所有现代函数语言都提供可变数据,而Haskell甚至在不牺牲纯度的情况下提供它(ST monad).
Pas*_*uoq 36
本文声称,union-find算法的已知纯函数实现都具有比它们发布的渐近复杂度更低的渐近复杂度,它具有纯粹的功能接口但在内部使用可变数据.
事实上,其他答案声称永远不会有任何差异,例如,纯功能代码的唯一"缺点"是它可以并行化,让您了解功能编程社区在这些问题上的知情/客观性.
编辑:
下面的评论指出,对纯函数式编程的优缺点的偏见讨论可能不是来自"函数式编程社区".好点子.也许我认为的倡导者只是引用一个评论,"文盲".
例如,我认为这篇博客文章是由一个可以说是功能编程社区代表的人编写的,因为它是一个"懒惰评估点"的列表,所以它是一个提到任何缺点的好地方.懒惰和纯功能编程可能有.一个好的地方本来可以代替以下(技术上是正确的,但偏向于不好笑)解雇:
如果严格的函数在严格的语言中具有O(f(n))复杂度,那么它在惰性语言中也具有复杂度O(f(n)).为什么要担心？:)