FrankKai.github.io
FrankKai.github.io copied to clipboard
如何实现一个缓存函数?
- 记忆一次缓存
- 记忆所有缓存
- LRU缓存
- 低性能版(栈+Map)
- 性能较好版(Map)
- WeakMap式缓存(入参为对象类型的缓存且方便浏览器垃圾回收)
实现一个缓存函数
记忆一次缓存
记忆化的意思就是:对于纯函数来说,相同输入产生相同输出。那么如果多次调用输入没有变化的函数时,产生的结果都是相同的,函数体内代码的多次执行是没有意义的,如果使得函数记忆住入参及其结果,下一次调用时直接返回结果即可。
function memoize(fn) {
var cachedArg;
var cachedResult;
return function(arg) {
if (cachedArg === arg) {
return cachedResult;
}
cachedArg = arg;
cachedResult = fn(arg);
return cachedResult;
};
}
let testFn = (foo) => foo + 999
let memoizeFn = memoize(testFn)
memoizeFn(1) // 首次计算需要调用testFn,同时生成缓存
memoizeFn(1) // 取缓存结果
memoizeFn(1) // 取缓存结果
memoizeFn(2) // 重新计算,缓存重置
memoizeFn(2) // 取缓存结果
memoizeFn(1) // 重新计算,缓存重置
记录所有缓存
function memoizeMap(fn) {
const map = new Map();
return function (arg) {
if (map.has(arg)) {
return map.get(arg);
}
const cachedArg = arg;
const cachedResult = fn(arg);
map.set(cachedArg, cachedResult)
return cachedResult;
};
}
let testFn = (foo) => foo + 999;
let memoizeMapFn = memoizeMap(testFn);
memoizeMapFn(1) // map对arg 1生成缓存
memoizeMapFn(1) // 取缓存结果
memoizeMapFn(1) // 取缓存结果
memoizeMapFn(2) // map对arg 2生成缓存
memoizeMapFn(2) // 取缓存结果
memoizeMapFn(1) // 取缓存结果
LRU缓存
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。
当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
题目:https://leetcode-cn.com/problems/lru-cache/ 题解:https://github.com/FrankKai/leetcode-js/blob/master/146.LRU_Cache.js
低性能版(栈+Map)
/**
* 解题思路:利用栈(栈顶栈底),Map记录值的特性实现LRU缓存机制
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.stack = [];
this.map = new Map();
};
LRUCache.prototype.get = function (key) {
if (this.map.has(key)) {
const index = this.stack.findIndex((item) => item.key === key)
this.stack.unshift(this.stack.splice(index, 1)[0]);
return this.map.get(key);
}
return -1;
};
LRUCache.prototype.put = function (key, value) {
// 存储相同key时的处理
if (this.map.has(key)) {
const index = this.stack.findIndex((item) => item.key === key)
// 替换value并移动到栈底
this.stack[index].value = value;
this.stack.unshift(this.stack.splice(index, 1)[0]);
// 更新key的值
this.map.set(key, value)
return;
}
if (this.map.size === this.capacity) {
this.map.delete(this.stack.pop().key);
}
this.map.set(key, value);
this.stack.unshift({ key, value })
};
性能较好版(Map)
/**
* 解题思路:利用Map的key具有顺序的特性实现LRU缓存机制
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.map = new Map();
};
LRUCache.prototype.get = function (key) {
if (this.map.has(key)) {
const value = this.map.get(key);
this.map.delete(key);
this.map.set(key, value);
return value;
}
return -1;
};
LRUCache.prototype.put = function (key, value) {
if (this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
if (this.map.size > this.capacity) {
this.map.delete(this.map.keys().next().value);
}
};
WeakMap式缓存(入参为对象类型的缓存且方便浏览器垃圾回收)
function memoizeWeakMap(fn) {
const wm = new WeakMap();
return function (arg) {
if (wm.has(arg)) {
return wm.get(arg);
}
const cachedArg = arg;
const cachedResult = fn(arg);
wm.set(cachedArg, cachedResult)
console.log('weakmap object', wm)
return cachedResult;
};
}
let testFn = (bar) => {return Object.prototype.toString.call(bar)}; // 这里需要改造一下,改造完返回传入对象的类型
let memoizeWeakMapFn = memoizeWeakMap(testFn);
memoizeWeakMapFn(document) // weakmap对document生成缓存
memoizeWeakMapFn([1,2,3]) // weakmap对[1,2,3]生成缓存
memoizeWeakMapFn(function(){}) // weakmap对function(){}生成缓存
memoizeWeakMapFn(new WeakMap()) // weakmap对WeakMap实例生成缓存
memoizeWeakMapFn(new Map()) // weakmap对Map实例生成缓存
memoizeWeakMapFn(new Set()) // weakmap对Set实例生成缓存
WeakMap:
0: {Array(3) => "[object Array]"}
1: {function(){} => "[object Function]"}
2: {WeakMap => "[object WeakMap]"}
3: {Map(0) => "[object Map]"}
4: {#document => "[object HTMLDocument]"}
5: {Set(0) => "[object Set]"}
如何体现出WeakMap的垃圾回收特性呢
// 忽略部分代码同上
setTimeout(()=>{
memoizeWeakMapFn(document)
},5000)
此时有时最后一次weakmap的打印结果如下:
WeakMap:
0: {#document => "[object HTMLDocument]"}
为什么说是“有时”?
因为打印时垃圾回收可能并没有执行完成,虽然会带来不确定性,但是可以确定的是,假设对象没有再被引用,WeakMap中的key会被浏览器自动垃圾回收掉。
为什么weakmap中仅保存了document?
这是因为[1,2,3], function(){},new WeakMap(),new Map(),new Set()在后面都没有再继续引用了,而且因为它们作为了WeakMap的key,所以会被浏览器自动垃圾回收掉。
如何不让key被垃圾回收掉呢?
保持一个变量对它的引用。
let memoizeWeakMapFn = memoizeWeakMap(testFn);
let retainArray = [1,2,3]; // 保持引用避免被垃圾回收
let retainMap = new Map(); // 保持引用避免被垃圾回收
memoizeWeakMapFn(document) // weakmap对document生成缓存
memoizeWeakMapFn(retainArray) // weakmap对[1,2,3]生成缓存
memoizeWeakMapFn(function(){}) // weakmap对function(){}生成缓存
memoizeWeakMapFn(new WeakMap()) // weakmap对WeakMap实例生成缓存
memoizeWeakMapFn(retainMap) // weakmap对Map实例生成缓存
memoizeWeakMapFn(new Set()) // weakmap对Set实例生成缓存
setTimeout(()=>{
memoizeWeakMapFn(document)
},5000)
此时打印结果为:
WeakMap:
0: {#document => "[object HTMLDocument]"}
1: {Map(0) => "[object Map]"}
2: {Array(3) => "[object Array]"}
这是因为[1,2,3], new Map()被变量retainArray和retainMap持续引用着,所以不会被垃圾回收。而function(){},new WeakMap(),new Set()都没有再继续引用了,而且因为它们作为了WeakMap的key,所以会被浏览器自动垃圾回收掉。
如果手动触发垃圾回收呢?
可以借助Chrome DevTools的memory面板工具,有一个手动触发垃圾回收的按钮。
// ...
setTimeout(()=>{
memoizeWeakMapFn(document)
},5000)
比如在上面的例子中,设置了一个5秒的延时:只要代码运行后的5秒内,去手动触发“垃圾回收按钮”,就可以很精确地看到WeakMap的key被垃圾回收了。
当然5秒这个时间是可以人为调整的,保证自己能在setTimeout内的代码运行前触发对WeakMap的垃圾回收即可,可以适当调大。