25

问题

我有一个应用程序，我想对元素数组a进行排序a 0， a 1，...，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)的调用次数？

  • 如果调用cmp(i,j)需要很长时间，则可以在我的应用程序中编写一个为 true的谓词昂贵（i，j） 。昂贵的(i,j)便宜且昂贵的(i,j) ∧ 昂贵的(j,k) → 昂贵的(i,k)主要适用于我当前的应用程序。但是，这并不能保证。

    昂贵（i，j）的存在是否允许更好的算法试图避免昂贵的比较操作？如果是的话，你能指出我这样的算法吗？

  • 我想要关于这个主题的更多材料的指针。

例子

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

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

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

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

4

9 回答 9

9

我会尽量回答每个问题。

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

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

  • 昂贵（i，j）的存在是否允许更好的算法试图避免昂贵的比较操作？如果是的话，你能指出我这样的算法吗？

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

  • 我想要关于这个主题的更多材料的指针。

检查这些：

于 2013-08-22T13:25:39.020 回答
7

对一个包含 n 个元素的数组进行平均排序所需的理论最小比较次数是 lg (n!)，大约是 n lg n - n。如果您使用比较来对元素进行排序，那么平均而言没有比这更好的方法了。

在基于标准 O(n log n) 比较的排序算法中，mergesort 进行的比较次数最少（大约 n lg n，而快速排序大约为 1.44 n lg n，堆排序大约为 n lg n + 2n），所以这可能是一个很好的算法，可以用作起点。通常，mergesort 比 heapsort 和 quicksort 慢，但这通常是在比较快速的假设下。

如果您确实使用归并排序，我建议您使用归并排序的自适应变体，例如自然归并排序，这样如果数据大部分是排序的，则比较次数更接近线性。

还有一些其他选项可用。如果您知道数据已经大部分排序，您可以使用插入排序或堆排序的标准变体来尝试加速排序。或者，您可以使用归并排序，但在 n 较小时使用最佳排序网络作为基本情况。这可能会减少足够的比较，从而显着提升性能。

希望这可以帮助！

于 2013-08-22T17:06:17.293 回答
4

一种称为Schwartzian 变换的技术可用于将任何排序问题简化为整数排序问题。它要求您对f每个输入项应用一个函数，其中f(x) < f(y)当且仅当x < y.

（面向 Python 的答案，当我认为问题被标记时[python]）

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

sort(L, key=f)

Python 保证key对于您正在排序的迭代的每个元素最多调用一次。这为Schwartzian 变换提供了支持。

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

于 2013-08-22T13:25:18.750 回答
2

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

编辑：啊，对不起。有一些算法可以最大限度地减少比较次数（如下），但对于特定元素，我不知道。

昂贵（i，j）的存在是否允许更好的算法试图避免昂贵的比较操作？如果是的话，你能指出我这样的算法吗？

我不知道，但也许你会在下面的这些论文中找到它。

我想要关于这个主题的更多材料的指针。

论优化和高效的就地合并

通过对称比较实现稳定的最小存储合并

最优稳定合并（这似乎是 O(n log2n) 虽然

实用的就地合并排序

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

于 2013-08-22T18:06:30.830 回答
1

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

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

昂贵（i，j）的存在是否允许更好的算法试图避免昂贵的比较操作？如果是的话，你能指出我这样的算法吗？

我认为一些现有的排序算法可能会被修改以考虑expensive(i,j)谓词。让我们采用其中最简单的一种——插入排序。它的一种变体，在维基百科中被命名为二元插入排序，只使用 O(N log N) 比较。

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

有几种可能的优化。如果谓词和/或廉价比较不是那么便宜，我们可以在尝试所有其他可能性之前回滚到“中间”元素。此外，如果不能认为移动操作非常便宜，我们可以使用一些订单统计数据结构（如Indexable skiplist）将插入成本降低到 O(N log N)。

这种修改后的插入排序需要 O(N log N) 时间来进行数据移动，O(N 2 ) 谓词计算和廉价比较，在最坏的情况下需要 O(N log N) 昂贵比较。但更有可能只有 O(N log N) 谓词和廉价比较和 O(1) 昂贵比较。

考虑一组可能很大的文件。在此应用程序中，目标是在其中找到重复的文件。

如果唯一的目标是查找重复项，我认为排序（至少是比较排序）是不必要的。您可以根据为每个文件的第一兆字节数据计算的哈希值在存储桶之间分配文件。如果某个桶中有多个文件，则取其他 10、100、1000、... 兆字节。如果某个存储桶中仍有多个文件，请逐字节比较它们。实际上这个过程类似于基数排序。

于 2013-08-23T09:55:15.553 回答
0

快速排序和归并排序是最快的排序算法，除非您有一些关于要排序的元素的附加信息。他们将需要 O(n log(n)) 比较，其中 n 是数组的大小。数学证明，任何通用排序算法都不会比这更有效。

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

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

您可以在 wikipedia 上查找所有提到的算法。

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

编辑

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

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

这是算法的描述。毫无意义，它的性能将比简单的归并排序差得多，除非 m 很大而 k 很小。总运行时间为 O[n^4 + E(nm)log(k)]，其中 E 是昂贵比较的成本（我假设 E >> n，以防止它从渐近符号中消失。至少在平均情况下，这 n^4 可能会进一步减少。

编辑

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

于 2013-08-22T13:24:06.933 回答
0

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

于 2013-08-22T17:59:46.787 回答
0

大多数排序算法都尝试在排序过程中尽量减少比较量。

我的建议：选择快速排序作为基本算法并记住比较结果，以防你碰巧再次比较相同的问题。这应该可以帮助您解决 O(N^2) 最坏的快速排序情况。请记住，这将使您使用 O(N^2) 内存。

现在，如果您真的很喜欢冒险，您可以尝试 Dual-Pivot 快速排序。

于 2013-08-22T13:24:58.953 回答
0

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

于 2013-08-23T10:26:35.817 回答