Ru Shui

vue - 用 TS 实现一个 LRU 算法

ru shui 2021-10-10 Framework
  • Vue
  • TypeScript
 About 5 min

关于什么是 LRU 算法可以去看 算法就像搭乐高：带你手撸 LRU 算法 (opens new window)。

我们将使用 TypeScript 实现一个属于前端的 LRU 算法，以及在 Vue 源码（Vue2）中的使用。

# 接口定义

interface LRU<Key, Value> {
  get(key: Key): Value | undefined
  put(key: Key, value: Value): void
}
1
2
3
4

# 辅助函数

下面我们就来写一个具体的实现类，然后我们先把框架搭好：

class LRUCache<Key, Value> implements LRU<Key, Value> {
  private static DEFAULT_CAPACITY = 8
  private cache: Key[]
  private map: Map<Key, Value>
  private capacity: number
  constructor(capacity: number = LRUCache.DEFAULT_CAPACITY) {
    this.capacity = capacity > 0 ? capacity : LRUCache.DEFAULT_CAPACITY
    this.cache = []
    this.map = new Map()
  }

  public getCapacity() {
    return this.capacity
  }

  public get(key: Key): Value {
    throw new Error('Method not implemented.')
  }
  public put(key: Key, value: Value): void {
    throw new Error('Method not implemented.')
  }

  private makeRecently(key: Key) {}
  private removeLeastRecently() {}
  private addRecently(key: Key, value: Value) {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

我们将所有的 key 存放在 cache 中，然后通过一个 map 来快速获取 value 值。 LRU 还是控制容量，我们使用 capacity 进行管理。然后通过 this.cache.length >= this.capacity 来判断当前容器是否达到上限。 这里还提供了几个私有的辅助函数，方便等下的调用。

# 实现

# 核心逻辑的实现

class LRUCache<Key, Value> implements LRU<Key, Value> {
  public get(key: Key): Value | undefined {
    if (!this.map.has(key)) {
      return
    }
    this.makeRecently(key)
    return this.map.get(key)
  }

  public put(key: Key, value: Value): void {
    if (this.map.has(key)) {
      this.makeRecently(key)
      // 更新
      this.map.set(key, value)
      return
    }
    // 容量达到上下，删除 least recent used.
    if (this.cache.length >= this.capacity) {
      this.removeLeastRecently()
    }

    this.addRecently(key, value)
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

对于 get 的实现：我们先判断缓存 (map) 中是否存在数据，如果不存在我们就直接返回 undefined。否则，我们在获取之前，我们还需要进行一个更新操作(makeRecently)。

对于 put 的实现：我们先判断缓存 (map) 是否存在数据，如果存在数据，我们需要先执行更新 makeRecently 操作，再进行返回。否则，再插入之前，我们需要看容器容量是否达到上限， 如果达到上限，我们就先删除 least recent used，然后再执行插入操作。

接下来我们就来实现几个辅助函数。

# 辅助函数的实现

class LRUCache<Key, Value> implements LRU<Key, Value> {
  private makeRecently(key: Key) {
    // 由于再 makeRecently 之前，我们就通过 map.has(key) 判断出 存在性。
    // 所以这里可以不用判断 index === -1
    const index = this.cache.indexOf(key)
    this.cache.splice(index, 1)
    this.cache.push(key)
  }
  private removeLeastRecently() {
    // 由于只有当 this.cache.length >= this.capacity 才会调用该方法，、
    // 所以所得到的 key 值是存在的
    const key = this.cache.shift()
    this.map.delete(key)
  }
  private addRecently(key: Key, value: Value) {
    this.cache.push(key)
    this.map.set(key, value)
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 最终代码

export interface LRU<Key, Value> {
  get(key: Key): Value | undefined
  put(key: Key, value: Value): void
}

export class LRUCache<Key, Value> implements LRU<Key, Value> {
  private static DEFAULT_CAPACITY = 8
  private cache: Key[]
  private map: Map<Key, Value>
  private capacity: number
  constructor(capacity: number = LRUCache.DEFAULT_CAPACITY) {
    this.capacity = capacity > 0 ? capacity : LRUCache.DEFAULT_CAPACITY
    this.cache = []
    this.map = new Map()
  }

  public getCapacity() {
    return this.capacity
  }

  public get(key: Key): Value | undefined {
    if (!this.map.has(key)) {
      return
    }
    this.makeRecently(key)
    return this.map.get(key)
  }

  public put(key: Key, value: Value): void {
    if (this.map.has(key)) {
      this.makeRecently(key)
      // 更新
      this.map.set(key, value)
      return
    }
    // 容量达到上下，删除 least recent used.
    if (this.cache.length >= this.capacity) {
      this.removeLeastRecently()
    }

    this.addRecently(key, value)
  }

  private makeRecently(key: Key) {
    // 由于再 makeRecently 之前，我们就通过 map.has(key) 判断出 存在性。
    // 所以这里可以不用判断 index === -1
    const index = this.cache.indexOf(key)
    this.cache.splice(index, 1)
    this.cache.push(key)
  }
  private removeLeastRecently() {
    // 由于只有当 this.cache.length >= this.capacity 才会调用该方法，、
    // 所以所得到的 key 值是存在的
    const key = this.cache.shift()
    this.map.delete(key)
  }
  private addRecently(key: Key, value: Value) {
    this.cache.push(key)
    this.map.set(key, value)
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

# 测试

我们采用 jest 进行简单的测试

import { LRUCache } from './index'

describe('LRUCache', () => {
  const DEFAULT_CAPACITY = 8
  it('should perform the correct init', () => {
    const lru = new LRUCache<number, string>()
    expect(lru.getCapacity()).toBe(DEFAULT_CAPACITY)
    expect(lru.get(1)).toBe(undefined)

    expect(new LRUCache(-1).getCapacity()).toBe(DEFAULT_CAPACITY)
  })

  it('should get value correctly', () => {
    const lru = new LRUCache<number, string>(2)
    lru.put(1, '1')
    expect(lru.get(1)).toBe('1')
    expect(lru.get(2)).toBe(undefined)
    lru.put(2, '2')
    lru.put(3, '3')
    expect(lru.get(1)).toBe(undefined)
    expect(lru.get(2)).toBe('2')
    expect(lru.get(3)).toBe('3')
  })

  it('should put data correctly', () => {
    const lru = new LRUCache<number, string>(2)
    lru.put(1, '1')
    expect(lru.get(1)).toBe('1')
    lru.put(2, '2')
    lru.put(3, '3')
    expect(lru.get(1)).toBe(undefined)
    expect(lru.get(2)).toBe('2')
    expect(lru.get(3)).toBe('3')

    lru.put(4, '4')
    expect(lru.get(2)).toBe(undefined)
    expect(lru.get(3)).toBe('3')

    lru.put(4, '44')
    expect(lru.get(4)).toBe('44')
  })
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

可以看到我们的测试是通过的(这里用 tsc 编译再测试)。

img

# Vue2 中的使用

Vue 在内置组件 keep-alive 就采用了 LRU 算法对缓存进行管理，对比一下 render 方法可以看到这个算法的影子：

// vue/src/core/components/keep-alive.js
  render () {
    const slot = this.$slots.default
    const vnode: VNode = getFirstComponentChild(slot)
    const componentOptions: ?VNodeComponentOptions = vnode && vnode.componentOptions
    if (componentOptions) {
      // check pattern
      const name: ?string = getComponentName(componentOptions)
      const { include, exclude } = this
      if (
        // not included
        (include && (!name || !matches(include, name))) ||
        // excluded
        (exclude && name && matches(exclude, name))
      ) {
        return vnode
      }

      const { cache, keys } = this
      const key: ?string = vnode.key == null
        // same constructor may get registered as different local components
        // so cid alone is not enough (#3269)
        ? componentOptions.Ctor.cid + (componentOptions.tag ? `::${componentOptions.tag}` : '')
        : vnode.key
      if (cache[key]) {
        vnode.componentInstance = cache[key].componentInstance
        // make current key freshest
        remove(keys, key)
        keys.push(key)
      } else {
        cache[key] = vnode
        keys.push(key)
        // prune oldest entry
        if (this.max && keys.length > parseInt(this.max)) {
          pruneCacheEntry(cache, keys[0], keys, this._vnode)
        }
      }

      vnode.data.keepAlive = true
    }
    return vnode || (slot && slot[0])
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 总结

LRU 是一个高效的获取和管理数据的算法。其实我们上面的实现还可以进一步的优化， 可以将 cache 数组改用一个双向链表实现。但是对于 capacity 要求不高的 条件下，其实算法的效率也是非常快的。

# Reference

Last update: October 10, 2021 13:29
Contributors: Laishuxin

Ru Shui

MIT Licensed | Copyright © 2021-present Ru Shui