performance - 当比较元素很昂贵时，我可以使用什么排序技术？

Question

问题

我有一个应用程序，我想对数组 a 的元素 a₀, a₁,... ,a_n-1。我有一个比较函数 cmp(i,j) 比较元素 a_i 和 a_j 和交换函数 swap(i,j)，交换元素 a_i 和 a_j 的数组。在应用程序中，cmp(i,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) 为真需要很长时间。 expensive(i,j) 很便宜，expensive(i,j) ∧ expensive(j,k) → expensive(i,k) 主要适用于我当前的应用程序。但这并不能保证。

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

• 我想要有关此主题的更多 Material 的指针。

例子

这是一个与我的应用程序并不完全不同的示例。

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

当然，大量数据的读取器是昂贵的，因此，例如，可以只读取每个文件的第一个兆字节并计算该数据的哈希函数。如果文件比较相等，则哈希值也相等，但反过来可能不成立。两个大文件在末尾附近只能相差一个字节。

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

Answer 1

我会尽力回答每个问题。

• 是否有一种排序算法可以最大限度地减少对 cmp(i,j) 的调用次数？

传统的排序方法可能会有一些变化，但总的来说，对列表进行排序所需的最少比较次数存在数学限制，大多数算法都利用了这一点，因为比较通常并不便宜。您可以尝试按其他方式排序，或者尝试使用可能更接近真实解决方案的更快的快捷方式。

• expensive(i,j) 的存在是否允许更好的算法来避免昂贵的比较操作？如果是，你能告诉我这样的算法吗？

我认为您无法避免至少进行最少数量比较的必要性，但您可以更改比较的内容。如果您可以比较数据的哈希值或子集而不是整个数据，那肯定会有所帮助。任何可以简化比较操作的方法都会产生很大的不同，但在不知道数据的具体细节的情况下，很难提出具体的解决方案。

• 我想要有关此主题的更多 Material 的指示。

检查这些:

• 显然 Donald Knuth 的计算机编程艺术，第 3 卷有一节是关于这个主题的，但我手头没有副本。
• Wikipedia当然对此事有所了解。
• Sorting an array with minimal number of comparisons
• How do I figure out the minimum number of swaps to sort a list in-place?
• Limitations of comparison based sorting techniques