三月倒春寒，天气的喜怒无常让你一会短袖，一会毛衣，忙碌了一天的你回到家里，因为穿了毛衣，所以满头大汗，想马上换身凉爽的衣服，但乱糟糟的衣柜又要花几个小时来整理，想想就不happy，如何一回到家就极速换上舒爽的衣服，开心的摊在沙发上，而且自己的其他衣物依然摆放整齐呢？
有一个算法能够让你迅速找到要穿的衣服鞋子而其他衣物依然摆放整齐，它还能够使你迅速搜寻到研究资料的同时办公桌依然井井有条，而且它还可以让你在人际交往中游刃有余，杜绝无效社交，从而拥有高效率人生，这就是最近最少使用替换算法（Least Recently Used，LRU）。
本周，我们来聊一聊【缓存】。由来自杜克大学的美女主播段天霖与大家分享：“LRU算法”赋能你的高效人生。
如果电脑的1024G内存装满时，就需要把一些视频，Vi源图等大文件忍痛割爱删除，才能让新的资料储存进来。这一so easy的方法，在计算机算法里被称为替换策略或剔除策略。
此算法由莱斯洛.贝雷迪创造，它的目的是最大化减少在缓存中不需要的数据，缓存装满时就替换或删除很长时间之后才会再次需要的资料，这个算法的核心是要预测什么时候会再次需要哪些数据。这个未雨绸缪、能够预测未来并且执行已知最优策略的算法，被称为贝雷迪算法（Bélády’s Algorithm）。
这个理论尽管不能够做到完美，但却能够极大的提高我们的效率。
贝雷迪算法（Bélády’s Algorithm）有三种方式：
-
随机剔除算法（Random Eviction），把新获取的数据放进缓存，随机替换旧的数据资料；
-
先进先出算法（ First In, First Out，FIFO），删除或替换在缓存停留时间最长的资料；
-
最近最少使用替换算法（Least Recently Used，LRU），覆盖或删除未使用时间最长的数据资料。
对于这三种方法，贝雷迪在多种情况下的做过测试比较，发现最近最少使用替换算法（Least Recently Used，LRU）的表现最佳。
在用计算机办公的时候，你可能会在email、网页浏览器和OFFICE软件之间不断切换，你刚刚用过其中一个软件，就有可能再次使用到它。不出意外的话，上次使用时间离现在时间最长的软件，通常也会隔很久时间才会用到。
对于操作系统的内存管理，需要解决的最难的问题是你使用了如此多软件程序，如何最有效率利用内存容量有限的内存，让多种软件程序的切换使用更流畅。
最近最少使用替换算法是为内存的虚拟存储管理服务的，是目前最通用、最有效的方法。
简单说就是在内存有限的状态下，增加一部分外存作为虚拟内存，把进程所需空间划分为多个页面，内存中只存放当前所需页面，真正的内存只存储当前运行时所用得到信息，其余页面放入外存，这就扩充了内存的功能，极大地提高了计算机的能力。
最近最少使用替换算法（Least Recently Used，LRU）根据数据的历史访问记录来进行删除数据资料，其关键的原则是“如果数据最近被访问过，那么将来被访问的几率也更高”。顾名思义，此算法关心的因素为：时间最近，距离最短。
运用这一算法最成功的大概是一些零售巨头：盒马先生、京东和亚马逊等。
亚马逊不采用传统图书馆或百货公司的仓储方式，而是通过研究消费者历史订单、搜索记录、愿望清单、购物车清单、退货记录、鼠标在各种商品的停留时间等各种数据预测出消费者下一步可能购买的商品，把最近的某个区域非常热销的商品，配送到该地区的临时仓库。
仓库内部看起来非常混乱，玩具可能放在钢笔、尿不湿、键盘和小提琴旁边，但是需求购买量大的商品会排放在不同区域。商品距离顾客已经很近，当顾客下单时，产品能迅速配送。这种仓储方式就是亚马逊根据贝雷迪算法（Bélády’s Algorithm）发明的“预测式出货”专利。
简要总结一下，亚马逊通过划分临时仓库和中央仓库的不同功能，让临时仓库存放顾客购买需求量大的商品，由于距离非常近，很利于短时间内完成配送服务，提升了顾客满意度，从而带来稳定高效的现金流。
LRU算法让你收纳衣物so easy
我们常看到的收纳建议，是把类似的物品归在一起。日本的东京大学的经济学家野口悠纪雄是反对此看法的，他出版过非常多办公室收纳和人生攻略的畅销书籍，刚开始研究经济学时，他常常被书籍和笔记等大量文件淹没，每天都要花很多时间整理。
一开始他只是把每份文件放进档案袋里，档案袋上标注文件标题和日期，然后把档案袋全部放进大箱子里，这种方法不需要思考每份文件的如何摆放，能节省很多时间。
到了1990年代初期，他一律把档案袋放在箱子的左手边。野口指出，不论新档案还是旧档案，都适用左边法，每次取出档案用过后，一定是放在箱子最左边，找档案也是从最左边开始，这样，他最先看到的就是最近使用过的档案。
野口一开始这样做，只是因为把档案塞到最左边比塞回原处要容易得多，但他后来发现，这种方式不只是简单，而且更有效率。然而这种方法有个问题，是否容易找到你需要的档案呢？
虽然野口当时并不知道他的收纳方法其实就是最近最少使用替换算法的延伸。最近最少使用替换算法告诉我们，把新的资料放入缓存时，应该剔除最旧的内容。
但我们应该把新的资料放在哪里，才会提高下次搜寻的效率？1970和1980年代的计算机科学家，进行了一系列的研究，解答了这个问题。当时他们遇到的问题和野口归档的困境一样，在寻找档案时，你必须要从头开始逐一看过每个档案，但你找到所需的档案后，可以放在任何位置。此时你应该把这个档案放在哪里，才能更高提升下次的搜索效率？
Daniel Sleator和Robert Tarjan在1985年发表关于自组织列表的重要论文。通常，搜寻从最前端开始，所以我们排列顺序时，也希望把最可能用到的物品放在最前端，但最可能用到的物品又是什么呢？这又回到预测未来的问题了。
史利特和塔尔占的研究结果显示，如果我们遵循最近最少使用替换算法，每次把物品放回最前端，那搜索所花的时间，绝对不会超过我们能预知未来时的两倍，而且其他算法都没办法保证这一点。
史利特和塔尔占的研究结果还提出另一种变化，把野口的档案收纳方法旋转90度，一箱档案旋转90度就变成一摞档案，这样一来在找档案时，自然会从上到下，每次抽取文件后不放回原处，而放在最上面。在书桌上堆了一大摞文件，不但是不是混乱的象征，还是目前已知最有效率的资料摆放结构，没有必要产生罪恶感，由于我们无法预知未来，所以把用过的东西放在最上面是最好的办法。最近最少使用替换算法不只更有效率，而且就是最佳方法。
那如何利用此算法高效整理你家的衣服鞋子呢？
首先，决定要保留和舍弃哪些衣物。如果你念大学时买的T恤有时还会穿，就不要丢掉；但很久没穿的格子长裤，就送到二手店，说不定要能遇到白富美。
其次，利用家里的不同空间。你经常在哪里穿西装，是卧室，还是书房，还是客厅，就把西装放在离那个地方最近的柜子里。这点经常被收纳专家提到，Julie Morgenstern的《收纳其实很容易》有这么一段话：我把跑步和运动用品放在前门衣柜的底部箱子里，我希望它尽量接近大门。
最后，多层次收纳。同时具备小容量且速度快和大容量且速度慢等多个层次结构的缓存，效率会更高。例如你家的收纳空间，门口的鞋柜是第一个存储结构，卧室的衣柜是第二个，地下室是第三个，依据最近最少使用替换算法（Least Recently Used，LRU），拿到衣服鞋子的速度会随着层级而越来越慢，不同物品会从每个层级剔除到下一个层级，你可以再买一个比鞋柜更小，取用速度更快的收纳箱。
LRU算法赋能你的高质量社交
有人说，人的地位是由认识与交往陌生人的能力决定的。
陌生人与熟人只是一层窗户纸，你完全有能力让一个陌生人变成熟人，自己的人脉远不是按交换的名片数量决定的，关系的培养和维护才是最重要的。
使用最近最少使用替换算法，来弥补短时间内对彼此记忆的大幅度衰减，经过多次联系交往后，新的“熟人”才会形成和固化。
人的记忆的能力从生理上讲是十分惊人的，它可以储存10的15次方比特的信息，理论上能够把全世界图书馆的所有书籍数据信息记住，但却没有人能够做到，这是因为每个人都有记忆遗忘规律。
1887年，雅各布斯通过实验发现，对于无序的数字，测试者者可以记起的最大数量大约为7个。发现遗忘曲线的艾宾浩斯也发现，人在阅读一次后，可记住约7个字母。
1956年，美国心理学家米勒教授发表了一篇重要的论文《神奇的数字7±2：我们信息加工能力的局限》，明确提出短时间记忆的容量为7±2，即一般为7，并在5到9之间波动，这就是神奇的7±2效应，它告诉我们一个规律：在与陌生人交谈的时候，你要尽力将自己话语中的信息块控制在7±2的范围内。但如何做到呢？借鉴最近最少使用替换算法。
首先，预测对方最想听的内容，删除对方最不想听的，把对方最想得到的信息放在最前面，虽然7±2法则表示人能记下7个左右的信息块，但在社交场合中有很多干扰因素存在，比如噪音干扰和对方的心情，所以最好讲述两三个信息块，这样才能够给对方留下深刻的印象。
其次，结构化组合不同的重要信息块，用生动的肢体语言和幽默有趣的话语，来打动陌生人，让他们更好的回忆起你热情洋溢的笑容。例如郭德纲的相声，大家都爱，为什么，大包袱和小包袱很有节奏感，你笑的也有节奏感，喜欢音乐的我们当然也最痴迷有节奏的谈话。
最后，呵护你的关系，第一次见面的一周后，选择对方最熟悉的话题，比如选择与对方行业、公司、产品、个人兴趣相关的话题，来请教一些自己感到苦闷与感到不解的问题，回答的质量不重要，你也不要太挑剔，彼此的肯定很重要，当来往超过五个来回就属于一般意义上的熟人了。
此后每月保持一个月一次左右的微信问候，忌讳在初期交往的时候提出太多的苛刻要求，每年保持在三到四个节假日送上自己编写的好玩的祝福微信。有机会的话，参加朋友的聚会或邀请朋友带上他们的朋友一起参加有趣味的活动，来扩大自己的交往圈，使关系发展的“星星之火”可以高效留存下来。
马上就要过莺啼燕语的四月了，是个让自己改变的好时间。只要有这个最近最少使用替换算法（Least Recently Used，LRU），不论你在公司冲业绩，还是在学校写论文，还是你在家里被逼着做家务，还是要提升自己的社交质量，你都可以比别人更有效率，更快升职加薪、更快得到奖学金、更快整理衣物、更高效找合伙人。
原文发布时间为：2018-04-6
本文作者：文摘菌
