可中断的原地排序算法

Question

可中断的原地排序算法

calgorithmsortingquicksortheapsort

13

我需要用C语言编写一个排序程序，并希望能够原地排序以节省磁盘空间。这是有价值的数据，因此我需要确保如果进程被中断（使用ctrl-c），文件不会损坏。我可以保证机器的电源线不会被拔掉。

额外的细节：文件大小约为40GB，每个记录为128位，机器为64位，操作系统为POSIX。

您有什么关于完成此任务的提示或一般性说明吗？

谢谢！

澄清一下：我预计用户将想要通过ctrl-c来中断进程。在这种情况下，我希望优雅地退出并确保数据是安全的。因此，这个问题是关于如何处理中断和选择能够快速完成的排序算法的。

后续（两年后）：仅供纪念，我已经安装了SIGINT处理程序，效果很好。这不能保护我免受停电的风险，但这是我可以处理的风险。代码位于https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.c和https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

- William Entriken

我认为你必须问哪个更重要？空间还是进程是否应该被中断。如果您需要确保文件未损坏，您将需要以某种方式跟踪其进度和先前状态 - 这将占用比文件更多的空间。 - Ryan Bennett

为了安全起见，请先复制一份并对其进行排序。我无法想象文件系统会因另外40GB的存储而出现问题。 - Martin York

@Martin：你的想象力和我的不一样。我主要的硬盘上目前还有36.4GB的可用空间。 - Steve Jessop

@Martin York：我目前正在使用一台150G的机器，而且它在未来一年内不会被替换。企业数据存储并不是跑到Costco或Best Buy买一个1TB硬盘的问题。企业级别的存储设备价格惊人地昂贵。话虽如此，如果这是重要数据，为了保持完整性再花费40G是值得的。 - David Thornley

@Martin：谁说这个程序只会在程序员控制的机器上运行？如果我是你的客户，你会给我买那个价值100美元的驱动器吗？还是我要使用你的竞争对手的产品，只需要我有2GB的可用磁盘空间并执行外部合并排序？ - Steve Jessop

显示剩余2条评论

6个回答

5

保护程序不被ctrl-c中断的部分相当简单：signal(SIGINT, SIG_IGN);。

至于排序本身，归并排序通常适用于外部排序。基本思路是尽可能多地将记录读入内存，对其进行排序，然后将其写回磁盘。最简单的处理方式是将每个运行写入单独的磁盘文件中。然后将它们合并在一起--从每个运行中读取第一个记录到内存中，并将其中最小的记录写回原始文件；从提供该记录的运行中读取另一条记录，并重复此过程直到完成。最后一个阶段是唯一修改原始文件的时间，因此这是您需要确保防止中断等情况的唯一时间。

另一个可能性是使用选择排序。坏处是排序本身相当慢。好处是几乎可以编写以使其免受任何干扰，而且不需要使用太多额外的空间。总体思路非常简单：查找文件中最小的记录，并将其交换到第一个位置。然后查找剩余记录中最小的记录，并将其交换到第二个位置，依此类推直到完成。这种方法的好处是日志记录很简单：在执行交换之前，记录要交换的两个记录的值。由于排序从第一条记录到最后一条记录运行，因此您需要跟踪的唯一其他内容是任何给定时间已经排序的记录数。

- Jerry Coffin

1

+1 - 不符合原地排序的要求，但在我看来这是最明智的方法。在对块进行排序时不会修改主文件，如果合并过程崩溃，您将拥有已排序的块文件作为备份。 - snemarch

1

不要忽略 SIGINT 信号，而是在交换操作期间阻塞它（以及所有其他信号），但定期解除阻塞，以便可以处理在阻塞期间到达的挂起信号。 - R.. GitHub STOP HELPING ICE

5

安装一个处理程序来处理SIGINT，它只需设置一个“进程应该很快退出”的标志。

在排序过程中，在交换两个记录（或每N次交换后）之后检查该标志。如果该标志被设置，则退出。

- caf

这对我来说听起来是最好的解决方案。其他一些建议给我的印象是，如果不在恰当的时间按下Ctrl-C，则应该忽略它，这对用户体验来说似乎是不好的。 - Jeffrey L Whitledge

这看起来像是赢家。它似乎适用于快速排序和堆排序。谢谢！ - William Entriken

它无法保护您的数据免受kill -9或电源故障的影响。 - Zan Lynx

3

使用堆排序，并在每次交换操作期间防止中断（例如，阻塞信号）。

- R.. GitHub STOP HELPING ICE

是的。简单易懂。同时更改内存，然后一次性写入/刷新所有内容（在此部分中阻止信号）。 - Matt Joiner

堆排序需要在整个文件中进行操作，这可能对那些无法全部适应物理内存的内容不利。 - David Thornley

另一方面，如果文件像您的情况一样巨大，那么大O符号而不是io缓存未命中的常数因子将占主导地位。堆排序是唯一具有优于二次方大O符号的原地排序算法。 - R.. GitHub STOP HELPING ICE

0

备份您计划更改的内容。然后设置一个标志，标记成功排序。如果一切正常，则保留结果，否则恢复备份。

- Victor Hurdugaci

-1 不符合问题的原地标准，问题明确说明有一个巨大的数据集，可能没有足够的空间来备份它。 - R.. GitHub STOP HELPING ICE

R：你不需要保存整个文件，只需保存在排序中使用的小片段。我从未说过整个文件必须备份。 - Victor Hurdugaci

-1

假设使用的是64位操作系统（虽然您说它是一台64位机器，但仍可能运行32位操作系统），您可以使用mmap将文件映射到数组上，然后在数组上使用qsort。

添加一个SIGINT处理程序来调用msync和munmap，以允许应用程序在不丢失数据的情况下响应Ctrl-C。

- Spaceghost

1

如果一个信号中断了qsort，则数据在qsort完成之前处于不确定状态。绝对没有办法使用系统的qsort来满足OP的需求。 - R.. GitHub STOP HELPING ICE

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Jessop · Accepted Answer

Jerry说得对，如果你只是担心Ctrl-C，那么你可以暂时忽略SIGINT信号。如果你想对进程死亡进行全面的保护，你需要一些形式的最小日志记录。为了交换两个元素:

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

2)将A复制到临时空间，记录已经完成此操作，然后执行刷新操作。

3)将B复制到A位置，然后在临时空间记录您已完成此操作，再次刷新。

4)从临时空间复制到B位置。

5)删除记录。

这对于所有实际目的而言都是O(1)额外空间的，在大多数定义下仍然被视为就地排序。理论上，如果n可以任意大，则记录索引的时间复杂度为O(log n)：实际上，对数值非常小，合理的硬件/运行时间将其上限限制在64个左右。

无论何时我说“刷新”，我指的是提交足够的更改。有时，基本的刷新操作只会在进程内部刷新缓冲区，但它并不会将物理介质同步，因为它不能完全刷新所有OS/设备驱动程序/硬件级别的缓冲区。当你只担心进程死亡时，这足够了，但如果你担心介质突然卸载，那么你必须刷新到驱动程序之后。如果你担心断电，你必须同步硬件，但你没有。如果你有UPS或者认为停电很少发生，你可以不用担心丢失数据。

在启动时，检查临时空间中是否存在任何“正在交换中”的记录。如果您找到一个，就计算出已经完成的比例，从那里开始完成交换以使数据回到可用状态。然后重新开始排序。

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

杰瑞也正确指出，对于大多数实际目的来说，真正的原地排序太困难和慢了。如果你可以抽出原始文件大小的某些线性部分作为缓存空间，那么用归并排序会更好。

根据你的澄清，即使使用原位排序，你也不需要执行任何刷新操作。你需要在内存中具有相同功能的缓存空间，你的SIGINT处理程序可以访问它，以便在退出之前将数据安全保存，而不是在异常退出后在启动时恢复，并且你需要以信号安全的方式访问该内存（技术上意味着使用sig_atomic_t标志已进行的更改）。即使如此，与其使用真正的原位排序，你可能还是更适合使用归并排序。