Gahing's blog
gahing
2020/03/31
随笔 2020
目录

面试官问：能否实现一个缓存计算结果的方法

# 背景

// 模拟耗时任务
function taskA (n, initialValue, incre) {
  let result = initialValue
  for (let i = 0; i < n; i++) {
    result += incre
  }
  return result
}
function cache (callback) {
  // ...
  return function () {
    console.time('task')
    // ...
    console.timeEnd('task')
  }
}
let taskACache = cache(taskA)
taskACache(1e+9, 0, 1) // 1.5s
taskACache(1e+9, 0, 1) // 0s
taskACache(1e+9, 2, 1) // 1.5s
taskACache(1e+9, 2, 1) // 0s
taskACache(1e+9, 0, 1) // 0s

let taskBCache = cache(taskB)
taskBCache('abc', 123, { a: 1, b: 2 }) // 5s
taskBCache('abc', 123, { b: 2, a: 1 }) // 0s
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

完善 cache 方法，使得相同参数调用时能够快速响应结果

注意：

  • 相同参数需要进行深度比较， {a:1,b:2} 和 {b:2,a:1} 属于参数不变的情况
  • 属性值仅需考虑基本类型和纯对象(typeof is object)，且不考虑循环引用的问题

# 分析

先不考虑 Web Worker 和 Node.js 多线程 ，我们先考虑单线程应该如何实现

同种任务参数不同可以被缓存多次，因此每次执行任务时先判断是否存在相同的参数列表

直观的想法是维护一个数组，数组元素为参数列表，每次都需要遍历数组元素逐一比较，这是 O(n) 的时间复杂度

那么有什么其他方法么？

# json + map

对参数列表应用 JSON.stringify ，其结果 json 作为 map 的 key

需要保证

  • 不同的参数列表生成的 key 是不同的
  • 相同的参数列表生成的 key 始终一致

对于下面 2 组，虽然参数列表是相同的，但是由于对象中属性的位置不一致

console.log(JSON.stringify(['abc', 123, { a: 1, b: 2 }]))
// ["abc",123,{"a":1,"b":2}]
console.log(JSON.stringify(['abc', 123, { b: 2, a: 1 }]))
// ["abc",123,{"b":2,"a":1}]
1
2
3
4

简单应用 JSON.stringify 会得到不同结果

需要借用第二个参数 replacer 进行对象的处理

function replacer (key, value) {
  const isPureObject = typeof value === 'object' && value !== null && !Array.isArray(value)
  if (!isPureObject) {
    return value
  }
  return Object
    .entries(value)
    .sort(([a], [b]) => +(a > b) || +(a === b) - 1)
    .reduce((_sortedObj, [k, v]) => ({
      ..._sortedObj,
      [k]: v
    }), {})
}
console.log(JSON.stringify(['abc', 123, { a: 1, b: 2 }], replacer))
// ["abc",123,{"a":1,"b":2}]
console.log(JSON.stringify(['abc', 123, { b: 2, a: 1 }], replacer))
// ["abc",123,{"a":1,"b":2}]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

将计算结果放入 map 即可

function replacer (key, value) {
  const isObject = typeof value === 'object' && value !== null && !Array.isArray(value)
  if (!isObject) {
    return value
  }
  return Object
    .entries(value)
    .sort(([a], [b]) => +(a > b) || +(a === b) - 1)
    .reduce((_sortedObj, [k, v]) => ({
      ..._sortedObj,
      [k]: v
    }), {})
}
function cache (callback) {
  let map = new Map()
  return function (...args) {
    console.time('task')
    try {
      const json = JSON.stringify(args, replacer)
      let result = map.get(json)
      if (result !== void 0) {
        return result
      }
      result = callback.apply(null, args)
      map.set(json, result)
      return result
    } catch (error) {

    } finally {
      console.timeEnd('task')
    }

  }
}
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

测试用例

// 模拟耗时任务
function taskA (n, { initialValue, incre }) {
  let result = initialValue
  for (let i = 0; i < n; i++) {
    result += incre
  }
  return result
}
let taskACache = cache(taskA)
console.log(taskACache(1e+9, { initialValue: 0, incre: 1 }))
console.log(taskACache(1e+9, { incre: 1, initialValue: 0 }))
console.log(taskACache(1e+9, { initialValue: 2, incre: 1 }))
console.log(taskACache(1e+9, { initialValue: 2, incre: 1 }))
console.log(taskACache(1e+9, { initialValue: 0, incre: 1 }))
/*
task: 2050.12890625ms
1000000000
task: 0.097900390625ms
1000000000
task: 2088.137939453125ms
1000000002
task: 0.0810546875ms
1000000002
task: 0.042724609375ms
1000000000
*/
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

还能继续优化？

当缓存的数据量足够大时，既占用内存，还拖慢查询速度，我们上 LRUCache

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) {
    return
  } else {
    let value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.set = function (key, value) {

  if (!this.map.has(key)) {
    if (this.map.size >= this.capacity) {
      // 删除首个节点
      this.map.delete(this.map.keys().next().value)
    }
    this.map.set(key, value)
  } else {
    this.map.delete(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

实现原理请看 实现一个 LRU-K (opens new window)

修改下 cache 的实现

function replacer (key, value) {
  const isObject = typeof value === 'object' && value !== null && !Array.isArray(value)
  if (!isObject) {
    return value
  }
  return Object
    .entries(value)
    .sort(([a], [b]) => +(a > b) || +(a === b) - 1)
    .reduce((_sortedObj, [k, v]) => ({
      ..._sortedObj,
      [k]: v
    }), {})
}
function cache (callback) {
  // 设置容量
  let map = new LRUCache(2)
  return function (...args) {
    console.time('task')
    try {
      const json = JSON.stringify(args, replacer)
      let result = map.get(json)
      if (result !== void 0) {
        return result
      }
      result = callback.apply(null, args)
      map.set(json, result)
      return result
    } catch (error) {

    } finally {
      console.timeEnd('task')
    }

  }
}
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

再次进行测试

// 模拟耗时任务
function taskA (n, { initialValue, incre }) {
  let result = initialValue
  for (let i = 0; i < n; i++) {
    result += incre
  }
  return result
}
let taskACache = cache(taskA)
console.log(taskACache(1e+9, { initialValue: 0, incre: 1 }))
console.log(taskACache(1e+9, { incre: 1, initialValue: 0 }))
console.log(taskACache(1e+9, { initialValue: 2, incre: 1 }))
console.log(taskACache(1e+9, { initialValue: 2, incre: 1 }))
console.log(taskACache(1e+9, { initialValue: 3, incre: 1 }))
console.log(taskACache(1e+9, { initialValue: 0, incre: 1 }))
/*
task: 2190.304931640625ms
1000000000
task: 0.12890625ms
1000000000
task: 2263.181884765625ms
1000000002
task: 0.123779296875ms
1000000002
task: 2218.0888671875ms
1000000003
task: 2395.6279296875ms
1000000000
*/
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

注意最后一个例子，计算结果已被 lru 移除

# hashMap

万物均可 hash
        -- 鲁迅
1
2

将参数列表进行哈希得到 hashCode ，并作为 hashMap 的 key

hashMap 的 value 是实体为参数列表与计算值的链表，链表较长则上红黑树

接下来就是 hashCode 的计算，需要明确的是：

  • 相同的参数列表生成的 hashCode 始终一致
  • 由于无需保证不同的参数列表生成的 hashCode 不一致，因此 hashCode 的计算应尽可能快

这里简单使用如下计算规则

  • Object
    • 数组，其 hashCode 为每一项的 hashCode 的累加
    • , 其 hashCode 为 -1
    • 纯对象，其 hashCode 为按属性升序后每一项的值的 hashCode 的累加
  • undefined, 其 hashCode 为 -1
  • Number
    • NaN, 其 hashCode 为 -1
    • Infinity, 其 hashCode 为 0xffff
    • 其他，其 hashCode 为自身值
  • String，其 hashCode 为 charCode 累加
  • Boolean，true 为 1，false 为 0

每次执行任务前先查询是否存在 hashCode ，存在的话在对链表中每一项进行深比较查询

该算法的要点在于找到一个合理的 hash 算法，减少 hash 冲突避免深比较

代码实现略。

# 上多线程

为避免阻塞主线程的事件循环，我们将耗时任务放到其他线程中进行

先上一版，再分析漏洞


/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) {
    return
  } else {
    let value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.set = function (key, value) {

  if (!this.map.has(key)) {
    if (this.map.size >= this.capacity) {
      // 删除首个节点
      this.map.delete(this.map.keys().next().value)
    }
    this.map.set(key, value)
  } else {
    this.map.delete(key)
    this.map.set(key, value)
  }
};
function replacer (key, value) {
  const isObject = typeof value === 'object' && value !== null && !Array.isArray(value)
  if (!isObject) {
    return value
  }
  return Object
    .entries(value)
    .sort(([a], [b]) => +(a > b) || +(a === b) - 1)
    .reduce((_sortedObj, [k, v]) => ({
      ..._sortedObj,
      [k]: v
    }), {})
}


// 构建 worker

function createWorker (taskContent, taskName) {
  let text = `
  ${taskContent}
  this.addEventListener('message', (msg) => {
    const result = this['${taskName}'].apply(this,msg.data)
    postMessage(result);
  }, false);
  `
  let blob = new Blob([text]);
  let url = window.URL.createObjectURL(blob);
  return new Worker(url);
}


function cache (task) {
  // 设置容量
  let map = new LRUCache(2)
  let worker = createWorker(task.toString(), task.name)
  return function (...args) {
    return new Promise((resolve, reject) => {
      console.time('task')
      try {
        const json = JSON.stringify(args, replacer)
        let result = map.get(json)
        if (result !== void 0) {
          resolve(result)
          console.timeEnd('task')
          return
        }
        worker.onmessage = (evt) => {
          map.set(json, evt.data)
          resolve(evt.data)
          console.timeEnd('task')
        };
        worker.postMessage(args);
      } catch (error) {
        reject(error)
      }
    })
  }
}

// 模拟耗时任务
// 仅考虑函数声明
function taskA (n, { initialValue, incre }) {
  let result = initialValue
  for (let i = 0; i < n; i++) {
    result += incre
  }
  return result
}

let taskACache = cache(taskA)
console.log(await taskACache(1e+9, { initialValue: 0, incre: 1 }))
console.log(await taskACache(1e+9, { incre: 1, initialValue: 0 }))
console.log(await taskACache(1e+9, { initialValue: 2, incre: 1 }))
console.log(await taskACache(1e+9, { initialValue: 2, incre: 1 }))
console.log(await taskACache(1e+9, { initialValue: 3, incre: 1 }))
console.log(await taskACache(1e+9, { initialValue: 0, incre: 1 }))
/*
task: 2196.513916015625ms
1000000000
task: 0.123046875ms
1000000000
task: 2287.091796875ms
1000000002
task: 0.10791015625ms
1000000002
task: 2272.23193359375ms
1000000003
task: 2178.444091796875ms
1000000000
*/
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

执行结果与单线程一致，且不阻塞主线程

那么，有什么问题吗？

首先，为了拓展性，将 task 内容传递到 worker 中，这里需要要求为函数声明，对于函数表达式或重写 toString 等情况无法正常处理

其次，这里通过 await 保证了 taskACache 按序执行，实际场景中可能存在多个同时执行的 worker ，且还有可能是参数列表一样的，导致 worker 重复计算

taskACache(1e+9, { initialValue: 0, incre: 1 })
taskACache(1e+9, { initialValue: 0, incre: 1 })
/*
A  ->f(1)不在缓存->[   计算f(1)    ]->将f(1)放入缓存
B  ----------->f(1)不在缓存->[   计算f(1)    ]->将f(1)放入缓存
*/
1
2
3
4
5
6

对于问题1无非就是做下兼容，或者直接约定仅支持函数声明，再或者将 self.postMessage 放置在任务方法中，这个无关紧要，重点是问题2，如何处理？

参考 Java FutureTask 的做法，即

FutureTask 表示一个计算的过程，可能已经计算完成，也可能正在进行。如果有结果可用，那么 FutureTask.get 将立即返回结果，否则会一直堵塞，直到计算结果出来再将其返回

在 js 中相像的就是 Promise 了

代码如下：


/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) {
    return
  } else {
    let value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.set = function (key, value) {

  if (!this.map.has(key)) {
    if (this.map.size >= this.capacity) {
      // 删除首个节点
      this.map.delete(this.map.keys().next().value)
    }
    this.map.set(key, value)
  } else {
    this.map.delete(key)
    this.map.set(key, value)
  }
};
function replacer (key, value) {
  const isObject = typeof value === 'object' && value !== null && !Array.isArray(value)
  if (!isObject) {
    return value
  }
  return Object
    .entries(value)
    .sort(([a], [b]) => +(a > b) || +(a === b) - 1)
    .reduce((_sortedObj, [k, v]) => ({
      ..._sortedObj,
      [k]: v
    }), {})
}


// 构建 worker

function createWorkerUrl (taskContent, taskName) {
  let text = `
  ${taskContent}
  this.addEventListener('message', (msg) => {
    const result = this['${taskName}'].apply(this,msg.data)
    postMessage(result);
  }, false);
  `
  let blob = new Blob([text]);
  let url = window.URL.createObjectURL(blob);
  return url
}


function cache (task) {
  // 设置容量
  let map = new LRUCache(2)
  const url = createWorkerUrl(task.toString(), task.name)
  return function (...args) {
    let startTime = performance.now()
    const json = JSON.stringify(args, replacer)
    let result = map.get(json)
    if (result !== void 0) {
      console.log('task: ', performance.now() - startTime, 'ms')
      return result
    }
    let worker = new Worker(url)
    let promise = new Promise((resolve, reject) => {
      try {
        worker.onmessage = (evt) => {
          resolve(evt.data)
          console.log('task: ', performance.now() - startTime, 'ms')
        };
        worker.postMessage(args);
      } catch (error) {
        reject(error)
      }
    })
    map.set(json, promise)
    return promise
  }
}

// 模拟耗时任务
// 仅考虑函数声明
function taskA (n, { initialValue, incre }) {
  let result = initialValue
  for (let i = 0; i < n; i++) {
    result += incre
  }
  return result
}

let taskACache = cache(taskA)
console.log(taskACache(1e+9, { initialValue: 0, incre: 1 }).then(res => console.log('{ initialValue: 0, incre: 1 } => ',res)))
console.log(taskACache(1e+9, { incre: 1, initialValue: 0 }).then(res => console.log('{ incre: 1, initialValue: 0 } => ',res)))
console.log(taskACache(1e+9, { initialValue: 2, incre: 1 }).then(res => console.log('{ initialValue: 2, incre: 1 } => ',res)))
console.log(taskACache(1e+9, { initialValue: 2, incre: 1 }).then(res => console.log('{ initialValue: 2, incre: 1 } => ',res)))
console.log(taskACache(1e+9, { initialValue: 3, incre: 1 }).then(res => console.log('{ initialValue: 3, incre: 1 } => ',res)))
console.log(taskACache(1e+9, { initialValue: 0, incre: 1 }).then(res => console.log('{ initialValue: 0, incre: 1 } => ',res)))
/*
Promise {<pending>}
task:  0.11500000255182385 ms
Promise {<pending>}
Promise {<pending>}
task:  0.1399999891873449 ms
Promise {<pending>}
Promise {<pending>}
Promise {<pending>}

task:  3322.7050000132294 ms
{ initialValue: 0, incre: 1 } =>  1000000000
{ incre: 1, initialValue: 0 } =>  1000000000
task:  3370.5150000023423 ms
{ initialValue: 2, incre: 1 } =>  1000000002
{ initialValue: 2, incre: 1 } =>  1000000002
task:  3772.9699999908917 ms
{ initialValue: 0, incre: 1 } =>  1000000000
task:  4013.5900000022957 ms
{ initialValue: 3, incre: 1 } =>  1000000003
*/
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

第二个任务和第四个任务命中了缓存，返回已缓存的 promise

单个 task 耗时看似增加了，这是由于并发执行 Worker 导致的，整体耗时反而减少了

# 其他注意点

由于 js 主线程是单线程，因此不用考虑先检查缓存再执行这一非原子性操作

# 拓展阅读

  1. Web Worker 使用教程 (opens new window)
  2. 动手写一个并发缓存框架 历程 (opens new window)

原文地址： https://github.com/francecil/leetcode/issues/38

编辑 (opens new window)
#ECMAScript#WebWorker
上次更新: 2024/09/01, 23:56:56
最近更新
01
浅谈代码质量与量化指标
08-27
02
快速理解 JS 装饰器
08-26
03
Vue 项目中的 data-v-xxx 是怎么生成的
09-19
更多文章>
Theme by Vdoing | Copyright © 2016-2024 Gahing | 闽ICP备19024221号-1