当比较元素很耗费时间时，我可以使用哪些排序技术？

Question

问题

我有一个应用程序，其中我想对元素 a₀, a₁,...,a_n-1 组成的数组 a 进行排序。我有一个比较函数 cmp(i,j)，它比较元素 a_i 和 a_j，以及一个交换函数 swap(i,j)，它交换数组中的元素 a_i 和 a_j。在应用程序中，执行 cmp(i,j) 函数可能非常昂贵，甚至比排序中任何其他步骤（当然除了其他 cmp(i,j) 调用）的时间都要长得多。您可以将 cmp(i,j) 视为相当冗长的 IO 操作。

请假设出于本问题的目的，没有办法使 cmp(i,j) 更快。假设可能使 cmp(i,j) 更快的所有优化已经完成。

问题

• 是否存在一种排序算法，可以最小化对 cmp(i,j) 的调用次数？

• 在我的应用程序中，可能会编写谓词 expensive(i,j)，如果调用 cmp(i,j) 将花费很长时间，则该谓词为 true。在我的当前应用程序中，expensive(i,j) 是廉价的，并且 expensive(i,j) ∧ expensive(j,k) → expensive(i,k) 大多数情况下成立。尽管不保证。

  是否存在一种利用 expensive(i,j) 的更好的算法来避免昂贵的比较操作？如果是，您能否指出此类算法？

• 我想了解更多关于此主题的资料。

示例

这是一个与我所拥有的应用程序有些相似的示例。

考虑一组可能很大的文件。在这个应用程序中，目标是在它们之中找到重复的文件。这本质上归结为按照某些任意标准对文件进行排序，然后按顺序遍历它们，输出遇到的相等文件的序列。

当然，读取大量数据是昂贵的，因此可以例如仅读取每个文件的前1MB并计算此数据的哈希函数。如果文件比较相等，则哈希也相等，但反过来不一定成立。两个大文件可能只在末尾附近的一个字节上有所不同。

在这种情况下，expensive(i,j)的实现简单地检查哈希是否相等。如果相等，则需要进行昂贵的深度比较。

- fuz

---

基数排序是我所知道的唯一非比较排序，但您需要将对象视为整数：http://en.wikipedia.org/wiki/Radix_sort - IllusiveBrian

我猜想，1）选择标准的低复杂度排序算法；2）缓存所有比较结果。你可能可以利用昂贵的谓词来更好地选择快速排序中的枢轴元素，但我怀疑这并不会带来很大的收益。 - Rup

expensive(i, j) 这个关系有特定的结构吗？ - Pascal Cuoq

我认为正如Rup所说，如果你有可用的空间，就缓存结果。当然，计算任何和所有的传递隐含结果，而不是查询它们（如果你已经查询确定“i<j”和“j<k”，那么就不需要为“i”和“k”调用“cmp”）。 - Damien_The_Unbeliever

@FUZxxl：针对你的例子，你可以先使用更便宜的标准，例如首先按大小排序，然后使用（记忆化的）快速哈希，再使用（记忆化的）完整哈希，或者可能使用多个哈希（即对块进行哈希），这将使您能够在第一个不匹配时停止。 正如Damien_The_Unbeliever所说，缓存传递结果可能会节省额外的比较。 - Hasturkun

Answer 1

我会尽力回答每一个问题。

• 有没有一种排序算法可以最小化对 cmp(i,j) 的调用次数？

传统的排序方法可能有一些变化，但通常情况下，对于排序列表所需的最小比较次数存在着数学上的限制，大多数算法都利用了这一点，因为比较通常不是廉价的。您可以尝试通过其他方式进行排序，或者尝试使用可能更快且近似于真实解决方案的快捷方式。

• 如果存在 expensive(i,j) ，是否可以使用更好的算法来避免昂贵的比较操作？如果是，您能指出这样的算法吗？

我认为您无法绕过至少进行最小数量的比较的必要性，但您可以尝试改变比较的内容。如果您可以比较哈希值或数据的子集而不是整个数据，那肯定会有所帮助。任何简化比较操作的方法都会产生很大的差异，但是如果不知道数据的具体细节，很难建议特定的解决方案。

• 我想了解这个主题的更多材料。

请查看以下内容：

• 显然，唐纳德·克努斯（Donald Knuth）的《计算机程序设计艺术，第3卷》有关于此主题的部分，但我手头没有副本。
• 维基百科当然对这个问题有一些见解。
• 使用最少比较次数对数组进行排序
• 如何确定就地对列表进行排序所需的最小交换次数？
• 比较排序技术的限制

- pattivacek

---

哦，是的，那是个好主意。当我从度假回来后，我会看一下我的《计算机程序设计艺术》第三卷的副本。 - fuz

你编辑后的问题中的示例是一个很好的快捷方式或备选比较操作的想法。然而，排序算法本身仍然受限于一定数量的比较操作，但如果你可以改变比较的内容，那将是关键。 - pattivacek

问题是，无论我做什么，在某些情况下（特别是当两个大文件几乎相等时）都无法避免快捷方式。我当然可以假设如果前几兆字节相等，则两个文件相等，但这显然是错误的假设。 - fuz

没错，某些情况下你可能仍然需要进行完整的、真实的比较。但是，如果你比较文件大小、md5sum、前几个字节和后几个字节或其他一些指标，你可能接近于不需要进行完整的比较。哪种指标最适合取决于你具体的数据情况，但我们可以尝试提出一些想法。 - pattivacek

@partickvacek 这是正确的。然而，这不是这个问题的重点。这个问题关注的是如何最小化实际执行昂贵（也就是深度）操作的情况。 - fuz

Answer 2

在平均情况下，对于一个包含n个元素的数组进行排序所需的理论最小比较次数是lg(n!)，大约为n lg n - n。如果你使用比较来对元素排序，平均情况下没有更好的方法。

在标准的O(n log n)比较排序算法中，归并排序需要的比较次数最少（大约为n lg n，而快速排序需要1.44 n lg n，堆排序需要n lg n + 2n），因此它可能是一个很好的起点算法。通常，归并排序比堆排序和快速排序慢，但这通常是在比较快速的情况下的假设。

如果你使用归并排序，我建议使用自然归并排序这样的自适应变种，以便如果数据大多已排序，则比较次数接近线性。

还有一些其他的选择。如果你确切地知道数据已经大部分排序了，那么你可以使用插入排序或标准变体的堆排序来尝试加速排序。或者你可以使用归并排序，但在n很小时使用最优排序网络作为基本情况。这可能会减少足够的比较次数，从而使性能提高明显。

希望这可以帮助您！

- templatetypedef

---

平均而言，在最佳情况下，基于比较的排序的时间复杂度是O(n log n)，而不是平均情况。 - Saeed Amiri

@SaeedAmiri- 你确定吗？比较排序算法的最佳情况运行时间可以达到O(n)。以已排序数组为例，考虑插入排序。n log n障碍只是说明平均情况不能比Omega(n log n)更好，而许多比较排序的最坏情况运行时间是O(n log n)，其中最好情况是O(n)。例如，smoothsort就是这种情况。 - templatetypedef

我看到我把我的评论写错了方向，对此感到抱歉（我本来想写最坏情况是Omega(n log n)，但我写反了！）顺便说一句，我的观点是障碍不关心平均值，而是关于运行时间，实际上可能平均值很重要，但比平均值更重要的是运行时间，而运行时间的度量是最坏情况（例如我们不说插入排序是O(n)，而是说是O(n^2)）。你在哪里看到障碍是关于平均值的？障碍是一个鸽巢原理，它说存在某些东西，从不谈论平均值。 - Saeed Amiri

@SaeedAmiri- 排序下限的标准证明只涉及最坏情况的运行时间，但是可以通过查看从根节点到任何叶节点的所有路径的平均长度来修改它以涉及平均情况的运行时间。您可以利用树的高度log（n！）这一事实来表明平均路径长度也必须至少为log（n！）。例如，此链接中给出了一个证明：http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf。希望这可以帮助您！ - templatetypedef

дҢ еЏҮд»Өзњ‹дёЂдё‹еә±е †жҺ’еғЏ(Weak Heapsort)пәЊе…¶жњЂеқЏжѓ…况下的жҮ”иңѓж¬Ұж•°дёғn log n + 0.1nгЂ‚иҮ¦з»†дүҰжЃҮиҮ·еЏ‚иЂѓhttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.2819&rep=rep1&type=pdfгЂ‚ - MicSim

Answer 3

一种名为Schwartzian transform的技术可以用于将任何排序问题简化为整数排序问题。它要求您对输入项中的每个应用函数f，其中f(x) < f(y)当且仅当x < y。请保留HTML标签。

---

（当我认为这个问题被标记为[python]时，给出Python方向的答案）

如果您可以定义一个函数f，使得当且仅当x < y时f(x) < f(y)，那么您可以使用以下方法进行排序：

sort(L, key=f)

Python保证对要排序的可迭代对象中的每个元素，最多只调用一次key函数。这为Schwartzian transform提供了支持。

Python 3不支持指定cmp函数，只支持key参数。此页面提供了一种简单的方法，可以将任何cmp函数转换为key函数。

- chepner

---

不知怎么的，我以为这是标记为“Python”的。然而，Schwartzian变换可以应用于任何语言。 - chepner

这在这里并不适用（见示例），但仍然有趣了解。 - fuz

你可以使用公理集合论的一些高级结果来证明这并不总是可能的。有些排序不能嵌入整数或实数中（例如，字符串的字典序）。 - templatetypedef

只有当字符串长度没有限制时才能这样做。 - chepner

Answer 4

有没有一种排序算法能够最小化对cmp(i,j)的调用次数？

编辑：啊，抱歉。有一些最小化比较次数的算法（如下），但我不知道是否有针对特定元素的算法。

如果存在expensive(i,j)，是否会允许更好的算法来尝试避免昂贵的比较操作？如果是，你能指出这样的算法吗？

据我所知，并没有这样的算法，但也许你可以在下面的论文中找到相关材料。

请给我提供此主题的进一步材料的指引。 《关于最佳和高效的原地合并》 《通过对称比较实现稳定的最小存储合并》 这段文本的翻译如下：

最优稳定归并算法（尽管此算法复杂度为 O(n log² n)）

实用原地归并排序算法

如果您实现了其中任何一种算法，将它们发布在这里可能对其他人也有用！:)

- user541686

---

这只是一个简单的比较排序算法，无法确定条件expensive(i,j) ∧ expensive(j,k) → expensive(i,k)是否可以用来避免昂贵的比较操作。 - jamesSampica

Answer 5

有一种排序算法可以最小化对cmp(i,j)的调用次数吗？

“合并插入”算法，D. Knuth在《计算机程序设计艺术》第3卷第5.3.1章中描述，使用的比其他基于比较的算法更少的比较。但仍需要O(N log N)个比较。

如果存在expensive(i,j)，是否会有更好的算法尝试避免昂贵的比较操作？如果是，你能指出这样的算法吗？

我认为现有的某些排序算法可以被修改以考虑expensive(i,j)谓词。让我们来看看其中最简单的——插入排序。维基百科上称其为二分插入排序的变体之一，只使用O(N log N)个比较。

它采用二分搜索确定插入新元素的正确位置。我们可以在每个二分搜索步骤后应用 expensive(i,j) 谓词来确定将插入元素与二分搜索步骤中找到的“middle”元素进行比较是否便宜。如果很昂贵，我们可以尝试“middle”元素的邻居，然后是它们的邻居等等。如果找不到便宜的比较，我们就返回到“middle”元素并执行昂贵的比较。

有几种可能的优化方法。如果谓词和/或便宜的比较不太便宜，我们可以早于所有其他可能性尝试将回滚到“middle”元素。此外，如果移动操作不能被视为非常便宜，我们可以使用一些顺序统计数据结构（如 Indexable skiplist）将插入成本降低到 O(N log N)。

这种修改后的插入排序对于数据移动需要 O(N log N) 时间，在最坏情况下需要 O(N²) 谓词计算和便宜的比较以及 O(N log N) 昂贵的比较。但更可能的是，只有 O(N log N) 谓词和便宜的比较以及 O(1) 昂贵的比较。

考虑一组可能很大的文件。在这个应用程序中，目标是在它们之间找到重复的文件。

如果唯一的目标是查找重复项，我认为排序（至少比较排序）是不必要的。您可以根据计算出的哈希值将文件分配到桶之间，该哈希值是从每个文件的前1兆字节的数据计算出来的。如果某个桶中有多个文件，则获取其他10、100、1000...兆字节。如果仍然在某个桶中有多个文件，则逐字节进行比较。实际上，此过程类似于基数排序。

- Evgeny Kluev

Answer 6

快速排序和归并排序是最快的排序算法，除非你有一些关于要排序的元素的额外信息。它们需要O(n log(n))次比较，其中n是数组的大小。数学上证明了任何通用排序算法都不能比这更有效率。

如果你想让过程更快，你可以考虑添加一些元数据来加速计算（除非你也很精确，否则无法更精确）。

如果你知道更强的条件，比如存在一个最大值和一个最小值，你可以使用更快的排序算法，比如基数排序或桶排序。

你可以在维基百科上查找所有提到的算法。

据我所知，你不能从昂贵的关系中获益。即使你知道了，你仍然需要执行这样的比较。正如我所说，你最好尝试缓存一些结果。

---

编辑

我花了一些时间思考，想出了一个稍微定制化的解决方案，我认为它将尽可能少地进行昂贵的比较，但完全忽略了总比较次数。它最多会进行 (n-m)*log(k) 次昂贵的比较，其中

• n 是输入向量的大小
• m 是易于相互比较的不同组件的数量
• k 是难以比较且具有连续排名的元素的最大数量。

这里是算法的描述。值得注意的是，除非 m 很大且 k 很小，否则它的性能将远远不如简单的归并排序。总运行时间为 O[n^4 + E(n-m)log(k)]，其中 E 是昂贵比较的成本（我假设 E >> n，以防止其被渐近符号抹去。那个 n^4 可能可以进一步减少，至少在平均情况下。

编辑

我发布的文件包含一些错误。在尝试它时，我也修复了它们（我忽略了insert_sorted函数的伪代码，但是想法是正确的）。我编写了一个Java程序，对整数向量进行排序，并按照您描述的方式添加延迟。即使我持怀疑态度，如果延迟显著（我使用1秒延迟来比较整数，这通常需要纳秒级别的执行时间），它实际上比归并排序更好。

- Giulio Franco

---

我可能错了，但平均时间复杂度应该是O(n log(n))，对吧？ 可能会更糟：O(n^2)，或者更好的O(n)。根据您的需求，可能有一种优化方法适用于快速排序。 - dyesdyes

@dyesdyes，对于非确定性输入，您无法将其_优化_为比nlog(n)更好的效果。 - jamesSampica

“Quicksort是最快的排序算法”这个说法并不完全适用。首先，Quicksort存在某些病态情况，其执行时间为*O(n²)，因此它可能不是最佳选择；其次，如果另一种算法比Quicksort的比较操作更便宜，即使该算法需要O(n³)*的时间，我也不会在意。这就是问题的关键所在。 - fuz

@Giulio说C语言可能会很大，但对于实际问题来说并不重要。这正是本案例的情况。 - fuz

快速排序和归并排序不是最优的比较排序算法。它们在渐近意义下是最优的，但这并不意味着它们可以证明地最小化比较次数。 - templatetypedef

Answer 7

大多数排序算法都试图在排序过程中尽可能减少比较的次数。

我的建议： 选择快速排序作为基本算法，并在必要时记住比较结果，以防再次比较同样的问题。这应该有助于你在快速排序的最坏情况O(N^2)下。请记住，这将使您使用O(N^2)的内存。

如果您真的很有冒险精神，可以尝试双轴快速排序。

- le-doude

Answer 8

需要记住的一点是，如果您不断地对列表进行排序并添加新元素，并且两个元素之间的比较保证永远不会改变，那么您可以对比较操作进行备忘录优化，这将导致性能提高。不幸的是，在大多数情况下，这种方法都不适用。

- Hderms

Answer 9

我们可以从另一个角度来看待您的问题，似乎您的问题与IO有关，那么您可以利用并行排序算法的优势。实际上，您可以运行许多线程来比较文件，然后使用最好的已知并行算法之一（如样本排序算法）对它们进行排序。

- Saeed Amiri

---

很好。你的意思是当我尝试同时访问两个文件时，我的硬盘会旋转得更快吗？请注意我在问题中写的内容：为了这个问题，请假设没有办法使cmp(i,j)更快。假设所有可能使cmp(i,j)更快的优化已经完成。 - fuz

@FUZxxl，非常不错啊，我没想到你能在你的硬盘驱动器上以更快的速度完成任务。你在我的回答中看到了什么？很明显有一些排序算法可以减少比较的次数，但是当你从IO加载数据到内存时，比较两个大数据所需的时间要多得多。所以最好的方法是并行获取数据。我并没有试图改进你的比较方法，而且明确提到了“看起来你的问题与IO有关”。我非常确定你没有尝试过这种并行方式，否则你就不会如此出色了。 - Saeed Amiri

如果数据量小到足以适应机器的RAM，那么我就不会遇到这些性能问题了。正如我上面所写的，实际排序所花费的时间是微不足道的。*cmp(i,j)*昂贵的情况恰好是那些我必须从硬盘中读取大量数据的情况（正如问题中所述，我无法优化掉）。现在，请告诉我并行化究竟如何帮助我。 - fuz

@FUZxxl，目前你正在执行串行操作，例如通过批量读取或其他方式读取数据，然后进行比较，接着读取下一部分，如此循环。但问题在于，在你处理 CPU 中的数据时，你也可以获取另一个数据。 - Saeed Amiri

处理数据可能只占用了0.1％的时间。同时读取其他数据也不会带来太多好处。 - fuz

@FUZxxl，这样可以提高运行时间0.1％，我认为如果您将就地合并排序更改为某些比较少的排序（如果有的话），则无法获得更好的结果。您应该考虑获取方式，或者可能是创造性的随机排序算法（与并行化相结合），以便您不需要获取整个文件，而是以高概率以良好格式进行排序。 - Saeed Amiri