阿里 笔试 LRU/LFU

class LRU {
    // 创建一个使用LRU策略的缓存
    constructor(store) {
        // store: 缓存容量
        this.store = store || 3;
        // cache: 模拟缓存
        // 第一个元素表示最近不使用的页面
        this.cache = [];
    }
    // 将一个页面放入缓存
    putOnePage(page) {
        const pos = this.cache.indexOf(page);
        if(pos >= 0) {
            // 命中缓存，将命中的页面移动到末尾
            if(this.cache.length-1 !== pos) {
                this.cache.splice(pos, 1);
                this.cache.push(page);
            }
        } else {
            if(this.cache.length < this.store) {
                // 没命中缓存但缓存没满，直接将页面放到末尾
                this.cache.push(page);
            } else {
                // 没命中缓存且缓存满了，移除首个页面（最不经常使用），再将页面放到末尾
                this.cache.shift();
                this.cache.push(page);
            }
        }
        console.log(this.cache)
    }
}

let test = new LRU();
test.putOnePage('1');
test.putOnePage('1');
test.putOnePage('2');
test.putOnePage('3');
test.putOnePage('1');
test.putOnePage('2');
test.putOnePage('4');
test.putOnePage('5');

class LFU {
    // 创建一个使用LFU策略的缓存
    constructor(store, maxAge) {
        // store: 缓存容量
        this.store = store || 3;
        // maxAge: 缓存过期时间
        this.maxAge = maxAge || 5;
        // cache: 模拟缓存
        this.cache = [];
        // map: 记录页面状态的映射表：页面 -> [页面访问次数，页面离最后一次访问的时间]
        this.map = new Map(); //
    }
    // 将一个页面放入缓存
    putOnePage(page) {
        // 所有页面生命加1
        for(let [key,value] of this.map) {
            this.map.set(key, [value[0], value[1] + 1]);
        } 
        const pos = this.cache.indexOf(page);
        if(pos >= 0) {
            // 命中缓存，页面访问次数+1，生命置0
            let times = this.map.get(page)[0];
            this.map.set(page, [times + 1, 0]);
        } else {
            if(this.cache.length < this.store) {
                // 没命中缓存但缓存没满，将页面加入到末尾
                this.cache.push(page);
                this.map.set(page, [1, 0]);
            } else {
                // 没命中缓存且缓存满了,需要进行替换
                // 查找有没有过期的页面,如果有则删除过期页面
                let flag = false;
                let delete_page_key;
                let delete_index;
                for(let i = 0; i<this.store; i++) {
                    if(this.map.get(this.cache[i])[1] >= this.maxAge) {
                        delete_page_key = this.cache[i];
                        delete_index = i;
                        flag = true;
                        break;
                    }
                }
                if(!flag) {
                    // 没有过期页面，则删除访问次数最少的页面
                    let min_times = Infinity;
                    for(let i = 0; i<this.store; i++) {
                        let times = this.map.get(this.cache[i])[0];
                        if(times < min_times) {
                            delete_index = i;
                            min_times = times;
                            delete_page_key = this.cache[i];                        }
                    }
                }
                this.cache.splice(delete_index, 1);
                this.cache.push(page);
                this.map.delete(delete_page_key);
                this.map.set(page, [1, 0]);
            }
        }
        console.log(this.cache);
    }
}

let test = new LFU();
test.putOnePage('1');
test.putOnePage('1');
test.putOnePage('3');
test.putOnePage('4');
test.putOnePage('5');
test.putOnePage('6');
test.putOnePage('7');
test.putOnePage('8');
test.putOnePage('9');
test.putOnePage('10');