纯功能编程的效率
有没有人知道什么是纯粹功能性编程而不是命令性（即允许副作用）编程时可能发生的最差渐近减速？
来自itowlson的评论的澄清：有没有什么问题最着名的非破坏性算法渐近地比最知名的破坏性算法更差，如果是这样，多少？
根据Pippenger [1996]的观点，当比较一个纯粹功能性的Lisp系统（并且具有严格的评估语义，而不是懒惰的）到可以改变数据的Lisp系统时，可以编译为在O（n）中运行的不纯的Lisp编写的算法到运行在O（n log n）时间内的纯Lisp算法（基于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的“纯功能数据结构”[Okasaki 1998]（这是他的论文[Okasaki 1996]的扩展版本）。
任何需要在纯功能数据结构上实现算法的人都应该阅读冈崎。 通过使用平衡二叉树模拟可变内存，每次操作总是可以减少O（log n）减速，但在许多情况下，您可以做得比这更好，而且Okasaki描述了许多有用的技术，从摊销技术到实时操作，它们是逐步完成分期付款工作的实时账户。 纯功能数据结构可能有点难以处理和分析，但是它们提供了很多好处，如引用透明性有助于编译器优化，并行和分布式计算以及实现版本控制，撤消和回滚等功能。
还要注意，所有这些只讨论了渐近运行时间。 由于实施纯功能数据结构所需的额外簿记和有关语言的实施细节，许多实现纯功能数据结构的技术会给您带来一定的不断因素放缓。 纯功能数据结构的好处可能会超过这些不断下降的因素，所以您通常需要根据相关问题进行权衡。
参考
实际上有几种算法和数据结构，即使在懒惰的情况下，其中也没有渐近效率的纯功能解决方案（可以在纯朗博达演算中实现）。
然而，我们假设在“命令式”语言中，访问内存是O（1），而在理论上，它不可能如此渐近（即对于无限大的问题）并且访问大型数据集中的内存始终是O（log n） ，它可以用功能语言来模拟。
另外，我们必须记住，实际上所有现代功能语言都提供可变数据，而Haskell甚至在不牺牲纯度的情况下提供它（ST monad）。
本文声明联合发现算法的已知纯功能实现都比它们发布的算法具有更差的渐近复杂性，它具有纯粹的功能接口，但在内部使用可变数据。
其他答案声称绝不会有任何区别，例如，纯函数代码的唯一“缺点”是它可以并行化，让您了解功能性编程社区在这些问题上的信息/客观性。
编辑：
下面的评论指出，对纯函数式编程的利弊的偏见讨论可能不是来自“函数编程社区”。 好点子。 也许我所看到的倡导者只是引用评论“文盲”。
例如，我认为这篇博客文章是由可以说是功能性编程社区代表的人编写的，因为它是“懒惰评估点”的列表，所以它将是一个很好的地方，懒惰和纯粹的功能编程可能有。 一个好的地方可能会取代以下（技术上属实，但偏向于不好笑）解雇：
如果严格的函数在严格的语言中具有O（f（n））复杂性，那么它也具有懒惰语言的复杂性O（f（n））。 为什么要担心？ :)
链接地址: http://www.djcxy.com/p/8367.html