函数式编程中最快的排序方法

Question

作为本科生，我学习了O(n log n)的排序算法以及证明当我们只能比较两个数字时，在通用情况下我们无法做得更好。这是针对计算模型中的随机访问内存的。

我想知道是否存在这样的理论下界，适用于函数式（引用透明）程序。假设每次Beta规约都算一步，每次比较也算一步。

- Abhishek Anand

---

是的，在函数式编程中，快速排序（QuickSort）是可能的（而且相当简单），时间复杂度为O(n lg n)。 - Gabe

我觉得Mergesort更容易实现和理解，包括确定下限，尤其是因为每个子问题（即递归步骤）都将问题精确地分成两半。Mergesort具有O(n lg n)的时间复杂度，但在不同的实现中具有不同的空间复杂度。 - user2864740

我相信在这个语境中，“函数式编程风格”只是指编写引用透明的代码。已知你总是可以通过加上log n的开销在纯代码中模拟可变内存，并且有些问题你无法做得比这更好(更多细节请见此：https://dev59.com/sXI-5IYBdhLWcg3wKE-x#1990580)，这就是为什么算法的时间复杂度在函数式编程风格下可能与通常情况不同的原因。 - Ben

谢谢@Ben，我会更新问题。 - Abhishek Anand

@user2864740：并非所有排序算法都可以以函数式风格编写，并且仍然具有相同的时间复杂度。函数式编程风格意味着在分配变量后不更改任何变量，这意味着您无法在创建数组后修改单个元素。 - Gabe

Answer 1

假设您同意证明，即在仅具有比较的一般情况下，我们无法做得比(n*log n)更好。那么问题是，我们是否可以展示在没有副作用的情况下做到相同。

一种方法是利用这个想法：如果您可以在O(n * log n)内构建一个不可变的二叉搜索树，然后进行中序遍历（可在O(n)内完成），那么我们将拥有一个排序算法。

如果我们可以遍历所有项目并将每个项目添加到平衡的不可变（持久）树中，时间复杂度为O(log n)，那么它将为我们提供O(n * log n)算法。

我们能否在O(log n)内向持久性二叉树添加元素？当然，对于持久数据结构库的每个合理实现，都有具有O(log n)插入的平衡二叉搜索树的不可变变体。

为了理解为什么这是可能的，可以想象一个标准的平衡二叉搜索树，如红黑树。你可以通过遵循与可变版本相同的算法来创建它的不可变版本，除了每当指针或颜色改变时，你需要分配一个新节点，并将其所有父节点一直转换到根（如果必要，同时还要转换它们）。未更改的侧枝被重用。影响的节点最多有O(log n)个，因此每次插入最多有O(log n)个操作（包括分配）。如果你知道红黑树，你会发现除了常数之外没有其他乘数（对于旋转，你可以为受影响的兄弟节点获得一些额外的分配，但这仍然保持为一个常数因子）。

这种相当非正式的演示可以让你知道存在一种无副作用的O(n * log n)排序证明。但是，我留下了一些更多的细节，例如分配在这里被认为是O(1)，但这并不总是正确的，但那会变得太复杂。

- jJ'

---

谢谢。那听起来很有道理。我会尝试正式地分析它。 - Abhishek Anand

Answer 2

我认为现代函数式编程实现（至少是Clojure，因为那是我唯一了解的）确实具有不可变内存，但这并不意味着更改列表等会导致整个原始列表的复制。因此，我不相信使用命令式或函数式习惯语实现排序算法之间存在数量级的计算差异。

关于如何在不复制内存的情况下修改不可变列表的更多信息：

为了说明这可能的工作方式，请考虑来自Clojure参考资料的此代码片段：http://clojure-doc.org/articles/tutorials/introduction.html

在Clojure中，所有标量和核心数据结构都是这样的。它们是值。它们是不可变的。

地图{:name "John" :hit-points 200 :super-power :resourcefulness}是一个值。如果你想“改变”约翰的命中点数，你并没有真正改变任何东西，而是只是创造了一个全新的哈希映射值。

但是等等：如果你在类C语言的命令式编程中做过任何事情，这听起来很浪费。然而，这种不可变性的阴影是，在幕后，Clojure共享数据结构。它跟踪它们所有的部分并广泛地重复使用它们。例如，如果你有一个100万项列表，并想要添加一个项目，你只需告诉Clojure，“给我一个新的，但加上这个项目”，Clojure就会忠实地立即给你返回一个1000001项列表。你不知道它正在重用原始列表。

那么为什么对不可变性如此关注呢？

我不知道函数式编程的完整历史，但在我看来，函数式语言的不可变性特征基本上是将共享内存的复杂性抽象出来。

虽然这很酷，但如果没有语言管理的共享数据结构作为整个机制的基础，对于许多用例而言，它将变得难以实际应用。

- Jonathan Schneider

---

谢谢jkschnieder。我会查看你的Clojure链接。总的来说，我同意函数式语言的底层求值器可以很聪明地避免不必要的复制。但是，在许多情况下，使用函数式语言有许多好处，尤其是在定理证明中。Hoare逻辑并不像依赖类型那样适用于程序正确性的形式推理。 - Abhishek Anand

很多人称赞Clojure语言，但它是否能回答这个问题呢？ - Ingo

@Ingo - 在我看来，像Mergesort这样的算法在命令式语言和函数式语言之间计算复杂度差异的唯一明显原因是语言对内存的处理方式。我的意思是，在使用现代函数式语言进行实际应用时，即使是不可变性也不会影响算法的性能。Clojure只是其中一个例子。我相信其他语言也是类似的。 - Jonathan Schneider

@Abhishek - 我不确定这个假设如何精确地适用于你的证明系统，但是假设不必要的复制没有发生足以简化情况吗？ - Jonathan Schneider

是的！当您没有状态（或其他副作用）需要担心时，您可以将方法（函数）视为纯数学函数--即接受输入并返回输出，不做其他任何事情。然后，方法的行为将不依赖于除输入之外的任何内容。 - Abhishek Anand