1700495313
算法之美：指导工作与生活的算法 缓存清理与未卜先知
1700495314
1700495315
夏洛克·福尔摩斯
1700495316
1700495317
相信我，总有一天，当你增加新知识的时候，就会把以前熟知的东西忘了。所以最要紧的是，不要让一些无用的知识把有用的挤出去。
1700495318
1700495319
缓存满了后，如果你想继续在缓存中存储其他东西，就必然需要腾出一些空间。在计算机科学中，在缓存中腾出空间的过程被称为“缓存替换”或“缓存清理”。威尔克斯指出：“由于缓存的容量比主存小好几倍，不能无限度地把数据保存在其中，因此我们必须在系统中植入一个算法，逐步覆盖缓存中的数据。”这些算法被称为“替换策略”或“清理策略”，或者简单地称为缓存算法。
1700495320
1700495321
我们知道，IBM在20世纪60年代率先推动缓存系统的部署应用。不出意料，它也是早期缓存算法开创性研究的发源地，也许他们取得的任何一项成果都没有拉斯洛·贝莱迪的算法重要。1928年，贝莱迪出生于匈牙利，大学期间学的是机械工程专业。在1956年匈牙利革命期间，身无分文的他逃到了德国，随身携带的书包里只装有“一件内衣和毕业论文”。后来，他又离开德国，来到法国，并于1961年移民到美国。这一次，他带着妻子，“襁褓中的孩子，口袋里装着1000美元。除此以外，就别无他物了”。似乎在他进入IBM研究缓存清理之前，他就已经深谙此道，知道哪些东西该留下来，哪些东西可以抛弃。
1700495322
1700495323
贝莱迪于1966年发表的那篇缓存算法论文是随后15年里被引用最多的计算机科学研究成果。这篇论文解释道，缓存管理的目标是尽可能减少“页面错误”或“缓存缺失”。所谓缓存缺失，是指无法在缓存中找到所需数据，因此只能到较慢的主存中查找的现象。贝莱迪在文中写道，从本质上讲，最优缓存清理策略就是在缓存已满时，将未来最长时间内不会再次使用的数据从缓存中清理出去。
1700495324
1700495325
当然，要确切地知道什么时候会再次需要某些数据，并不像说起来那么容易。
1700495326
1700495327
今天，为了表示敬意，人们把那个无所不知、有先见之明，而且可以在分析未来情况基础上执行最优缓存策略的那个假想算法称作贝莱迪算法。该算法是被计算机科学家称为“千里眼”算法的一个实例，一个可以从未来数据中获取信息的算法。这个概念其实并不像听起来那么疯狂（在某些情况下，系统可能会对未来产生一种期望），但是一般来说，未卜先知是很难实现的，因此软件工程师在实践中试图使用贝莱迪算法时，就会开玩笑说他们遭遇了“实施难题”。因此，我们面临的挑战是找到一种接近于未卜先知的算法，当我们被当前现状遮住双眼的时候，可以借助这种算法看清楚未来的情况。
1700495328
1700495329
我们可以尝试随机清理算法，将新数据添加到缓存中，并随机覆盖旧数据。随机清理是早期高速缓存理论得出的一个令人吃惊的结果，虽然远非完美，但是效果也还不错。这也可能是一种巧合，因为只要有一个缓存，无论你如何维护，都可以提升系统的效率。不管怎么说，你经常使用的内容通常还会很快回到缓存中。另一种简单的策略叫作先进先出（FIFO）。这种算法总是清理或覆盖在缓存中保存时间最久的内容（与玛莎·斯图尔特问的“我已拥有它多长时间了”这个问题有异曲同工之妙）。第三种方法是最近最少使用（LRU），即将闲置不用时间最长的内容清理掉（与之相对应的斯图尔特的问题是“上次穿它或使用它是什么时候的事”）。
1700495330
1700495331
事实证明，斯图尔特强调的这两点暗示了两种截然不同的策略，而且她的一条建议显然比另一条更有效果。贝莱迪在若干情形下对随机清理、先进先出和最近最少使用的几个变体进行了比较，结果发现最近最少使用法始终表现出最接近未卜先知的效果。最近最少使用法的高效性得益于计算机科学家所谓的“时间局部性”：如果一个程序曾经调用过某个信息，那么在不久的将来它可能会再次调用这个信息。计算机解决问题的方式（例如，执行一个循环，使一系列相关的读和写可以快速完成）是造成时间局部性的一个原因，而人解决问题的方式是另外一个原因。在使用电脑时，你可能会在电子邮件、网页浏览器和文字处理器之间来回切换。你最近访问过这些程序的这个事实就是一个线索，表明你可能会再次访问该程序。在同等条件下，如果某个程序处于闲置状态的时间较长，就表明你在未来一段时间内应该也不会调用该程序。
1700495332
1700495333
事实上，这一原则甚至隐含于计算机向用户展示的界面中。电脑屏幕上的窗口有所谓的“Z轴顺序”，即决定程序相互叠加次序的模拟深度。最近最少使用的程序处于底部。前火狐浏览器的创意主管阿扎·拉斯金说：“使用现代浏览器（电脑）在很多时候就相当于从事数字版的文书工作。”与“文书工作”的相似性淋漓尽致地体现在微软系统Windows和苹果系统Mac OS任务切换界面中：当你按下Alt+Tab或Command+Tab组合键时，就会看到，你最近使用过的程序按你使用的时间先后逆向排列。
1700495334
1700495335
研究缓存清理策略的相关文献已经达到了令人难以想象的深度，各种算法应有尽有，不一而足，有的可以计算使用频率和最后一次使用时间，有的可以追踪倒数第二次访问的时间，而不关心最后一次访问的情况。不过，尽管创新性高速缓存方案品种繁多，其中一些在适当的条件下甚至可以击败最近最少使用法，但是最近最少使用法（以及在该策略基础上做出的一些细微调整）仍然深受计算机科学家们的喜爱，并且在开发各种应用程序时得到不同程度的应用。最近最少使用法告诉我们，我们需要的下一个程序可能就是之前我们需要的最后一个程序，接下来我们可能还需要之前需要的倒数第二个程序。我们最不需要的可能就是我们弃用时间最长的那个程序。
1700495336
1700495337
除非有充分的反对理由，否则我们可以认为对未来最有借鉴意义的就是历史的镜像。最接近于未卜先知的做法就是假定历史会重演，不过是按照相反的顺序重新上演。
1700495338
1700495339
1700495340
1700495341
1700495343
算法之美：指导工作与生活的算法 重整图书馆藏书
1700495344
1700495345
加州大学伯克利分校的地下加德纳书库是加州大学图书馆系统的一大亮点。书库在一扇锁着的门后，门上写着“闲人止步”几个显眼的大字，把想要借阅图书的人堵在门外。这里收藏着科马克·麦卡锡、托马斯·品钦、伊丽莎白·毕肖普、J.D.塞林格、阿娜伊斯·宁、苏珊·桑塔格、朱诺·迪亚斯、迈克尔、查邦、安妮·普劳克丝、马克·斯特兰德、菲利普·K·迪克、威廉·卡洛斯·威廉姆斯、恰克·帕拉尼克、托妮·莫里森、丹尼斯·约翰逊、朱莉安娜·斯帕尔、乔丽·格雷厄姆、戴维·赛达瑞斯、西尔维亚·普拉斯、戴维·马梅特、戴维·福斯特·华莱士和尼尔·盖曼等人的作品。但是，这些不是图书馆的珍本藏书，而是它的“缓存”。
1700495346
1700495347
前文讨论过，图书馆与我们自己的桌面空间相互配合，就可以恰如其分地表现出分级存储器体系的特点。实际上，图书馆由不同分区和存储设施构成，本身就是多层次分级存储器体系的一个具体实例，因此图书馆面临各种各样的缓存问题。图书馆工作人员必须决定把哪些书放在图书馆最前面的有限展示空间里，哪些书放到书架上，哪些书放到其他地方储存起来。各图书馆判断哪些书应该异地收藏的策略都不相同，但是几乎所有图书馆都会使用某种版本的最近最少使用策略。加州大学伯克利分校图书馆负责监督这个过程的贝丝·杜普斯说：“举例来说，如果一本图书12年里没有人借阅，我们就会把它撤出主馆。”
1700495348
1700495349
图书馆“粗略分类”区的情况与12年没有人借阅的图书正好处于两个极端。我们在前一章讨论过这些图书：它们刚刚被读者归还到图书馆，还没有被完全排序并重新放到书架上。具有讽刺意味的是，在某种意义上看，那些辛勤的图书馆助理在把这些图书放回书架上的时候，可能会让次序变得更乱。
1700495350
1700495351
原因很简单。如果时间局部性有效，那么粗略排序书架上摆放的就是整幢楼里最重要的图书。这些都是最近被人借阅过的书，所以学生们寻找的可能就是它们。可以说，图书馆的这种做法就相当于把几英里长的书架中最有吸引力、最值得浏览的那些书架藏起来，不向学生开放，而是让态度认真、埋头工作的图书馆员工不断地破坏它们，这似乎是一种非常愚蠢的决定。
1700495352
1700495353
与此同时，墨菲特本科生图书馆的大厅在最显眼、最容易进入的位置摆放一些书架，用来展示图书馆最近添加的图书。这种安排是先进先出缓存的一个具体体现：享受特殊待遇的是图书馆最后添加的图书，而不是刚刚被人借阅过的图书。
1700495354
1700495355
鉴于最近最少使用算法在计算机科学家的大多数测试中占尽优势，我们不妨向图书馆提出一个简单的建议：把图书馆的藏书来个乾坤大挪移。把图书馆刚刚添加的图书放到里面的书架，让需要的人去那里寻找；把最近归还的图书放在大厅里，以方便学生自由浏览。
1700495356
1700495357
人是一种社会生物，也许大学生希望可以培养自己的阅读习惯。大学经常会指定“普通图书”，目的是促进学生建立共同的学术参照点，而学生自行培养阅读习惯的做法将把校园推向一个更有机、更自由的学术参照点。这样，校园里正在阅读的图书，无论是什么内容，都可能成为其他学生偶然发现的好书，这就相当于实施了一种来自草根阶层、自下而上的普通图书计划。
1700495358
1700495359
这样的系统不仅有积极的社会意义，而且可以提高效率，因为最近归还的图书可能很快就会被人再次借阅。也许学生们可能会感到困惑，不知为何受欢迎的图书有时摆放在书架上，有时可以在大厅里找到。因为，曾经的情况是刚刚归还、等候上架的图书既不会出现在书架上，也无法在大厅里找到。在这个短暂的过渡时期，这些图书暂时无法借阅。所以，把刚刚归还的图书摆在大厅里，学生们可以彻底避免受到图书上架的短暂影响，有机会及时借阅这些图书。图书馆员工无须把图书一本本放到书架上，学生们也不必去书库把这些图书拿出来。确切地说，缓存就应该发挥这样的效果。
1700495360
1700495361
[
上一页 ]
[ :1.700495312e+09 ]
[
下一页 ]