王坤祥2020-04-06陈老师您好，文章中提到的第四个算法LRU算法，在使用哈希表和链表的实现中，链表的数据结构有必要使用双向链表吗？既然有哈希表的映射关系了，是不是一个简单的链表就可以啦。 或许我哪里思考的不全面，需要向您请教~~~作者回复: 你注意到了这个问题，非常棒！多问为什么，你就会想得更明白。 你可以想一下，lru把一个元素提到链表头是怎么操作的。步骤如下: 1.查询哈希表 2.通过哈希表直接访问到链表中的节点k（注意:节点k不是遍历链表得到的！是哈希表直接定位的！因此，我们此时并不知道k的前序节点是哪个）。 3.将节点k提到链表头。到这一步的时候，你就会发现，如果链表是单链表的话，那么如何把k节点从链表中摘取出来，然后链表还不能被打断，这就成了一个问题了。因此，我们用双向链表，就可以快速地找到k节点的前序节点，这样就能完成节点k的摘取操作。
共 7 条评论20
峰2020-04-061. 调整次序： 在数据库的最常见的就是join-order这个老大难问题，堪称数据库一朵大乌云。。。 2. 快速多路归并法： 多路归并可谓是数据库解决数据排序，尤其是不能内排的条件下的一大基础利器，当然像大数据组件里的mr，spark等等，做shuffle时，同样要考虑多个排序数组如何归并的问题。 3.预先组合： 最熟悉的代表就是kylin了， 经典的cube预计算理论， 4. 缓存法：这个就太多了，核心还是局部性原理，所以必须清楚自己的业务场景是否是有那种比较热点的查询，如果每种查询概率都一样，那缓存法也是浪费，所以mysql在某个版本之后把sql到结果的缓存给关闭了。作者回复: 1.调整次序涉及到预估代价的问题，因此如果对于系统的数据分布情况不清楚的话，的确效果不见得好。可以在有把握的情况下才调整。 2.3.你会发现，检索核心技术是通用的，大数据时代的各个框架都会用相似的技术来进行加速处理。万变不离其宗。 4.非常好！任何方案都有自己的适用场景。因此我们才需要学习它们的实现原理。缓存法适用于有查询热点存在的场景。否则如果没有热点，缓存的命中率不高，它反而会造成无谓的缓存管理代价。
共 2 条评论12
流浪在寂寞古城2020-06-20前两种方法：调整批次法和快速多路归并法是实时召回的方法 后两种方法：预先组合、缓存法实际上就跟我们设计系统时redis作为缓存一个道理，防止打穿来提高效率。 但是后两种方法在用的时候应该还要注意实时更新问题，比如搜索引擎中，更新了数据，如果使用缓存那么只能召回已经“计算”好的数据，即使是热点。就搜索引擎的应用，缓存的key应该还要保存一个时间进行重召回替换，比如1分钟这样。一般搜索引擎应该使用双buffer机制来更新。作者回复: 其实每种方法都有要注意的问题，都需要进行一定的优化才能更好地发挥效果。 1.调整批次法要预判是否调整以后有效，否则如果调整前和调整后性能差不多，那么无谓的调整反而会增大开销。 2.快速多路归并法适用在要归并的key较多且posting list较长的情况下。否则频繁的排序调整也是一个额外开销。 而预先组合和缓存法，就像你说的，需要有合理的实时更新方案。而且缓存法适用于有热点的情况下，并且需要设置缓存的生命周期，在一些场景下，还要解决数据一致性，缓存击穿等问题。 因此，我们无论是使用什么方法，一定要深入了解这种方法的优点和缺点，并针对具体场景采用合适的解决方案。
2
aoe2020-04-18“快速多路归并法”的图解非常好，一看就明白了。如果只看文字描述，是很难理解的。 老师的图解非常重要，让难以理解的算法变的简单明了。 阅读本专栏全程“轻松愉快”，原来是因为能读懂。很多令人望而生畏的算法，都让图解化解了！ 专栏可以有一个别名：检索算法图解。让更多基础不好，又想学习的同学轻松学习。 另外分享一个LRU算法的练习，更好的理解实现原理：https://leetcode-cn.com/problems/lru-cache/作者回复: 起名字的确是个难题。基础篇会比较偏算法，但是进阶篇开始会有一些系统设计和更全面的知识。所以最后还是定了这么一个“朴实无华且枯燥”的题目。希望到后面全部看下来都能保持轻松愉快😄
2
每天晒白牙2020-04-06思考题： 1.调整次序法 调整次序法是有前提的，就是集合大小要有诧异且调整后优于调整前，所以依赖预判机制 2.快速多路归并法 多路归并法充分利用跳表加快速度，老师说在 ES 中采用了这个方法，在下面我要看看加深理解 3.预先组合法 预先组合法适合用在数据报表分析的场景上，比如我们部门的报表系统就原始数据存放在 hive 上，然后通过 druid 和 kylin 对一些常用的组合做提前预聚合，这样可以加快查询速度。但我们在使用的时候，druid 和 kylin 对组合数和对应的数据也会有限制的，不能滥用，毕竟会浪费内存 4.缓存加速联合查询 缓存和预先组合法挺像，都是提前把数据准备好。但是它俩又有不同，预先组合的数据一般是稳定的，而缓存的数据是热点数据，如果非热点数据放到缓存中，会白白浪费内存，所以存储空间是需要考虑的。再者就是缓存命中率的问题，可以引入 LRU 缓存替换机制，把常用的缓存放到前面能够快速访问。通过双向链表 + 哈希表实现作者回复: 总结得很好。es中也用了快速多路归并法，因此你现在了解了这个算法以后，再去看es的相关代码，相信就容易理解了。 至于3和4，你的举例和总结都很好。其实在你们的广告系统中，如果想提高性能，也可以试试这两种方案。
2
多襄丸2020-04-13老师，我想问个问题 (jdk_1.8)： LinkedHashMap 的 accessOrder = true ，它表示遍历的时候按 访问的顺序输出。 我现在 linkedHashMap map; // accessOrder = true map put(1，1); // a map put(2，2); // b map put(3，3); // c A处： 此时若遍历，打印的顺序是 1 2 3 map. get(2); // d B处：此时若遍历，打印的顺序是 1 3 2 我知道accessOrder = true时，每访问过一个元素，都要改变它的位置链到双链表的末尾去。 我的问题是： 既然accessOrder = true 那它的遍历打印，不应该是最后（最后是时间上的顺序，那也就是最近）访问过的元素先被打印出来吗？ 即B处的遍历打印应该是 2 3 1 才对啊 ？ 还是应该理解成： 在B处：1的唯一一次访问是在注释为a的地方访问的； 3的唯一一次访问是在注释为c的地方访问的；2的第一次访问是 在注释为 b的地方访问的，最后一次访问是在注释为 d的地方访问的，访问被更新，因此加到末尾； 由此推出 ==> 1的访问时间最早 1先输出 3的访问时间早于最后一次2的访问时间， 所以接着3输出 2的访问时间由于是最后一次访问更新了访问时间，所以放到链表末尾，表示最后一个访问的。 因此，遍历输出应该是==> 1, 3, 2 而不是 2 开头。 即，访问时间遍历（accessOrder = true）的意思是，最早访问过的先被遍历，最晚访问过的元素，最后被遍历，是这个意思吗？ 我没评论之前还没想明白，评论完了，好像终于想清楚了。还是想找老师确认一下。 恳请老师回答，谢谢老师！展开作者回复: 你的理解是对的。accessOrder = true，表示“使用最近最少访问次序”，那么按照“最近最少使用”来排序的话，就是1，3，2了。 当然，由于是双链表，因此不管是升序还是降序都可以操作，只要弄清楚链表头和链表尾元素的意义就好。
共 2 条评论1
许大勇2020-12-25老师，对于快速多路归并法，我有一些疑惑。在多路归并的时候，因为集合可能是链表，那么如果我们是在求交集的时候才对多个数据集合建立跳表这样的数据结构，时间复杂度该如何考虑呢？还是我们应该在求交集前就已经把各个数据集的跳表索引建立好呢？如果数据集都非常大，并且是静态(不会再改变)的，会损失一些跳表本该具有优势的特性吗，比如快速插入和删除？作者回复: 临时建立数据结构往往开销都挺大，因此一般来说，我们都是提前建立好索引。 如果数据集本身是静态的不可变的，没有实时插入删除的问题，那么其实完全可以使用数组代替跳表，这样空间也紧凑，还能利用内存局部性原理进行加速。
汤尼房2023-05-22 来自广东说下对于LRU实现的基本思考： 假设一个容量为3的缓存cache = []，此时添加缓存A，cache = [A]；添加缓存B，cache = [B, A]；添加缓存C，cache = [C, B, A]; 访问缓存A后，cache变为[A, C, B]；若此时再要加入缓存D，则因为缓存容量只有3，因此需要淘汰掉最久没被使用的缓存B才可以，因此cache变为 [D, A, C]；从中可以发现缓存的实现有最本质的三个特点，一是各个缓存之间是有顺序的，比如D在A之前，A在C之前（A相比C在最近的时间内被使用过）； 二是要能快速的判断出一个缓存是否在缓存中，比如A是否在cache中；三是从缓存中删除一个元素的操作也要是便捷的（O(1)），所以结合这三点来看， 单单的数组与Dict都是无法满足最优条件的。拿数组来说，其能够满足顺序这个特性，但判断一个缓存元素是否在其中，需要遍历整个数组， 且当删除一个缓存元素时，还伴有数组内元素移动的操作，因此整个的性能开销很大；再来看Dict，Dict能够满足O(1)的缓存元素的快速判断， 且删除元素的操作也为O(1)，但Dict中的元素没有顺序，比如因为缓存容量满了需要淘汰最久没有被使用的元素（按顺序来看，处于最末尾的元素）， 此时在Dict中是没有办法识别处于末尾的元素的。所以最好的方式是对基本的数据结构进行组合使用，依然是三个特点：有序，O(1)查找，O(1)删除； Dict + 数组：数组用于实际存储缓存元素，Dict用于快速判断缓存是否存在，但是数组的淘汰删除策略不是最优的，因此不能满足条件； Dict + 双向链表：双向链表用于实际存储缓存元素，Dict依然是用于快速判断缓存元素是否存在，双向链表本身有序，且删除一个特定节点操作的时间 复杂度是O(1)，因此LRUCache最终的实现方式是采用Dict + 双向链表 字典dict+双向链表实现 1. dict存储真正的被封装成双向链表节点的key、value对，即key -> Node(key, value) 2. 双向链表和上述使用到的数组一样，用于记录元素的位置展开
ifelse
2023-04-07 来自浙江Nice，very good👍🏻