Open hfuuss opened 5 years ago
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。 常见的缓存策略有三种:先进先出策 略FIFO(First In，First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used) 缓存： 空间换时间
单链表、双向链表和循环链表
// TODO
我的思路是这样的:我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。 1.如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。 2.如果此数据没有在缓存链表中，又可以分为两种情况: 如果此时缓存未满，则将此结点直接插入到链表的头部; 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。 这样我们就用链表实现了一个LRU缓存，是不是很简单? 现在我们来看下m缓存访问的时间复杂度是多少。因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度 为O(n)。 实际上，我们可以继续优化这个实现思路，比如引入散列表(Hash table)来记录每个数据的位置，将缓存访问的时间复杂度降到O(1)。因为要涉及我们还没有讲 到的数据结构，所以这个优化方案，我现在就不详细说了，等讲到散列表的时候，我会再拿出来讲。 除了基于链表的实现思路，实际上还可以用数组来实现LRU缓存淘汰策略。如何利用数组实现LRU缓存淘汰策略呢?我把这个问题留给你思考。
1、实现 LRU 2、回文字符串
hfuuss
commented
5 years ago hfuuss
commented
5 years ago
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。 常见的缓存策略有三种:先进先出策 略FIFO(First In，First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used) 缓存： 空间换时间
常见链表
单链表、双向链表和循环链表
循环链表实现 约瑟夫问题
// TODO
数组和链表比拼
如何基于链表实现LRU缓存淘汰算法?
我的思路是这样的:我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。 1.如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。 2.如果此数据没有在缓存链表中，又可以分为两种情况: 如果此时缓存未满，则将此结点直接插入到链表的头部; 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。 这样我们就用链表实现了一个LRU缓存，是不是很简单? 现在我们来看下m缓存访问的时间复杂度是多少。因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度 为O(n)。 实际上，我们可以继续优化这个实现思路，比如引入散列表(Hash table)来记录每个数据的位置，将缓存访问的时间复杂度降到O(1)。因为要涉及我们还没有讲 到的数据结构，所以这个优化方案，我现在就不详细说了，等讲到散列表的时候，我会再拿出来讲。 除了基于链表的实现思路，实际上还可以用数组来实现LRU缓存淘汰策略。如何利用数组实现LRU缓存淘汰策略呢?我把这个问题留给你思考。