LFU缓存

[YBFACC]

LFU缓存

为了实现O（1）时间复杂度，此题需要使用双向链表。

需要使用map来快速获取双向链表的值

需要使用frequentMap来获取同频率的所有节点。

需要维护一个变量minFreq来指向frequentMap中频率最低

更新minFreq的时机：节点已经从原链表中删除，节点插入到新链表之后

• get：看map中是否有key？
  • 有=>从x频率中删除，放到x+1频率的首部。（更新minFreq）
  • 无=>返回-1
• put：看map中是否有key？
  • 有=>从x频率中删除，放到x+1频率的首部，更新value。（更新minFreq）
  • 无=>是否超出容量上限
    • 是=>删除使用频率最少，时间最久远的
    • 无=>容量+1
    • finally=>new 一个新节点，将其放入map中和频率为1的链表首部。（minFreq=1）

此图作者：liweiwei1419

链接：https://leetcode-cn.com/problems/lfu-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiwei/

class linkedTwo {
  pre: linkedTwo | undefined
  next: linkedTwo | undefined
  key: number
  val: number
  times: number
  constructor(key: number, val: number) {
    this.key = key
    this.val = val
    this.pre
    this.next
    this.times = 1
  }
  delete(): void {
    const pre = this.pre as linkedTwo
    const next = this.next as linkedTwo
    pre.next = next
    next.pre = pre
  }
}

class LFUCache {
  getLinked: Map<number, linkedTwo>
  frequentMap: Map<number, LFUitem>
  max: number
  cache_num: number
  minFreq: number
  constructor(capacity: number) {
    this.max = capacity
    this.frequentMap = new Map()
    this.getLinked = new Map()
    this.cache_num = 0
    this.minFreq = 1
  }

  get(key: number): number {
    if (this.getLinked.has(key)) {
      const linked = this.getLinked.get(key) as linkedTwo
      this.move(linked)
      return linked.val
    }
    return -1
  }

  put(key: number, value: number): void {
    const frequentMap = this.frequentMap
    if (this.getLinked.has(key)) {
      const linked = this.getLinked.get(key) as linkedTwo
      linked.val = value
      this.move(linked)
    } else {
      if (this.cache_num >= this.max && this.max >= 1) {
        let item = frequentMap.get(this.minFreq) as LFUitem
        const temp = item.delete_Tail()
        this.getLinked.set(key, this.insert_linked(key, value))
        this.getLinked.delete(temp)
      } else if (this.cache_num < this.max) {
        this.getLinked.set(key, this.insert_linked(key, value))
        this.cache_num++
      }

    }

  }
  move(linked: linkedTwo): void {
    const frequentMap = this.frequentMap
    linked.delete()
    linked.times++
    this.add_frequentMap(linked)
    this.updata_minFreq(frequentMap.get(linked.times - 1) as LFUitem, linked.times - 1)
  }
  insert_linked(key: number, value: number): linkedTwo {
    const target = new linkedTwo(key, value)
    this.minFreq = 1
    this.add_frequentMap(target)
    return target
  }
  add_frequentMap(linked: linkedTwo): void {
    const frequentMap = this.frequentMap
    const index = linked.times
    if (!frequentMap.has(index)) {
      frequentMap.set(index, new LFUitem())
    }
    const item = frequentMap.get(index) as LFUitem
    item.insert_tump(linked)
  }
  updata_minFreq(item: LFUitem | undefined, index: number): void {
    if (!item) return
    const frequentMap = this.frequentMap
    if (item.nothing()) {
      frequentMap.delete(index)
      if (frequentMap.size === 0) {
        this.minFreq = 1
        return
      }
      while (!frequentMap.has(this.minFreq)) {
        this.minFreq++
      }
    }
  }

}

class LFUitem {
  tump: linkedTwo
  tail: linkedTwo
  constructor() {
    this.tump = new linkedTwo(NaN, NaN)
    this.tail = new linkedTwo(NaN, NaN)
    this.tump.next = this.tail
    this.tail.pre = this.tump
  }
  insert_tump(linked: linkedTwo): void {
    const temp = this.tump.next as linkedTwo
    linked.pre = this.tump
    this.tump.next = linked
    linked.next = temp
    temp.pre = linked
  }
  delete_Tail(): number {
    const target = this.tail.pre as linkedTwo
    const pre = target.pre as linkedTwo
    pre.next = this.tail
    this.tail.pre = pre
    return target.key
  }
  nothing(): boolean {
    const tump = this.tump
    const tail = this.tail
    if (tump.next === tail) {
      return true
    }
    return false
  }
}

使用双向链表代替frequentMap

使用双向链表代替frequentMap，可以省去minFreq变量。

原本更新minFreq的时间复杂度在最坏的情况下，不是O（1）

class linked_list {
  tump: linked_item
  tail: linked_item
  constructor(frequent: frequentItem) {
    this.tump = new linked_item(NaN, NaN, frequent)
    this.tail = new linked_item(NaN, NaN, frequent)
    this.tump.next = this.tail
    this.tail.pre = this.tump
  }
  insert_tump(linked: linked_item): void {
    const temp = this.tump.next as linked_item
    linked.pre = this.tump
    this.tump.next = linked
    linked.next = temp
    temp.pre = linked
  }
  delete_Tail(): number {
    const target = this.tail.pre as linked_item
    const pre = target.pre as linked_item
    pre.next = this.tail
    this.tail.pre = pre
    return target.key
  }
  nothing(): boolean {
    const tump = this.tump
    const tail = this.tail
    if (tump.next === tail) {
      return true
    }
    return false
  }
}
class linked_item {
  pre: linked_item | undefined
  next: linked_item | undefined
  key: number
  val: number
  frequent: frequentItem | undefined
  constructor(key: number, val: number, frequent?: frequentItem) {
    this.key = key
    this.val = val
    this.pre
    this.next
    this.frequent = frequent
  }
  delete(): void {
    const pre = this.pre as linked_item
    const next = this.next as linked_item
    pre.next = next
    next.pre = pre
  }
}

class frequent_list {
  start: frequentItem
  end: frequentItem
  constructor() {
    this.start = new frequentItem(NaN)
    this.end = new frequentItem(NaN)
    this.start.next = this.end
    this.end.pre = this.start
  }
  insert(linked: linked_item) {
    if (this.start?.next?.key !== 1) {
      this.start.add_frequentItem(1)
    }
    const one = this.start.next as frequentItem
    linked.frequent = one
    one.item.insert_tump(linked)
  }
  delete(): number {
    const target = this.start.next as frequentItem
    if (target.key === NaN) return -1
    const key = target.item.delete_Tail()
    target.delete_frequentItem()
    return key
  }
}

class frequentItem {
  pre: frequentItem | undefined
  next: frequentItem | undefined
  item: linked_list
  key: number
  constructor(key: number) {
    this.pre
    this.next
    this.item = new linked_list(this)
    this.key = key
  }
  next_item(linked: linked_item) {
    if (this.next?.key !== this.key + 1) {
      this.add_frequentItem(this.key + 1)
    }
    const next_linked_list = this.next?.item!
    linked.frequent = this.next!
    next_linked_list.insert_tump(linked)
    this.delete_frequentItem()
  }
  add_frequentItem(key: number) {
    const next = this.next as frequentItem
    const new_item = new frequentItem(key)
    this.next = new_item
    new_item.pre = this

    new_item.next = next
    next.pre = new_item
  }
  delete_frequentItem() {
    const linked_list = this.item as linked_list
    if (linked_list.nothing()) {
      const pre = this.pre as frequentItem
      const next = this.next as frequentItem
      pre.next = next
      next.pre = pre
    }
  }
}

class LFUCache {
  linked_item: Map<number, linked_item>
  frequent_list: frequent_list
  capacity: number
  cache_num: number
  constructor(capacity: number) {
    this.cache_num = 0
    this.capacity = capacity
    this.linked_item = new Map()
    this.frequent_list = new frequent_list()
  }
  get(key: number): number {
    const map = this.linked_item
    if (map.has(key)) {
      const target = map.get(key) as linked_item
      this.move(target)
      return target.val
    }
    return -1
  }
  put(key: number, value: number): void {
    const map = this.linked_item
    if (this.capacity === 0) return
    if (map.has(key)) {
      const target = map.get(key) as linked_item
      target.val = value
      this.move(target)
    } else {
      const frequent_list = this.frequent_list
      if (this.cache_num === this.capacity) {
        const key = frequent_list.delete()
        map.delete(key)
      } else {
        this.cache_num++
      }
      const target = new linked_item(key, value)
      map.set(key, target)
      frequent_list.insert(target)
    }
  }
  move(linked: linked_item) {
    const frequent = linked.frequent as frequentItem
    linked.delete()
    frequent.next_item(linked)
  }
}