在大学念书期间,我和班长一起参加了图书馆兼职的校园招聘,岗位只有两个,幸运的是两人一起被录用了。后来,图书馆的老师说,因为我们是同一专业的,这个两人岗位交给我们,工作上沟通起来也顺利。我们的任务就是整理书架,把馆内的藏书放到对应的区域。这些图书当然不能乱放,我们按照索引号一行一行地摆放。有时候,部分书籍难免混乱,通常我们会巡视,看到两本书先后次序不对,那就调换过来,一直走到书架的最后端。接着再回到书架最前端,多巡视几次。或者,用例外一种相对轻松的办法(不用一直跑),把混乱的那堆书统统撤下,把取下来的第一本书放在空出来的中间,第二本书和第一本书比较,决定是放在左边还是右边,放第三本书的时候浏览书架,放到合适的位置。不断重复这个过程,直到所有的书都放上了书架。这两种方法在计算机科学中,分别被称呼为“冒泡排序”和“插入排序”,他们所花费的时间和书籍的个数n呈现平方关系。


在我们的电子邮箱中有大量的邮件,他们会依据收件、发送时间被排列得整整齐齐;微信上最近相互问候的朋友在条目最顶端的位置;出门在外,在高德地图中输入“地铁”,附近的地铁站会默认依据地理距离由近到远地展示出来;在google上搜索我们想要的信息,搜索引擎会把包含关键词的网页进行有效排序,关系越密切的网页越靠前。大量的信息要被整理好,理出头绪,从本质上讲都是在排序。
要被整理的元素个数越多,问题的难度就会越大。整理2次3本书所花费的时间比整理1次6本书所花费的时间少得多。人们迫切想要找到更加高效的方法,完成排序任务。然而,在很长的一段时间里,我们都无法突破 n^2 的束缚,这个问题影响着社会生产力,人类想要获得更加幸福的生活,就必须解开 n^2 的魔咒。


历史进程需要英雄来推动,20世纪,匈牙利出生了一名数学天才,他的名字叫做约翰·冯·诺依曼(John von Neumann)。冯·诺依曼从小表现出极高的数学天赋,相传他6岁会8位数心算,8岁掌握了微积分。在成年之后,他的才华受到了数学界的瞩目。后来,在老师的推荐下,冯·诺依曼前往了美国发展。在计算机领域,他提出了重要的“冯诺依曼结构”和二进制编码,以及编程基础理论 —— 计算机需要存储程序。
1945年,冯·诺依曼在存储计算机上编写了一个比较程序。用整理扑克牌进行说明,比较两张牌非常简单,一次比较后就能确定好位置。如果两叠牌都整理好了,那么我们就很容易把这四张牌整理成排序好的一叠牌。操作细节是,再构造一个新的牌堆,一开始没有牌,比较整理好的两堆牌中最上面的两张,按照大小关系取其中一个放到新牌堆中,接着重复这个过程。直到还剩下一堆牌,剩余的牌加入新牌堆中即可。这类合并的过程比起传统的比较排序高效多了。这个计算机科学中的传奇算法被世人称为“合并排序”(merge sort)


这个新的排序方法有多么重要呢?有人曾这样评价它,“合并排序在排序历史中的重要地位和排序在计算历史中的重要地位旗鼓相当。” 合并排序比起传统的冒泡、插入排序非常高效,因为每次合并之后,整理好的元素就是原来的2倍,每次合并比较次数是元素总个数,所以产生了新的时间 – 规模关系式:

我们用图像来对比生产力的提高(时间的锐减):

p1 = Plot[n^2, {n, 0, 50}, PlotLabels -> "Expressions"]
p2 = Plot[n*Log2[n], {n, 0, 50}, PlotLabels -> "Expressions"]
Show[p1, p2]


emmm,合并排序的源码也贴出来吧,缅怀“计算机之父”!因为这位科学巨人的贡献,才有了如今计算机行业的繁荣。

def merge(a, b):
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

def sort(_list):
    if len(_list) == 0 or len(_list) == 1:
        return _list
    else:
        middle = len(_list)//2
        a = sort(_list[:middle])
        b = sort(_list[middle:])
        return merge(a, b)

0 0 vote
Article Rating
Subscribe
Notify of
guest
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] 更多有关冯·诺依曼的文章:冯·诺依曼: 用分治算法打破平方时间的诅咒 […]

A prohibited operation
1
0
Would love your thoughts, please comment.x
()
x