纯函数式编程的效率

根据Pippenger[1996]的研究，当将纯功能的Lisp系统（具有严格的评估语义，而不是惰性的）与可以变异数据的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的“纯功能数据结构” [Okasaki1998]（这是其论文的扩展版本[Okasaki
1996]）。

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

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