( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230624{main}( ).../view.php:0
20.0001231368include( '/var/www/html/head.php' ).../view.php:2
30.0010250728isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(22)-并行排序

小学计算思维课程(22)-并行排序

小学计算思维课程(22)-并行排序

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com


第二十二课:并行排序

众所周知计算机的运行速度非常快,现在普通的家用计算机每秒钟也可以计算几千万次加法。但对于某些问题,比如气象预报、石油勘探等,需要处理的数据将非常非常多。如果只使用一台计算机进行处理,将需要花费很多时间才能处理完成。因此,如何让很多台计算机并行的处理数据是计算机科学家们研究的重要课题之一。今天学习的“并行排序”就是其中的一个应用。

对于排序来说,提高速度的途径之一是让多台计算机同时进行比较。然而让多台计算机或者多个处理器同时协调的工作并不容易,需要我们设计一个精巧的排序网络。请看下面这个网络,它可以一次对6个数进行排序:

准备:

可以在地上用粉笔画出排序网络,然后找5个朋友一起玩,每个人代表一个数字。也可以把网络画在棋盘上,用6个数字棋子来玩。

活动:

等待排序的数字开始被放在左侧的6个框中(随机放),每一步将它们沿着箭头移动到右侧的圆圈中(称为“处理节点”),处理节点负责比较两个数字的大小,较小的数字沿向上的箭头移动,较大的数字沿向下的箭头移动。

问题:

1.试试将数字重新打乱再排一次,是否总能排好序?

2.数字穿过排序网络一共需要移动多少步?

3.如果让较小的数字向下移动、较大的数向上移动会发生什么?

4.你能设计一个将3个数字排序的网络吗(每个节点只比较2个数)?

从图中看,第一轮比较时,有3个处理节点同时进行比较,这样一共进行了5轮比较,6个数字就被排序完成。可见借助排序网络比前几节课的排序算法快的多,因为它可同时进行3次比较,理论上可以比一次只能进行一次比较的系统快2倍。排序网络的设计非常重要,下面两个不同的网络对4个数据进行排序,是否正确?哪一个更快?为什么?

想一想下面这个排序网络在做什么运算?( 表示此路不通,这个数字被丢弃。)

在我们的生活中,也有很多事情可以通过并行的方法来加速,想一想下面的问题:

1.雇更多的人用更多的铁锹能将一个9米长的排水渠挖得理快吗?

2.雇更多的人用更多的铁锹能将一个9米深的井挖的更深吗?

3.做一顿饭的过程中哪些步骤可以并行操作,哪些不能?

4.洗衣服的过程中哪些步骤能并行操作,哪些不能?

一般来说,并行操作能让很多事情做的更快,但有些却不能,因为你需要先完成这一步才能开始下一步。像排序这样的工作就可以依靠排序网络来并行工作,但是设计对100个数的排序网络就是一件很困难的事。因为我们需要测试这个排序网络工作是否正确,而6个输入的排序网络的输入可能就有6×5×4×3×2×1=720种(应用乘法原理),只有逐一测试这720种可能才能确保排序网络工作正确。不过幸运的是,计算机科学家已经可以用数学证明的方法来证明这种排序网络可以正常工作,不需要我们测试几百万次。