偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

冷淡的面試官,讓我手寫LRU緩存淘汰算法打發(fā)時(shí)間!

存儲(chǔ) 存儲(chǔ)軟件 算法
在我們這個(gè)日益追求高效的世界,我們對(duì)任何事情的等待都顯得十分的浮躁,網(wǎng)頁頁面刷新不出來,好煩,電腦打開運(yùn)行程序慢,又是好煩!那怎么辦,技術(shù)的產(chǎn)生不就是我們所服務(wù)么,今天我們就聊一聊緩存這個(gè)技術(shù),并使用我們熟知的數(shù)據(jù)結(jié)構(gòu)--用鏈表實(shí)現(xiàn)LRU緩存淘汰算法。

[[384337]]

本文轉(zhuǎn)載自微信公眾號(hào)「小郎碼知答」,作者Simon郎。轉(zhuǎn)載本文請(qǐng)聯(lián)系小郎碼知答公眾號(hào)。    

背景

在我們這個(gè)日益追求高效的世界,我們對(duì)任何事情的等待都顯得十分的浮躁,網(wǎng)頁頁面刷新不出來,好煩,電腦打開運(yùn)行程序慢,又是好煩!那怎么辦,技術(shù)的產(chǎn)生不就是我們所服務(wù)么,今天我們就聊一聊緩存這個(gè)技術(shù),并使用我們熟知的數(shù)據(jù)結(jié)構(gòu)--用鏈表實(shí)現(xiàn)LRU緩存淘汰算法。

在學(xué)習(xí)如何使用鏈表實(shí)現(xiàn)LRU緩存淘汰算法前,我們先提出幾個(gè)問題,大家好好思考下,問題如下:

  • 什么是緩存,緩存的作用?
  • 緩存的淘汰策略有哪些?
  • 如何使用鏈表實(shí)現(xiàn)LRU緩存淘汰算法,有什么特點(diǎn),如何優(yōu)化?

好了,我們帶著上面的問題來學(xué)進(jìn)行下面的學(xué)習(xí)。

1、什么是緩存,緩存的作用是什么?

緩存可以簡單的理解為保存數(shù)據(jù)的一個(gè)副本,以便于后續(xù)能夠快速的進(jìn)行訪問。以計(jì)算機(jī)的使用場景為例,當(dāng)cpu要訪問內(nèi)存中的一條數(shù)據(jù)時(shí),它會(huì)先在緩存里查找,如果能夠找到則直接使用,如果沒找到,則需要去內(nèi)存里查找;

同樣的,在數(shù)據(jù)庫的訪問場景中,當(dāng)項(xiàng)目系統(tǒng)需要查詢數(shù)據(jù)庫中的某條數(shù)據(jù)時(shí),可以先讓請(qǐng)求查詢緩存,如果命中,就直接返回緩存的結(jié)果,如果沒有命中,就查詢數(shù)據(jù)庫, 并將查詢結(jié)果放入緩存,下次請(qǐng)求時(shí)查詢緩存命中,直接返回結(jié)果,就不用再次查詢數(shù)據(jù)庫。

通過以上兩個(gè)例子,我們發(fā)現(xiàn)無論在哪種場景下,都存在這樣一個(gè)順序:先緩存,后內(nèi)存;先緩存,后數(shù)據(jù)庫。但是緩存的存在也占用了一部分內(nèi)存空間,所以緩存是典型的以空間換時(shí)間,犧牲數(shù)據(jù)的實(shí)時(shí)性,卻滿足計(jì)算機(jī)運(yùn)行的高效性。

仔細(xì)想一下,我們?nèi)粘i_發(fā)中遇到緩存的例子還挺多的。

  • 操作系統(tǒng)的緩存

減少與磁盤的交互

  • 數(shù)據(jù)庫緩存

減少對(duì)數(shù)據(jù)庫的查詢

  • Web服務(wù)器緩存

減少對(duì)應(yīng)用服務(wù)器的請(qǐng)求

  • 客戶瀏覽器的緩存

減少對(duì)網(wǎng)站的訪問

2、緩存有哪些淘汰策略?

緩存的本質(zhì)是以空間換時(shí)間,那么緩存的容量大小肯定是有限的,當(dāng)緩存被占滿時(shí),緩存中的那些數(shù)據(jù)應(yīng)該被清理出去,那些數(shù)據(jù)應(yīng)該被保留呢?這就需要緩存的淘汰策略來決定。

事實(shí)上,常用的緩存的淘汰策略有三種:先進(jìn)先出算法(First in First out FIFO);淘汰一定時(shí)期內(nèi)被訪問次數(shù)最少的頁面(Least Frequently Used LFU);淘汰最長時(shí)間未被使用的頁面(Least Recently Used LRU)

這些算法在不同層次的緩存上執(zhí)行時(shí)具有不同的效率,需要結(jié)合具體的場景來選擇。

2.1 FIFO算法

FIFO算法即先進(jìn)先出算法,常采用隊(duì)列實(shí)現(xiàn)。在緩存中,它的設(shè)計(jì)原則是:如果一個(gè)數(shù)據(jù)最先進(jìn)入緩存中,則應(yīng)該最早淘汰掉。

FIFO算法

新訪問的數(shù)據(jù)插入FIFO隊(duì)列的尾部,隊(duì)列中數(shù)據(jù)由隊(duì)到隊(duì)頭按順序順序移動(dòng)

隊(duì)列滿時(shí),刪除隊(duì)頭的數(shù)據(jù)

2.2 LRU算法

LRU算法是根據(jù)對(duì)數(shù)據(jù)的歷史訪問次數(shù)來進(jìn)行淘汰數(shù)據(jù)的,通常使用鏈表來實(shí)現(xiàn)。在緩存中,它的設(shè)計(jì)原則是:如果數(shù)據(jù)最近被訪問過,那么將來它被訪問的幾率也很高。

LRU算法

  • 新加入的數(shù)據(jù)插入到鏈表的頭部
  • 每當(dāng)緩存命中時(shí)(即緩存數(shù)據(jù)被訪問),則將數(shù)據(jù)移到鏈表頭部
  • 當(dāng)來鏈表已滿的時(shí)候,將鏈表尾部的數(shù)據(jù)丟棄

2.3 LFU算法

LFU算法是根據(jù)數(shù)據(jù)的歷史訪問頻率來淘汰數(shù)據(jù),因此,LFU算法中的每個(gè)數(shù)據(jù)塊都有一個(gè)引用計(jì)數(shù),所有數(shù)據(jù)塊按照引用計(jì)數(shù)排序,具有相同引用計(jì)數(shù)的數(shù)據(jù)塊則按照時(shí)間排序。在緩存中,它的設(shè)計(jì)原則是:如果數(shù)據(jù)被訪問多次,那么將來它的訪問頻率也會(huì)更高。

LFU算法

  • 新加入數(shù)據(jù)插入到隊(duì)列尾部(引用計(jì)數(shù)為1;
  • 隊(duì)列中的數(shù)據(jù)被訪問后,引用計(jì)數(shù)增加,隊(duì)列重新排序;
  • 當(dāng)需要淘汰數(shù)據(jù)時(shí),將已經(jīng)排序的列表最后的數(shù)據(jù)塊刪除。

3、如何使用鏈表實(shí)現(xiàn)緩存淘汰,有什么特點(diǎn),如何優(yōu)化?

在上面的文章中我們理解了緩存的概念及淘汰策略,其中LRU算法是筆試/面試中考察比較頻繁的,我秋招的時(shí)候,很多公司都讓我手寫了這個(gè)算法,為了避免大家采坑,下面,我們就手寫一個(gè)LRU緩存淘汰算法。

我們都知道鏈表的形式不止一種,我們應(yīng)該選擇哪一種呢?

思考三分鐘........

好了,公布答案!

事實(shí)上,鏈表按照不同的連接結(jié)構(gòu)可以劃分為單鏈表、循環(huán)鏈表和雙向鏈表。

  • 單鏈表
    • 每個(gè)節(jié)點(diǎn)只包含一個(gè)指針,即后繼指針。
    • 單鏈表有兩個(gè)特殊的節(jié)點(diǎn),即首節(jié)點(diǎn)和尾節(jié)點(diǎn),用首節(jié)點(diǎn)地址表示整條鏈表,尾節(jié)點(diǎn)的后繼指針指向空地址null。
    • 性能特點(diǎn):插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1),查找的時(shí)間復(fù)雜度為O(n)。
  • 循環(huán)鏈表
    • 除了尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)的地址外均與單鏈表一致。
    • 適用于存儲(chǔ)有循環(huán)特點(diǎn)的數(shù)據(jù),比如約瑟夫問題。
  • 雙向鏈表
    • 節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外,還有兩個(gè)指針分別指向前一個(gè)節(jié)點(diǎn)地址(前驅(qū)指針prev)和下一個(gè)節(jié)點(diǎn)地址(后繼指針next)
    • 首節(jié)點(diǎn)的前驅(qū)指針prev和尾節(jié)點(diǎn)的后繼指針均指向空地址。

雙向鏈表相較于單鏈表的一大優(yōu)勢(shì)在于:找到前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1),而單鏈表只能從頭節(jié)點(diǎn)慢慢往下找,所以仍然是O(n).而且,對(duì)于插入和刪除也是有優(yōu)化的。

我們可能會(huì)有問題:單鏈表的插入刪除不是O(1)嗎?

是的,但是一般情況下,我們想要進(jìn)行插入刪除操作,很多時(shí)候還是得先進(jìn)行查找,再插入或者刪除,可見其實(shí)是先O(n),再O(1)。

因?yàn)槲覀冃枰獎(jiǎng)h除操作,刪除一個(gè)節(jié)點(diǎn)不僅要得到該節(jié)點(diǎn)本身的指針,也需要操作其它前驅(qū)節(jié)點(diǎn)的指針,而雙向鏈表能夠直接找到前驅(qū),保證了操作時(shí)間復(fù)雜度為O(1),因此使用雙向鏈表作為實(shí)現(xiàn)LRU緩存淘汰算法的結(jié)構(gòu)會(huì)更高效。

算法思路

維護(hù)一個(gè)雙向鏈表,保存所有緩存的值,并且最老的值放在鏈表最后面。

當(dāng)訪問的值在鏈表中時(shí):將找到鏈表中值將其刪除,并重新在鏈表頭添加該值(保證鏈表中 數(shù)值的順序是從新到舊)

當(dāng)訪問的值不在鏈表中時(shí):當(dāng)鏈表已滿:刪除鏈表最后一個(gè)值,將要添加的值放在鏈表頭 當(dāng)鏈表未滿:直接在鏈表頭添加

3.1 LRU緩存淘汰算法

極客時(shí)間王爭的《數(shù)據(jù)結(jié)構(gòu)與算法之美》給出了一個(gè)使用有序單鏈表實(shí)現(xiàn)LRU緩存淘汰算法,代碼如下:

  1. public class LRUBaseLinkedList<T> { 
  2.  
  3.     /** 
  4.      * 默認(rèn)鏈表容量 
  5.      */ 
  6.     private final static Integer DEFAULT_CAPACITY = 10; 
  7.  
  8.     /** 
  9.      * 頭結(jié)點(diǎn) 
  10.      */ 
  11.     private SNode<T> headNode; 
  12.  
  13.     /** 
  14.      * 鏈表長度 
  15.      */ 
  16.     private Integer length; 
  17.  
  18.     /** 
  19.      * 鏈表容量 
  20.      */ 
  21.     private Integer capacity; 
  22.  
  23.     public LRUBaseLinkedList() { 
  24.         this.headNode = new SNode<>(); 
  25.         this.capacity = DEFAULT_CAPACITY; 
  26.         this.length = 0; 
  27.     } 
  28.  
  29.     public LRUBaseLinkedList(Integer capacity) { 
  30.         this.headNode = new SNode<>(); 
  31.         this.capacity = capacity; 
  32.         this.length = 0; 
  33.     } 
  34.  
  35.     public void add(T data) { 
  36.         SNode preNode = findPreNode(data); 
  37.  
  38.         // 鏈表中存在,刪除原數(shù)據(jù),再插入到鏈表的頭部 
  39.         if (preNode != null) { 
  40.             deleteElemOptim(preNode); 
  41.             intsertElemAtBegin(data); 
  42.         } else { 
  43.             if (length >= this.capacity) { 
  44.                 //刪除尾結(jié)點(diǎn) 
  45.                 deleteElemAtEnd(); 
  46.             } 
  47.             intsertElemAtBegin(data); 
  48.         } 
  49.     } 
  50.  
  51.     /** 
  52.      * 刪除preNode結(jié)點(diǎn)下一個(gè)元素 
  53.      * 
  54.      * @param preNode 
  55.      */ 
  56.     private void deleteElemOptim(SNode preNode) { 
  57.         SNode temp = preNode.getNext(); 
  58.         preNode.setNext(temp.getNext()); 
  59.         temp = null
  60.         length--; 
  61.     } 
  62.  
  63.     /** 
  64.      * 鏈表頭部插入節(jié)點(diǎn) 
  65.      * 
  66.      * @param data 
  67.      */ 
  68.     private void intsertElemAtBegin(T data) { 
  69.         SNode next = headNode.getNext(); 
  70.         headNode.setNext(new SNode(data, next)); 
  71.         length++; 
  72.     } 
  73.  
  74.     /** 
  75.      * 獲取查找到元素的前一個(gè)結(jié)點(diǎn) 
  76.      * 
  77.      * @param data 
  78.      * @return 
  79.      */ 
  80.     private SNode findPreNode(T data) { 
  81.         SNode node = headNode; 
  82.         while (node.getNext() != null) { 
  83.             if (data.equals(node.getNext().getElement())) { 
  84.                 return node; 
  85.             } 
  86.             node = node.getNext(); 
  87.         } 
  88.         return null
  89.     } 
  90.  
  91.     /** 
  92.      * 刪除尾結(jié)點(diǎn) 
  93.      */ 
  94.     private void deleteElemAtEnd() { 
  95.         SNode ptr = headNode; 
  96.         // 空鏈表直接返回 
  97.         if (ptr.getNext() == null) { 
  98.             return
  99.         } 
  100.  
  101.         // 倒數(shù)第二個(gè)結(jié)點(diǎn) 
  102.         while (ptr.getNext().getNext() != null) { 
  103.             ptr = ptr.getNext(); 
  104.         } 
  105.  
  106.         SNode tmp = ptr.getNext(); 
  107.         ptr.setNext(null); 
  108.         tmp = null
  109.         length--; 
  110.     } 
  111.  
  112.     private void printAll() { 
  113.         SNode node = headNode.getNext(); 
  114.         while (node != null) { 
  115.             System.out.print(node.getElement() + ","); 
  116.             node = node.getNext(); 
  117.         } 
  118.         System.out.println(); 
  119.     } 
  120.  
  121.     public class SNode<T> { 
  122.  
  123.         private T element; 
  124.  
  125.         private SNode next
  126.  
  127.         public SNode(T element) { 
  128.             this.element = element; 
  129.         } 
  130.  
  131.         public SNode(T element, SNode next) { 
  132.             this.element = element; 
  133.             this.next = next
  134.         } 
  135.  
  136.         public SNode() { 
  137.             this.next = null
  138.         } 
  139.  
  140.         public T getElement() { 
  141.             return element; 
  142.         } 
  143.  
  144.         public void setElement(T element) { 
  145.             this.element = element; 
  146.         } 
  147.  
  148.         public SNode getNext() { 
  149.             return next
  150.         } 
  151.  
  152.         public void setNext(SNode next) { 
  153.             this.next = next
  154.         } 
  155.     } 
  156.  
  157.     public static void main(String[] args) { 
  158.         LRUBaseLinkedList list = new LRUBaseLinkedList(); 
  159.         Scanner sc = new Scanner(System.in); 
  160.         while (true) { 
  161.             list.add(sc.nextInt()); 
  162.             list.printAll(); 
  163.         } 
  164.     } 

這段代碼不管緩存有沒有滿,都需要遍歷一遍鏈表,所以這種基于鏈表的實(shí)現(xiàn)思路,緩存訪問的時(shí)間復(fù)雜度為 O(n)。

3.2使用哈希表優(yōu)化LRU

事實(shí)上,這個(gè)思路還可以繼續(xù)優(yōu)化,我們可以把單鏈表換成雙向鏈表,并引入散列表。

  • 雙向鏈表支持查找前驅(qū),保證操作的時(shí)間復(fù)雜度為O(1)
  • 引入散列表記錄每個(gè)數(shù)據(jù)的位置,將緩存訪問的時(shí)間復(fù)雜度降到O(1)

哈希表查找較快,但是數(shù)據(jù)無固定的順序;鏈表倒是有順序之分。插入、刪除較快,但是查找較慢。將它們結(jié)合,就可以形成一種新的數(shù)據(jù)結(jié)構(gòu)--哈希鏈表(LinkedHashMap)

哈希表+雙向鏈表

力扣上146題-LRU緩存機(jī)制剛好可以拿來練手,題圖如下:

題目:

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu),設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制 。

  • 實(shí)現(xiàn) LRUCache 類:

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存

int get(int key) 如果關(guān)鍵字 key 存在于緩存中,則返回關(guān)鍵字的值,否則返回 -1 。

void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在,則變更其數(shù)據(jù)值;如果關(guān)鍵字不存在,則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時(shí),它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值,從而為新的數(shù)據(jù)值留出空間。

思路

我們的思路就是哈希表+雙向鏈表

  • 哈希表用于滿足題目時(shí)間復(fù)雜度O(1)的要求,雙向鏈表用于存儲(chǔ)順序
  • 哈希表鍵值類型:
  • 雙向鏈表的節(jié)點(diǎn)中除了value外還需要包含key,因?yàn)樵趧h除最久未使用的數(shù)據(jù)時(shí),需要通過鏈表來定位hashmap中應(yīng)當(dāng)刪除的鍵值對(duì)
  • 一些操作:雙向鏈表中,在后面的節(jié)點(diǎn)表示被最近訪問
    • 新加入的節(jié)點(diǎn)放在鏈表末尾,addNodeToLast(node)
    • 若容量達(dá)到上限,去除最久未使用的數(shù)據(jù),removeNode(head.next)
    • 若數(shù)據(jù)新被訪問過,比如被get了或被put了新值,把該節(jié)點(diǎn)挪到鏈表末尾,moveNodeToLast(node)
  • 為了操作的方便,在雙向鏈表頭和尾分別定義一個(gè)head和tail節(jié)點(diǎn)。

代碼

  1. class LRUCache { 
  2.     private int capacity; 
  3.     private HashMap<Integer, ListNode> hashmap;  
  4.     private ListNode head; 
  5.     private ListNode tail; 
  6.  
  7.     private class ListNode{ 
  8.         int key
  9.         int val; 
  10.         ListNode prev; 
  11.         ListNode next
  12.         public ListNode(){   
  13.         } 
  14.         public ListNode(int keyint val){ 
  15.             this.key = key
  16.             this.val = val; 
  17.         } 
  18.     } 
  19.  
  20.     public LRUCache(int capacity) { 
  21.         this.capacity = capacity; 
  22.         hashmap = new HashMap<>(); 
  23.         head = new ListNode(); 
  24.         tail = new ListNode(); 
  25.         head.next = tail; 
  26.         tail.prev = head; 
  27.     } 
  28.  
  29.     private void removeNode(ListNode node){ 
  30.         node.prev.next = node.next
  31.         node.next.prev = node.prev; 
  32.     } 
  33.  
  34.     private void addNodeToLast(ListNode node){ 
  35.         node.prev = tail.prev; 
  36.         node.prev.next = node; 
  37.         node.next = tail; 
  38.         tail.prev= node; 
  39.     } 
  40.  
  41.     private void moveNodeToLast(ListNode node){ 
  42.         removeNode(node); 
  43.         addNodeToLast(node); 
  44.     } 
  45.      
  46.     public int get(int key) {    
  47.         if(hashmap.containsKey(key)){ 
  48.             ListNode node = hashmap.get(key); 
  49.             moveNodeToLast(node); 
  50.             return node.val; 
  51.         }else
  52.             return -1; 
  53.         } 
  54.     } 
  55.      
  56.     public void put(int keyint value) { 
  57.         if(hashmap.containsKey(key)){ 
  58.             ListNode node = hashmap.get(key); 
  59.             node.val = value; 
  60.             moveNodeToLast(node); 
  61.             return
  62.         } 
  63.         if(hashmap.size() == capacity){ 
  64.             hashmap.remove(head.next.key); 
  65.             removeNode(head.next); 
  66.         } 
  67.  
  68.         ListNode node = new ListNode(key, value); 
  69.         hashmap.put(key, node); 
  70.         addNodeToLast(node); 
  71.     } 

巨人的肩旁:

[1]數(shù)據(jù)結(jié)構(gòu)與算法之美-王爭

[2]力扣-LRU緩存機(jī)制(146題)

[3]https://blog.csdn.net/yangpl_tale/article/details/44998423

[4]https://leetcode-cn.com/problems/lru-cache/solution/146-lru-huan-cun-ji-zhi-ha-xi-biao-shuan-l3um/

 

責(zé)任編輯:武曉燕 來源: 小郎碼知答
相關(guān)推薦

2024-08-19 09:13:02

2020-02-19 19:18:02

緩存查詢速度淘汰算法

2024-06-04 07:38:10

2022-08-18 20:02:04

JSLRU緩存

2021-12-13 09:02:13

localStorag面試前端

2020-09-18 10:31:47

LRU算法數(shù)組

2024-06-05 08:09:56

2024-02-20 14:10:55

系統(tǒng)緩存冗余

2020-05-22 08:11:48

線程池JVM面試

2024-09-03 09:20:45

2020-09-17 17:53:12

面試ArrayList數(shù)組

2021-12-02 08:19:06

MVCC面試數(shù)據(jù)庫

2021-05-06 19:50:14

隊(duì)列機(jī)制

2022-11-15 17:45:46

數(shù)據(jù)庫MySQL

2024-01-19 14:03:59

Redis緩存系統(tǒng)Spring

2024-08-05 01:26:54

2023-02-20 08:08:48

限流算法計(jì)數(shù)器算法令牌桶算法

2020-07-02 07:52:11

RedisHash映射

2021-06-28 17:26:15

歸并排序建模

2021-11-24 10:10:32

axios前端攔截器
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)