Wil*_*ken 13 c sorting algorithm quicksort heapsort
我需要在C中编写一个排序程序,如果文件可以在适当的位置排序以节省磁盘空间,那将是很好的.数据很有价值,所以我需要确保如果进程被中断(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
Ste*_*sop 12
Jerry是对的,如果只是你担心的Ctrl-C,你可以一次忽略SIGINT.如果你想要证明一般的过程死亡,你需要某种最小的日记.为了交换两个元素:
1)将记录添加到文件末尾的控制结构或单独的文件中,指示要交换的文件的哪两个元素,A和B.
2)将A复制到临时空间,记录您已经完成的,冲洗.
3)将A复制到A上,然后在您已经完成的临时空间中进行记录,刷新
4)从B空间复制B.
5)删除记录.
对于所有实际目的而言,这是O(1)额外空间,因此在大多数定义下仍然适用于原位.理论上,如果n可以任意大,则索引是O(log n):实际上它是一个非常小的log n,合理的硬件/运行时间将其限制在64以上.
在所有情况下,当我说"刷新"时,我的意思是提交"足够远"的变化.有时您的基本刷新操作仅刷新进程内的缓冲区,但它实际上并不同步物理介质,因为它不会在OS /设备驱动程序/硬件级别上一直刷新缓冲区.当你担心的只是过程死亡时,这就足够了,但是如果你担心媒体的突然失误,那么你必须冲过司机.如果你担心电源故障,你必须同步硬件,但你不是.使用UPS或者如果您认为断电是如此罕见,您不介意丢失数据,那很好.
在启动时,检查临时空间以查找任何"交换进度"记录.如果你找到一个,找出你得到多远,并从那里完成交换,以使数据恢复到健全的状态.然后重新开始你的排序.
显然这里存在一个性能问题,因为你的记录写入量是以前的两倍,而刷新/同步可能会非常昂贵.在实践中,您的就地排序可能有一些复合移动操作,涉及许多交换,但您可以优化以避免每个元素都到达临时空间.您只需要确保在覆盖任何数据之前,您可以在某处保存一份安全副本,并记录该副本的位置,以便将文件恢复到其中只包含每个元素的一个副本的状态.
杰里也是对的,真正的就地排序对于大多数实际目的而言太难和慢.如果您可以将原始文件大小的某些线性分数作为临时空间,那么使用合并排序可以获得更好的时间.
根据您的说明,即使使用就地排序,也不需要任何刷新操作.您需要在内存中以相同方式工作的临时空间,并且您的SIGINT处理程序可以访问以便在退出之前获得数据安全,而不是在异常退出后在启动时恢复,并且您需要在信号中访问该内存 -安全方式(技术上意味着使用a sig_atomic_t来标记已经进行了哪些更改).即便如此,使用mergesort比使用真正的就地排序更好.
防止ctrl-c的部分非常简单:signal(SIGINT, SIG_IGN);.
就排序本身而言,合并排序通常适用于外部排序.基本思想是尽可能多地将记录读入内存,对它们进行排序,然后将它们写回磁盘.到目前为止,处理此问题的最简单方法是将每个运行写入磁盘上的单独文件.然后将它们合并在一起 - 将每次运行的第一条记录读入内存,并将最小的记录写入原始文件; 从提供该记录的运行中读取另一条记录,并重复完成.最后一个阶段是您修改原始文件的唯一时间,因此这是您真正需要确保中断等的唯一时间.
另一种可能性是使用选择排序.不好的一点是排序本身很慢.好的一点是,编写它几乎可以生存,而不需要占用额外的空间.一般的想法很简单:找到文件中的最小记录,并将其交换到第一个位置.然后找到剩下的最小记录,并将其交换到第二个点,依此类推,直到完成.这样做的好处是日记是微不足道的:在进行交换之前,你会记录你要交换的两个记录的值.由于排序从第一个记录到最后一个记录,因此您需要跟踪的唯一事项是在任何给定时间已经排序了多少记录.