纯函数式编程的效率

有人知道当纯函数式编程而不是命令式编程(即允许副作用)时，可能发生的最糟糕的渐近减速是多少吗?

itowlson澄清了评论:是否存在任何问题，其中最著名的非破坏性算法渐进地比最著名的破坏性算法差，如果是这样，差多少?

58978 次浏览
小开

这篇文章声称，已知的联合查找算法的纯函数实现都比他们发布的具有纯函数接口但内部使用可变数据的实现具有更差的渐近复杂性。

事实上，其他的答案都声称不会有任何区别，例如，纯函数式代码的唯一“缺点”是它可以并行化，这让你对函数式编程社区在这些问题上的知情性/客观性有了一个概念。

编辑:

下面的评论指出，关于纯函数式编程利弊的有偏见的讨论可能不会来自“函数式编程社区”。好点。也许我所看到的倡导者只是，引用一个评论，“文盲”。

例如，我认为这个博客是由一个可以说是函数式编程社区代表的人编写的，由于它是一个“懒惰求值的点”列表，它将是一个提及懒惰和纯函数式编程可能具有的任何缺点的好地方。一个好地方应该是取代以下(技术上是正确的，但有偏见到不搞笑的地步)解雇:

如果一个严格函数在严格语言中有O(f(n))个复杂度，那么在惰性语言中它也有O(f(n))个复杂度。为什么担心?：）

小开
最佳答案

根据Pippenger [1996]，当比较纯函数式(并且具有严格的求值语义，而不是懒惰的)Lisp系统和可以改变数据的Lisp系统时，为运行在O(n)中的不纯Lisp编写的算法可以转换为运行在O(n log n)时间中的纯Lisp算法(基于Ben-Amram and Galil [1992]关于仅使用指针模拟随机访问内存的工作)。皮蓬格还指出，对于某些算法，这是你能做的最好的;在纯系统中有问题是O(n)在不纯系统中是Ω(n log n)。

关于这篇论文有几点需要注意。最重要的是它没有解决惰性函数语言，比如Haskell。伯德，琼斯和德摩尔[1997]证明了Pippenger构造的问题可以在O(n)时间内用惰性函数语言解决，但他们没有确定(据我所知，没有人确定)惰性函数语言是否可以在与突变语言相同的渐近运行时间内解决所有问题。

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

在实践中，许多算法可以用纯函数式语言实现，其效率与使用可变数据结构的语言相同。有关有效实现纯函数式数据结构的技术的良好参考，请参见Chris Okasaki的“纯功能数据结构”[Okasaki 1998](这是他的论文[Okasaki 1996]的扩展版本)。

任何需要在纯函数数据结构上实现算法的人都应该阅读Okasaki。通过用平衡二叉树模拟可变内存，每次操作最坏的结果总是O(log n)减速，但在许多情况下，你可以做得更好，Okasaki描述了许多有用的技术，从平摊技术到增量平摊工作的实时技术。纯函数式数据结构可能有点难以处理和分析，但它们提供了许多好处，如参考透明性，有助于编译器优化、并行和分布式计算，以及版本控制、撤消和回滚等特性的实现。

还要注意，所有这些只讨论渐近运行时间。许多实现纯函数式数据结构的技术都会给您带来一定程度的持续因素减速，这是由于它们工作所需的额外簿记以及相关语言的实现细节。纯函数式数据结构的好处可能超过这些恒定的因素减速，因此您通常需要根据所讨论的问题进行权衡。

参考文献

小开

对于内存使用的固定上限，应该没有区别。

< p >证明草图: 给定一个固定的内存使用上限，人们应该能够编写一个虚拟机，它执行命令式指令集，具有与实际在该机器上执行相同的渐近复杂性。这是因为您可以将可变内存作为持久数据结构来管理，允许O(log(n))读写，但是由于内存使用的上限是固定的，因此您可以拥有固定数量的内存，从而导致这些内存衰减为O(1)。因此，函数实现可以是在VM的函数实现中运行的强制版本，因此它们都应该具有相同的渐近复杂度
小开

确实有一些算法和数据结构是没有渐进有效的纯函数解决方案(即一个可在纯lambda微积分中实现的解决方案)，即使懒惰。

  • 前面提到的联合发现
  • 哈希表
  • 数组
  • 一些图算法
  • .．.

然而，我们假设在“命令式”语言中，对内存的访问是O(1)，而在理论上，它不可能如此渐近(即对于无界的问题大小)，并且在一个巨大的数据集中对内存的访问总是O(log n)，这可以在函数式语言中模拟。

此外，我们必须记住，实际上所有现代函数式语言都提供可变数据，Haskell甚至在不牺牲纯度的情况下提供了它(ST单子)。


提交答案