什麼是 LFU 演算法?

語言: CN / TW / HK

上次的文章介紹了 LRU 演算法,今天打算來介紹一下 LFU 演算法。在上篇文章中有提到, LFU( Least frequently used :最少使用)演算法與 LRU 演算法只是在淘汰策略上有所不同,LRU 傾向於保留最近有使用的資料,而 LFU 傾向於保留使用頻率較高的資料。

舉一個簡單的:chestnut::快取中有 A、B 兩個資料,且已達到上限,如果 資料 A 先被訪問了 10 次,然後 資料 B 被訪問 1 次,當存入新的 資料 C 時,如果當前是 LRU 演算法,會將 資料 A 淘汰,而如果是 LFU 演算法,則會淘汰 資料 B

簡單來說,就是在 LRU 演算法中,不管訪問的頻率,只要最近訪問過,就不會將這個資料淘汰,而在 LFU 演算法中,將訪問的頻率作為權重,只要訪問頻率越高,該資料就越不會被淘汰,即使該資料很久沒有被訪問過。

我們還是通過一段 JavaScript 程式碼來實現這個邏輯。

class LFUCache {
	freqs = {} // 用於標記訪問頻率
	cache = {} // 用於快取所有資料
	capacity = 0 // 快取的最大容量
	constructor (capacity) {
    // 儲存 LFU 可快取的最大容量
		this.capacity = capacity
	}
}

與 LRU 演算法一樣,LFU 演算法也需要實現 getput 兩個方法,用於獲取快取和設定快取。

class LFUCache {
  // 獲取快取
	get (key) { }
  // 設定快取
	put (key, value) { }
}

老規矩,先看設定快取的部分。如果該快取的 key 之前存在,需要更新其值。

class LFUCache {
  // cache 作為快取的儲存物件
  // 其解構為: { key: { freq: 0, value: '' } }
  // freq 表示該資料讀取的頻率;
  // value 表示快取的資料;
	cache = {}
  // fregs 用於儲存快取資料的頻率
  // 其解構為: { 0: [a], 1: [b, c], 2: [d] }
  // 表示 a 還沒被讀取,b/c 各被讀取1次,d被讀取2次
  freqs = {}
  // 設定快取
  put (key, value) {
    // 先判斷快取是否存在
    const cache = this.cache[key]
    if (cache) {
      // 如果存在,則重置快取的值
      cache.value = value
      // 更新使用頻率
      let { freq } = cache
      // 從 freqs 中獲取對應 key 的陣列
      const keys = this.freqs[freq]
      const index = keys.indexOf(key)
      // 從頻率陣列中,刪除對應的 key
      keys.splice(index, 1)
      if (keys.length === 0) {
        // 如果當前頻率已經不存在 key
        // 將 key 刪除
        delete this.freqs[freq]
      }
      // 更新頻率加 1
      freq = (cache.freq += 1)
      // 更新頻率陣列
      const freqMap =
            this.freqs[freq] ||
            (this.freqs[freq] = [])
      freqMap.push(key)
      return
    }
  }
}

如果該快取不存在,要先判斷快取是否超過容量,如果超過,需要淘汰掉使用頻率最低的資料。

class LFUCache {
  // 更新頻率
  active (key, cache) {
    // 更新使用頻率
    let { freq } = cache
    // 從 freqs 中獲取對應 key 的陣列
    const keys = this.freqs[freq]
    const index = keys.indexOf(key)
    // 從頻率陣列中,刪除對應的 key
    keys.splice(index, 1)
    if (keys.length === 0) {
      // 如果當前頻率已經不存在 key
      // 將 key 刪除
      delete this.freqs[freq]
    }
    // 更新頻率加 1
    freq = (cache.freq += 1)
    // 更新讀取頻率陣列
    const freqMap = this.freqs[freq] || (this.freqs[freq] = [])
    freqMap.push(key)
  }
  // 設定快取
  put (key, value) {
    // 先判斷快取是否存在
    const cache = this.cache[key]
    if (cache) {
      // 如果存在,則重置快取的值
      cache.value = value
      this.active(key, cache)
      return
    }
    // 判斷快取是否超過容量
    const list = Object.keys(this.cache)
    if (list.length >= this.capacity) {
      // 超過儲存大小,刪除訪問頻率最低的資料
      const [first] = Object.keys(this.freqs)
      const keys = this.freqs[first]
      const latest = keys.shift()
      delete this.cache[latest]
      if (keys.length === 0) delete this.freqs[latest]
    }
    // 寫入快取,預設頻率為0,表示還未使用過
    this.cache[key] = { value, freq: 0 }
    // 寫入讀取頻率陣列
    const freqMap = this.freqs[0] || (this.freqs[0] = [])
    freqMap.push(key)
  }
}

實現了設定快取的方法後,再實現獲取快取就很容易了。

class LRUCache {
  // 獲取資料
	get (key) {
		if (this.cache[key] !== undefined) {
    	// 如果 key 對應的快取存在,更新其讀取頻率
      // 之前已經實現過,可以直接複用
			this.active(key)
			return this.cache[key]
		}
		return undefined
  }
}

關於 LFU 快取演算法實現就到這裡了,當然該演算法一般使用雙鏈表的形式來實現,這裡的實現方式,只是為了方便理解其原理,感興趣的話可以在網上搜索下更加高效的實現方式。