写点什么

ARTS-WEEK2

用户头像
Allen
关注
发布于: 2020 年 06 月 15 日
ARTS-WEEK2

Algorithm

LeetCode 146 LRUCache

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。



获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。



进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

思路也是在网上看了一些大佬的思路才整理出来的现在思路,如有错误地方,请指出。



整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 save 和 get key的时间都是 O(1),而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点



核心总结:

save(key, value),首先在 HashMap 找到 Key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果LRU空间不足,则通过 tail 淘汰掉队尾的节点,同时在 HashMap 中移除 Key。

get(key),通过 HashMap 找到 LRU 链表节点,因为根据LRU 原理,这个节点是最新访问的,所以要把节点插入到队头,然后返回缓存的值。

Review

http://igoro.com/archive/gallery-of-processor-cache-effects/

主要讲述了CPU CACHE原理,并用代码和图表做了量化分析

Tip

VxWorks中logMsg与printf的区别

VxWorks中logMsg函数可以在中断中使用,VxWorks中断处理程序之所以不用printf,本质在于printf是将信息输出到标准输出设备(STDOUT)中, 整个标准输出设备是一个全局变量,由于有semTake操作,那么就会发生阻塞,vxworks属于硬实时操作系统,不能在规定的时间内完成操作即会死机或复位。所以vxworks不用printf的原因在于阻塞。

Share

无知要比博学更容易产生自信。(Ignorance more frequently begets confidence than does knowledge.)—— 查尔斯·达尔文

  1. 对未知的事物要保持谦逊的态度

  2. Dunning-Kruger effect

达克效应(D-K effect),全称为邓宁-克鲁格效应(Dunning-Kruger effect)。它是一种认知偏差现象,指的是能力欠缺的人在自己欠考虑的决定的基础上得出错误结论,但是无法正确认识到自身的不足,辨别错误行为。这些能力欠缺者们沉浸在自我营造的虚幻的优势之中,常常高估自己的能力水平,却无法客观评价他人的能力。



用户头像

Allen

关注

还未添加个人签名 2020.05.20 加入

还未添加个人简介

评论

发布
暂无评论
ARTS-WEEK2