c - 可中断就地排序算法

Question

我需要用 C 编写一个排序程序，如果文件可以就地排序以节省磁盘空间，那就太好了。数据很有值(value)，所以我需要确保如果进程中断 (ctrl-c)，文件不会损坏。我可以保证机器上的电源线不会被拉扯。

额外细节:文件约为 40GB，记录为 128 位，机器为 64 位，操作系统为 POSIX

关于完成此操作的任何提示或一般说明？

谢谢!

澄清一下:我预计用户会想要 ctrl-c 这个过程。在这种情况下，我想优雅地退出并确保数据安全。所以这个问题是关于处理中断和选择一种可以在需要时快速结束的排序算法。

跟进(2 年后): 为了后代，我安装了 SIGINT 处理程序，它运行良好。这不能保护我免受电源故障的影响，但这是我可以处理的风险。代码在 https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.c和 https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

Answer 1

Jerry 是对的，如果您只是担心 Ctrl-C，您可以一次忽略 SIGINT 一段时间。如果你想证明一般情况下没有进程死亡，你需要某种最小的日志记录。为了交换两个元素:

1) 在文件末尾或单独的文件中向控制结构添加一条记录，指示要交换文件的哪两个元素，A 和 B。

2) 将A复制到暂存空间，记录你已经这样做了，刷新。

3) 将B复制到A上，然后在暂存空间中记录你所做的，刷新

4)从B上的暂存空间复制。

5) 删除记录。

对于所有实际用途来说，这是 O(1) 的额外空间，因此在大多数定义下仍然算作就地。理论上，如果 n 可以任意大，则记录索引的时间复杂度为 O(log n):实际上它是一个非常小的 log n，并且合理的硬件/运行时间将其限制在 64 以上。

在所有情况下，当我说“刷新”时，我的意思是提交“足够远”的更改。有时，您的基本刷新操作仅刷新进程内的缓冲区，但实际上并没有同步物理介质，因为它不会在操作系统/设备驱动程序/硬件级别上一直刷新缓冲区。当您担心的只是进程死亡时，这就足够了，但如果您担心媒体突然卸载，那么您就必须冲过驱动程序。如果您担心电源故障，则必须同步硬件，但事实并非如此。使用 UPS，或者如果您认为停电非常罕见，您不介意丢失数据，那很好。

启动时，检查暂存空间是否有任何“正在进行的交换”记录。如果你找到了一个，算出你得到了多远，并从那里完成交换以使数据恢复到良好状态。然后重新开始排序。

显然这里存在性能问题，因为您正在执行两倍于以前的记录写入，并且刷新/同步可能非常昂贵。在实践中，您的就地排序可能有一些复合移动操作，涉及许多交换，但您可以对其进行优化以避免每个元素都进入暂存空间。您只需确保在覆盖任何数据之前，您在某个地方有一份安全的副本，并记录该副本应该去哪里，以便让您的文件恢复到一个状态，其中它只包含每个元素的一个副本。

Jerry 也说对了，对于大多数实际用途而言，真正的就地排序太困难且太慢。如果您可以腾出原始文件大小的一些线性部分作为暂存空间，那么使用合并排序会更好一些。

根据您的说明，即使使用就地排序，您也不需要任何刷新操作。您需要内存中以相同方式工作的暂存空间，并且您的 SIGINT 处理程序可以访问该空间，以便在退出之前确保数据安全，而不是在之后启动时恢复异常退出，并且您需要以信号安全的方式访问该内存(从技术上讲，这意味着使用 sig_atomic_t 来标记已进行的更改)。即便如此，与真正的就地排序相比，合并排序可能会更好。