引子:
我们平时总会有一个电话本记录所有朋友的电话,但是,如果有朋友经常联系,那些朋友的电话号码不用翻电话本我们也能记住,但是,如果长时间没有联系了,要再次联系那位朋友的时候,我们又不得不求助电话本,但是,通过电话本查找还是很费时间的。但是,我们大脑能够记住的东西是一定的,我们只能记住自己最熟悉的,而长时间不熟悉的自然就忘记了。
其实,计算机也用到了同样的一个概念,我们用缓存来存放以前读取的数据,而不是直接丢掉,这样,再次读取的时候,可以直接在缓存里面取,而不用再重新查找一遍,这样系统的反应能力会有很大提高。但是,当我们读取的个数特别大的时候,我们不可能把所有已经读取的数据都放在缓存里,毕竟内存大小是一定的,我们一般把最近常读取的放在缓存里(相当于我们把最近联系的朋友的姓名和电话放在大脑里一样)。现在,我们就来研究这样一种缓存机制。
LRU缓存:
LRU缓存利用了这样的一种思想。LRU是Least Recently Used 的缩写,翻译过来就是“最近最少使用”,也就是说,LRU缓存把最近最少使用的数据移除,让给最新读取的数据。而往往最常读取的,也是读取次数最多的,所以,利用LRU缓存,我们能够提高系统的performance.
实现:
要实现LRU缓存,我们首先要用到一个类 LinkedHashMap。 用这个类有两大好处:一是它本身已经实现了按照访问顺序的存储,也就是说,最近读取的会放在最前面,最最不常读取的会放在最后(当然,它也可以实现按照插入顺序存储)。第二,LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数,但是,原始方法默认不需要移除(这是,LinkedHashMap相当于一个linkedlist),所以,我们需要override这样一个方法,使得当缓存里存放的数据个数超过规定个数后,就把最不常用的移除掉。LinkedHashMap的API写得很清楚,推荐大家可以先读一下。
要基于LinkedHashMap来实现LRU缓存,我们可以选择inheritance, 也可以选择 delegation, 我更喜欢delegation。基于delegation的实现已经有人写出来了,而且写得很漂亮,我就不班门弄斧了。代码如下:
- import java.util.LinkedHashMap;
- import java.util.Collection;
- import java.util.Map;
- import java.util.ArrayList;
- /**
- * An LRU cache, based on <code>LinkedHashMap</code>.
- *
- * <p>
- * This cache has a fixed maximum number of elements (<code>cacheSize</code>).
- * If the cache is full and another entry is added, the LRU (least recently used) entry is dropped.
- *
- * <p>
- * This class is thread-safe. All methods of this class are synchronized.
- *
- * <p>
- * Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br>
- * Multi-licensed: EPL / LGPL / GPL / AL / BSD.
- */
- public class LRUCache<K,V> {
- private static final float hashTableLoadFactor = 0.75f;
- private LinkedHashMap<K,V> map;
- private int cacheSize;
- /**
- * Creates a new LRU cache.
- * @param cacheSize the maximum number of entries that will be kept in this cache.
- */
- public LRUCache (int cacheSize) {
- this.cacheSize = cacheSize;
- int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1;
- map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) {
- // (an anonymous inner class)
- private static final long serialVersionUID = 1;
- @Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {
- return size() > LRUCache.this.cacheSize; }}; }
- /**
- * Retrieves an entry from the cache.<br>
- * The retrieved entry becomes the MRU (most recently used) entry.
- * @param key the key whose associated value is to be returned.
- * @return the value associated to this key, or null if no value with this key exists in the cache.
- */
- public synchronized V get (K key) {
- return map.get(key); }
- /**
- * Adds an entry to this cache.
- * The new entry becomes the MRU (most recently used) entry.
- * If an entry with the specified key already exists in the cache, it is replaced by the new entry.
- * If the cache is full, the LRU (least recently used) entry is removed from the cache.
- * @param key the key with which the specified value is to be associated.
- * @param value a value to be associated with the specified key.
- */
- public synchronized void put (K key, V value) {
- map.put (key, value); }
- /**
- * Clears the cache.
- */
- public synchronized void clear() {
- map.clear(); }
- /**
- * Returns the number of used entries in the cache.
- * @return the number of entries currently in the cache.
- */
- public synchronized int usedEntries() {
- return map.size(); }
- /**
- * Returns a <code>Collection</code> that contains a copy of all cache entries.
- * @return a <code>Collection</code> with a copy of the cache content.
- */
- public synchronized Collection<Map.Entry<K,V>> getAll() {
- return new ArrayList<Map.Entry<K,V>>(map.entrySet()); }
- } // end class LRUCache
- ------------------------------------------------------------------------------------------
- // Test routine for the LRUCache class.
- public static void main (String[] args) {
- LRUCache<String,String> c = new LRUCache<String, String>(3);
- c.put ("1", "one"); // 1
- c.put ("2", "two"); // 2 1
- c.put ("3", "three"); // 3 2 1
- c.put ("4", "four"); // 4 3 2
- if (c.get("2") == null) throw new Error(); // 2 4 3
- c.put ("5", "five"); // 5 2 4
- c.put ("4", "second four"); // 4 5 2
- // Verify cache content.
- if (c.usedEntries() != 3) throw new Error();
- if (!c.get("4").equals("second four")) throw new Error();
- if (!c.get("5").equals("five")) throw new Error();
- if (!c.get("2").equals("two")) throw new Error();
- // List cache content.
- for (Map.Entry<String, String> e : c.getAll())
- System.out.println (e.getKey() + " : " + e.getValue()); }
import java.util.LinkedHashMap; import java.util.Collection; import java.util.Map; import java.util.ArrayList; /** * An LRU cache, based on <code>LinkedHashMap</code>. * * <p> * This cache has a fixed maximum number of elements (<code>cacheSize</code>). * If the cache is full and another entry is added, the LRU (least recently used) entry is dropped. * * <p> * This class is thread-safe. All methods of this class are synchronized. * * <p> * Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br> * Multi-licensed: EPL / LGPL / GPL / AL / BSD. */ public class LRUCache<K,V> { private static final float hashTableLoadFactor = 0.75f; private LinkedHashMap<K,V> map; private int cacheSize; /** * Creates a new LRU cache. * @param cacheSize the maximum number of entries that will be kept in this cache. */ public LRUCache (int cacheSize) { this.cacheSize = cacheSize; int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1; map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) { // (an anonymous inner class) private static final long serialVersionUID = 1; @Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) { return size() > LRUCache.this.cacheSize; }}; } /** * Retrieves an entry from the cache.<br> * The retrieved entry becomes the MRU (most recently used) entry. * @param key the key whose associated value is to be returned. * @return the value associated to this key, or null if no value with this key exists in the cache. */ public synchronized V get (K key) { return map.get(key); } /** * Adds an entry to this cache. * The new entry becomes the MRU (most recently used) entry. * If an entry with the specified key already exists in the cache, it is replaced by the new entry. * If the cache is full, the LRU (least recently used) entry is removed from the cache. * @param key the key with which the specified value is to be associated. * @param value a value to be associated with the specified key. */ public synchronized void put (K key, V value) { map.put (key, value); } /** * Clears the cache. */ public synchronized void clear() { map.clear(); } /** * Returns the number of used entries in the cache. * @return the number of entries currently in the cache. */ public synchronized int usedEntries() { return map.size(); } /** * Returns a <code>Collection</code> that contains a copy of all cache entries. * @return a <code>Collection</code> with a copy of the cache content. */ public synchronized Collection<Map.Entry<K,V>> getAll() { return new ArrayList<Map.Entry<K,V>>(map.entrySet()); } } // end class LRUCache ------------------------------------------------------------------------------------------ // Test routine for the LRUCache class. public static void main (String[] args) { LRUCache<String,String> c = new LRUCache<String, String>(3); c.put ("1", "one"); // 1 c.put ("2", "two"); // 2 1 c.put ("3", "three"); // 3 2 1 c.put ("4", "four"); // 4 3 2 if (c.get("2") == null) throw new Error(); // 2 4 3 c.put ("5", "five"); // 5 2 4 c.put ("4", "second four"); // 4 5 2 // Verify cache content. if (c.usedEntries() != 3) throw new Error(); if (!c.get("4").equals("second four")) throw new Error(); if (!c.get("5").equals("five")) throw new Error(); if (!c.get("2").equals("two")) throw new Error(); // List cache content. for (Map.Entry<String, String> e : c.getAll()) System.out.println (e.getKey() + " : " + e.getValue()); }
代码出自:http://www.source-code.biz/snippets/java/6.htm
在博客 http://gogole.iteye.com/blog/692103 里,作者使用的是双链表 + hashtable 的方式实现的。如果在面试题里考到如何实现LRU,考官一般会要求使用双链表 + hashtable 的方式。 所以,我把原文的部分内容摘抄如下:
双链表 + hashtable实现原理:
将Cache的所有位置都用双连表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,而想链表后面移动,链表尾则表示最近最少使用的Cache。当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘汰链表最后的部分即可。
- public class LRUCache {
- private int cacheSize;
- private Hashtable<Object, Entry> nodes;//缓存容器
- private int currentSize;
- private Entry first;//链表头
- private Entry last;//链表尾
- public LRUCache(int i) {
- currentSize = 0;
- cacheSize = i;
- nodes = new Hashtable<Object, Entry>(i);//缓存容器
- }
- /**
- * 获取缓存中对象,并把它放在最前面
- */
- public Entry get(Object key) {
- Entry node = nodes.get(key);
- if (node != null) {
- moveToHead(node);
- return node;
- } else {
- return null;
- }
- }
- /**
- * 添加 entry到hashtable, 并把entry
- */
- public void put(Object key, Object value) {
- //先查看hashtable是否存在该entry, 如果存在,则只更新其value
- Entry node = nodes.get(key);
- if (node == null) {
- //缓存容器是否已经超过大小.
- if (currentSize >= cacheSize) {
- nodes.remove(last.key);
- removeLast();
- } else {
- currentSize++;
- }
- node = new Entry();
- }
- node.value = value;
- //将最新使用的节点放到链表头,表示最新使用的.
- moveToHead(node);
- nodes.put(key, node);
- }
- /**
- * 将entry删除, 注意:删除操作只有在cache满了才会被执行
- */
- public void remove(Object key) {
- Entry node = nodes.get(key);
- //在链表中删除
- if (node != null) {
- if (node.prev != null) {
- node.prev.next = node.next;
- }
- if (node.next != null) {
- node.next.prev = node.prev;
- }
- if (last == node)
- last = node.prev;
- if (first == node)
- first = node.next;
- }
- //在hashtable中删除
- nodes.remove(key);
- }
- /**
- * 删除链表尾部节点,即使用最后 使用的entry
- */
- private void removeLast() {
- //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象)
- if (last != null) {
- if (last.prev != null)
- last.prev.next = null;
- else
- first = null;
- last = last.prev;
- }
- }
- /**
- * 移动到链表头,表示这个节点是最新使用过的
- */
- private void moveToHead(Entry node) {
- if (node == first)
- return;
- if (node.prev != null)
- node.prev.next = node.next;
- if (node.next != null)
- node.next.prev = node.prev;
- if (last == node)
- last = node.prev;
- if (first != null) {
- node.next = first;
- first.prev = node;
- }
- first = node;
- node.prev = null;
- if (last == null)
- last = first;
- }
- /*
- * 清空缓存
- */
- public void clear() {
- first = null;
- last = null;
- currentSize = 0;
- }
- }
- class Entry {
- Entry prev;//前一节点
- Entry next;//后一节点
- Object value;//值
- Object key;//键
- }
public class LRUCache { private int cacheSize; private Hashtable<Object, Entry> nodes;//缓存容器 private int currentSize; private Entry first;//链表头 private Entry last;//链表尾 public LRUCache(int i) { currentSize = 0; cacheSize = i; nodes = new Hashtable<Object, Entry>(i);//缓存容器 } /** * 获取缓存中对象,并把它放在最前面 */ public Entry get(Object key) { Entry node = nodes.get(key); if (node != null) { moveToHead(node); return node; } else { return null; } } /** * 添加 entry到hashtable, 并把entry */ public void put(Object key, Object value) { //先查看hashtable是否存在该entry, 如果存在,则只更新其value Entry node = nodes.get(key); if (node == null) { //缓存容器是否已经超过大小. if (currentSize >= cacheSize) { nodes.remove(last.key); removeLast(); } else { currentSize++; } node = new Entry(); } node.value = value; //将最新使用的节点放到链表头,表示最新使用的. moveToHead(node); nodes.put(key, node); } /** * 将entry删除, 注意:删除操作只有在cache满了才会被执行 */ public void remove(Object key) { Entry node = nodes.get(key); //在链表中删除 if (node != null) { if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } if (last == node) last = node.prev; if (first == node) first = node.next; } //在hashtable中删除 nodes.remove(key); } /** * 删除链表尾部节点,即使用最后 使用的entry */ private void removeLast() { //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象) if (last != null) { if (last.prev != null) last.prev.next = null; else first = null; last = last.prev; } } /** * 移动到链表头,表示这个节点是最新使用过的 */ private void moveToHead(Entry node) { if (node == first) return; if (node.prev != null) node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; if (last == node) last = node.prev; if (first != null) { node.next = first; first.prev = node; } first = node; node.prev = null; if (last == null) last = first; } /* * 清空缓存 */ public void clear() { first = null; last = null; currentSize = 0; } } class Entry { Entry prev;//前一节点 Entry next;//后一节点 Object value;//值 Object key;//键 }
相关推荐
内容概要:本文档详细介绍了基于 MATLAB 实现的 LSTM-AdaBoost 时间序列预测模型,涵盖项目背景、目标、挑战、特点、应用领域以及模型架构和代码示例。随着大数据和AI的发展,时间序列预测变得至关重要。传统方法如 ARIMA 在复杂非线性序列中表现欠佳,因此引入了 LSTM 来捕捉长期依赖性。但 LSTM 存在易陷局部最优、对噪声鲁棒性差的问题,故加入 AdaBoost 提高模型准确性和鲁棒性。两者结合能更好应对非线性和长期依赖的数据,提供更稳定的预测。项目还展示了如何在 MATLAB 中具体实现模型的各个环节。 适用人群:对时间序列预测感兴趣的开发者、研究人员及学生,特别是有一定 MATLAB 编程经验和熟悉深度学习或机器学习基础知识的人群。 使用场景及目标:①适用于金融市场价格预测、气象预报、工业生产故障检测等多种需要时间序列分析的场合;②帮助使用者理解并掌握将LSTM与AdaBoost结合的实现细节及其在提高预测精度和抗噪方面的优势。 其他说明:尽管该模型有诸多优点,但仍存在训练时间长、计算成本高等挑战。文中提及通过优化数据预处理、调整超参数等方式改进性能。同时给出了完整的MATLAB代码实现,便于学习与复现。
palkert_3ck_01_0918
pepeljugoski_01_1106
tatah_01_1107
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
题目:基于单片机的步进电机控制系统 模块: 主控:AT89C52RC 步进电机(ULN2003驱动) 按键(3个) 蓝牙(虚拟终端模拟) 功能: 1、可以通过蓝牙远程控制步进电机转动 2、可以通过按键实现手动与自动控制模式切换。 3、自动模式下,步进电机正转一圈,反转一圈,循环 4、手动模式下可以通过按键控制步进电机转动(顺时针和逆时针)
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
内容概要:本文详细介绍了建设智慧校园平台所需的六个关键步骤。首先通过需求分析深入了解并确定校方和使用者的具体需求;其次是规划设计阶段,依据所得需求制定全面的建设方案。再者是对现有系统的整合——系统集成,确保新旧平台之间的互操作性和数据一致性。培训支持帮助全校教职工和学生快速熟悉新平台,提高效率。实施试点确保系统逐步稳定部署。最后,强调持续改进的重要性,以适应技术和环境变化。通过这一系列有序的工作,可以使智慧校园建设更为科学高效,减少失败风险。 适用人群:教育领域的决策者和技术人员,包括负责信息化建设和运维的团队成员。 使用场景及目标:用于指导高校和其他各级各类学校规划和发展自身的数字校园生态链;目的是建立更加便捷高效的现代化管理模式和服务机制。 其他说明:智慧校园不仅仅是简单的IT设施升级或软件安装,它涉及到全校范围内的流程再造和创新改革。
该文档系统梳理了人工智能技术在商业场景中的落地路径,聚焦内容生产、电商运营、智能客服、数据分析等12个高潜力领域,提炼出100个可操作性变现模型。内容涵盖AI工具开发、API服务收费、垂直场景解决方案、数据增值服务等多元商业模式,每个思路均配备应用场景拆解、技术实现路径及收益测算框架。重点呈现低代码工具应用、现有平台流量复用、细分领域自动化改造三类轻量化启动方案,为创业者提供从技术选型到盈利闭环的全流程参考。
palkert_3ck_02_0719
克鲁格曼专业化指数,最初是由Krugman于1991年提出,用于反映地区间产业结构的差异,也被用来衡量两个地区间的专业化水平,因而又称地区间专业化指数。该指数的计算公式及其含义可以因应用背景和具体需求的不同而有所调整,但核心都是衡量地区间的产业结构差异或专业化程度。 指标 年份、城市、第一产业人数(first_industry1)、第二产业人数(second_industry1)、第三产业人数(third_industry1)、专业化指数(ksi)。
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
精品推荐,通信技术LTE干货资料合集,19份。 LTE PCI网络规划工具.xlsx LTE-S1切换占比专题优化分析报告.docx LTE_TDD问题定位指导书-吞吐量篇.docx LTE三大常见指标优化指导书.xlsx LTE互操作邻区配置核查原则.docx LTE信令流程详解指导书.docx LTE切换问题定位指导一(定位思路和问题现象).docx LTE劣化小区优化指导手册.docx LTE容量优化高负荷小区优化指导书.docx LTE小区搜索过程学习.docx LTE小区级与邻区级切换参数说明.docx LTE差小区处理思路和步骤.docx LTE干扰日常分析介绍.docx LTE异频同频切换.docx LTE弱覆盖问题分析与优化.docx LTE网优电话面试问题-应答技巧.docx LTE网络切换优化.docx LTE高负荷小区容量优化指导书.docx LTE高铁优化之多频组网优化提升“用户感知,网络价值”.docx
matlab程序代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
pepeljugoski_01_0508
szczepanek_01_0308
oif2007.384.01_IEEE
stone_3ck_01_0119
oganessyan_01_1107