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
道奇森不仅仅是一个数学家（其实他几乎不记得自己是从事数学研究的）。现在，反而是他的笔名——刘易斯·卡罗尔更加广为人知。他以这个笔名写出了《爱丽丝漫游奇境记》以及大量其他深受欢迎的文学作品。他还将他的数学知识与文学天赋相结合，完成了一篇知名度略低的文章——《草地网球锦标赛：正确的名次确定方法以及现行方法辨误》。
1700495130
1700495131
道奇森针对的是单一淘汰赛。在这种赛制下，运动员两两对决，只要输掉一场比赛，就会被淘汰出局。道奇森的理由非常有说服力，他认为，货真价实的第二名有可能是被第一名淘汰的任何人，而不一定是最后才被淘汰的那名运动员。具有讽刺意味的是，奥运会设立有铜牌争夺赛，这个规定似乎表明我们知道单一淘汰模式无法确定第三名。[1]但是，这种赛制其实同样不足以确定第二名的归属，实际上，它只能准确地判断出谁是第一名。正如道奇森所说：“利用现行办法确定的名次，除了第一名，其他的都毫无意义。”直白地说，银牌是一种假象。
1700495132
1700495133
“作为一个数学事实，”他继续写道，“实力排第二位的运动员获得应得名次的机会只有16/31，而最优秀的4名运动员获得与实力相称名次的机会非常小，发生的概率为1/12！”
1700495134
1700495135
尽管道奇森的文章犀利有力，却没有对草地网球产生任何影响。他提出应该采取三败淘汰制（根据这种赛制，击败过你的运动员如果落败，也有可能导致你随之出局），但是这个提议根本没有人理会。不过，虽然道奇森的解决方案实施起来有很大的难度，但是他在这个问题上的看法仍然是有道理的。（可惜的是，至今为止，在单淘汰赛中，仍然会颁发银牌。）
1700495136
1700495137
不过，道奇森的逻辑还给我们带来了一个更加深刻的认识。我们人类不仅会对数据、财产进行排序，还会把我们自己变成排序对象。
[
上一页 ]
[ :1.700495088e+09 ]
[
下一页 ]