首页 > 阿里 笔试 LRU/LFU
头像
爱睡觉的吸铁石
编辑于 2021-05-10 23:07
+ 关注

阿里 笔试 LRU/LFU

/*
问题:实现 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');

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐