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）。它是一种认知偏差现象，指的是能力欠缺的人在自己欠考虑的决定的基础上得出错误结论，但是无法正确认识到自身的不足，辨别错误行为。这些能力欠缺者们沉浸在自我营造的虚幻的优势之中，常常高估自己的能力水平，却无法客观评价他人的能力。