1700495080
1700495081
据我的经验,书目号在3500至3600之间的书很多,因此我首先找3500以下的书,先粗排,再细排。等3500以下的书都排好之后,我知道3500以上的书(也就是3500至3599这些书)是个大头,所以我想把这些书单独排好序。如果这些书的数量太多,我可能会进一步细分,分成3510-3519、3520-3529、3530-3539等。
1700495082
1700495083
乔丹总是把25本左右的书编成一组,全部排好序之后,装到小车上。排序的时候,他使用的确实是插入排序法。他精心想出来的办法是一种桶排序法。他事先就知道各种书目号对应的图书数量,因此他清楚应该如何选桶。结果,这个办法取得了非常好的效果。
1700495084
1700495085
1700495086
1700495087
1700495089
算法之美:指导工作与生活的算法 排序是搜索的准备工作
1700495090
1700495091
掌握了这些排序算法,你下一次整理书架时就应该能派上用场。同奥巴马一样,你也会知道不能使用冒泡排序法。好的办法(得到图书馆工作人员和机器的共同认证)是使用桶排序,等到将排序对象分成足够小的组之后,再使用插入排序,或者干脆举办比萨派对,使用合并排序。
1700495092
1700495093
但是,如果你邀请计算机科学家帮助你完成这项工作,他们询问的第一个问题应该是:你到底为什么要整理这些图书?
1700495094
1700495095
老师经常告诉那些本科生,计算机科学研究的就是如何取舍的问题。在前面讲到观察与行动以及探索与利用之间的矛盾时,就已经讨论过这个观点。而排序与搜索之间的取舍是最重要的取舍问题之一,其基本原理是:人们投入精力为物品排序是一种先发制人的措施,目的是保证以后无须在搜索上投入精力。平衡点应该如何确定,取决于当时情况的具体参数,但是,如果认为排序的价值仅仅是为未来的搜索提供支持,那么你会有一个令人吃惊的发现:
1700495096
1700495097
混乱无序也无伤大雅!
1700495098
1700495099
如果你从来不在某些物品中搜索某个目标,那么为这些物品排序就纯粹是一种浪费。如果你从来不为某些物品排序,那么你在其中搜索的效率就会很低。
1700495100
1700495101
因此,摆在我们面前的问题已经变成如何提前预估未来的用途。
1700495102
1700495103
谷歌等互联网搜索引擎是排序带来的一个典型益处。很难想象,谷歌可以利用你输入的搜索词,在不到半秒的时间内搜索整个互联网。事实上,谷歌做不到,不过它也无须这样做。如果你是谷歌,你几乎可以肯定以下3点:(1)你的数据会被搜索;(2)它不仅会被搜索,而且会被多次搜索;(3)与搜索所需时间相比,排序所需时间“价值较低”。(这里,排序是由机器提前完成的,排序结果暂时无用;搜索是由用户完成的,而用户的时间非常宝贵。)所有这些因素都倾向于预先排序,而谷歌和其他搜索引擎也正是这样做的。
1700495104
1700495105
因此,你是否应该整理你的书架呢?大多数家庭并不具备支持整理书架的任何条件。我们几乎不会在书架上的藏书中搜索某个书名,因此无序搜索的成本非常低:任何一本书,只要我们知道它的大致位置,就可以快速地找到它。在井然有序的书架上找到一本书或许需要2秒钟,而在一个胡乱堆放的书架上找到一本书则可能需要10秒钟,但是两者之间并不存在难以接受的差距。我们因为迫切需要某本书,而宁愿预先花几个小时时间书架,为将来再找它省下几秒钟,这种情况几乎不会发生。此外,我们的双眼可以快速搜索,而双手排序的速度却非常慢。
1700495106
1700495107
结论很明确:整理书架与在书架上浏览一遍相比,前者需要更多的时间和精力。
1700495108
1700495109
你可能不会每天都关注乱七八糟的书架,但是电子邮件的收件箱绝对是搜索轻松击败排序的另一个舞台。人工将电子信息归档到文件夹中所花费的时间与在现实世界中纸质文件归档所需的时间差不多,但是电子邮件的搜索速度要比纸质邮件高得多。随着搜索成本的下降,排序的价值也会随之降低。
1700495110
1700495111
IBM的研究科学家、加州大学圣克鲁兹分校教授史蒂夫·惠特克是研究人们处理电子邮件方式的知名专家之一。近20年来,惠特克一直在研究人们是如何管理个人信息的。(1996年,他写了一篇关于“电子邮件过载”的论文,当时很多人甚至还没有电子邮箱。)2011年,惠特克领导了一项关于电子邮件用户搜索和排序习惯的研究,其研究结果发表在一篇名为“我整理电子邮件是一种浪费时间的行为吗?”的文章中。我在这里来个剧透吧:结论不仅是肯定,而且是非常肯定。惠塔克指出:“这是一种经验,同时也是一种体验。在采访中谈论这些邮件整理问题时,他们告诉我,他们通常会讨论这个问题,并且认为这件事浪费了他们大量时间。”
1700495112
1700495113
计算机科学表明,混乱的危害和秩序的危害是可以量化的,他们的成本都可以用时间这个“货币”来衡量。杂乱无序可能会被认为是一种拖延的行为——把责任推给未来的自己,而且还要连本带息偿还我们不愿意提前支付的债务。但是,详细情况还要更加微妙。有时,混乱不仅仅是轻松的选择,还是一个最优选择。
1700495114
1700495115
1700495116
1700495117
1700495119
算法之美:指导工作与生活的算法 排序与体育
1700495120
1700495121
搜索与排序的取舍问题表明混乱状况有时反而更加有效。不过,节省时间不是排序的唯一原因,有时秩序本身就是我们追求的目标。最清楚这一点的非运动场莫属。
1700495122
1700495123
1883年,查尔斯·路特维奇·道奇森对英国草地网球的状况产生了令人难以置信的强烈情怀。他解释说:
1700495124
1700495125
不久前,我去观看草地网球锦标赛,一位十分沮丧的运动员引起了我对球赛目前采用的名次确定方法的注意。这位运动员在比赛中早早落败,因此彻底失去了获得奖牌的机会。令他感到屈辱的是,获得第二名的是他知道的一名远不如自己的运动员。
1700495126
1700495127
普通观众可能会把这种“哀叹”归咎于失败的痛苦,但道奇森并不是一个同情心泛滥的人,他是牛津大学数学系讲师,因此,在听到运动员的抱怨之后,他决定对体育赛事展开深入调查。
1700495128
1700495129
道奇森不仅仅是一个数学家(其实他几乎不记得自己是从事数学研究的)。现在,反而是他的笔名——刘易斯·卡罗尔更加广为人知。他以这个笔名写出了《爱丽丝漫游奇境记》以及大量其他深受欢迎的文学作品。他还将他的数学知识与文学天赋相结合,完成了一篇知名度略低的文章——《草地网球锦标赛:正确的名次确定方法以及现行方法辨误》。
[
上一页 ]
[ :1.70049508e+09 ]
[
下一页 ]