- 浏览: 271773 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (161)
- 【**计划】 (2)
- 【**Core Java**】 (30)
- 【**JAVA EE】 (6)
- JDBC (3)
- Hibernate专题系列 (0)
- 【**OS】 (14)
- 【**架构设计/设计模式】 (11)
- 【Hadoop】 (3)
- 【**分布式】 (9)
- 模板 (1)
- C (2)
- 常用工具 (1)
- Oracle (2)
- 【Tips】 (3)
- 【数据库】 (2)
- 玩转Ubuntu (0)
- 【计算机网络/网络编程】 (7)
- 【**Search Engine】 (21)
- 【**专题**】 (6)
- 【**Python】 (10)
- XML (1)
- 【**Open Source Framework】 (1)
- 【高级主题】 (1)
- 【存储】 (3)
- 【笔试面试】 (2)
- 【**数据结构与算法设计】 (20)
- 【其他】 (3)
- 【编程练习】 (2)
- 【待完成】 (12)
- 【工作】 (6)
- 【软件研发】 (4)
- 【**多线程多进程编程】 (5)
- 【Web Service】 (1)
- 【表达式解析/JavaCC系列】 (5)
- 【缓存系统:Memcached】 (1)
- 【Java IO/NIO】 (5)
- 【JVM运行机制及内存管理】 (7)
最新评论
-
107x:
...
python list排序 -
yuzhu223:
...
【Python基础】Python的lambda函数与排序 -
Tonyguxu:
分析查询结果的打分小于11.query=1065800715* ...
lucene打分机制的研究 -
Tonyguxu:
query=139320661963.013709 = (MA ...
lucene打分机制的研究 -
Tonyguxu:
query=10658007150.6772446 = (MA ...
lucene打分机制的研究
前言
实现LRU算法,注意观察者模式、并发(读写锁、线程池)的运用
核心类:LRUMap
成员变量
LinkedHashMap<K,V> map
—— 底层存放元素(
key-value
)的容器。
ConcurrentLinkedQueue<LRUMapEvictionListener<K,V>> listeners
—— 监听器队列,存放注册到该LRUMap的所有监听器(通过
LRUMap的
addListener注册
),具体监听器实现
LRUMapEvictionListener接口,实现void objectEvicted(K key, V value)方法(对象逐出处理程序,详见 )。当执行LRUMap的evict、setCapacity、put操作时,会notify listener,并由线程池中的线程来遍历
listeners
执行各个监听器的处理程序(即
objectEvicted
)。
ExpirationProcessor exProcess —— 内部类,线程类(继承Thread,是个守护线程setDaemon(true)),唤作“阎王线程”。持有成员属性Map<Object,Long> expirations唤作“死亡手册”(放置了key和lastAccess最后访问时间)和long expireTime(构造阎王线程实例时候设置的存活时间)。 “阎王线程”会不断地定时地检查死亡名单,如果名单中某个元素达到死亡时间(当前时间 - lastAccess > expireTime),则将该元素从名单 及 容器 中删除并notify listener做相应处理操作。
“阎王线程”何时新建、start呢?
在实例化LRUMap的时候,会根据设置的存活时间 expireTime决定是否启动“阎王线程”,如果实例化LRUMap时不指定 expireTime 或者设置为0,则不会有人定期检查容器中的元素是否到了死亡时间了。
if(expired > 0){ exProcess = new ExpirationProcessor(this,expired*1000L); exProcess.start(); }
ThreadPoolExecutor poolExecutor ——线程池用于异步执行监听器处理程序。在调用LRUMap构造的时候实例化。
poolExecutor = new ThreadPoolExecutor(1,10,120L,TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>(), new ThreadFactoryImpl(null,"LRUMap Listener Thread") ); poolExecutor.execute(new Runnable() { public void run() { doNotifyListeners(rmKey,rmVal); } });
ReadWriteLock readWriteLock = new ReentrantReadWriteLock() ——通过readLock()和writeLock()可以获得读锁和写锁。
内部类
private static class ExpirationProcessor extends Thread —— “阎王线程”类,在run()方法里while(true)体,会不断地定期地(每隔10s)检查死亡名单,将达到死亡时间的成员“干掉”。
将key及对应的最近访问时间放到阎王线程持有的死亡名单expirations里
public Long put(Object key, Long value) { return expirations.put(key, value); }
构造方法
public LRUMap(int size) —— expired存活时间默认为0
public LRUMap(int size,int expired)
public LRUMap(int size,int expired) { if(size <= 0){ throw new IllegalArgumentException("Size should larger than 0"); } map = new LinkedHashMap<K,V>(size); this.capacity = size; listeners = new ConcurrentLinkedQueue<LRUMapEvictionListener<K,V>>(); poolExecutor = new ThreadPoolExecutor(1,10,120L,TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>(), new ThreadFactoryImpl(null,"LRUMap Listener Thread") ); if(expired > 0){ exProcess = new ExpirationProcessor(this,expired*1000L); exProcess.start(); } }
成员方法
public boolean containsKey(K key) ——判断是否包含key,注意读锁
public boolean containsKey(K key){ Lock lock = readWriteLock.readLock(); lock.lock(); try{ return map.containsKey(key); }finally{ lock.unlock(); } }
public V get(K key) ——从容器里获得key对应的value。根据LRU算法,如果根据key获取元素时,该元素会被认为最近使用,执行先删后加(加在链表尾部表示活跃使用),然后返回key对应的value,注意读写锁
public V get(K key){
Lock lock = readWriteLock.readLock();
lock.lock();
try {
if(map.containsKey(key)){
Lock writeLock = readWriteLock.writeLock();
lock.unlock();
writeLock.lock();
try {
//体现LRU算法:最近使用的元素会被放在最后面位置
map.put(key,map.remove(key)); // Most-Recent used is always in last
if(exProcess != null){
exProcess.put(key,System.currentTimeMillis());
}
}finally {
lock.lock();
writeLock.unlock();
}
return map.get(key);
}
return null;
} finally {
lock.unlock();
}
}
public V peek(K key) ——返回key对应的value。peek与get的区别
public V peek(K key){ Lock lock = readWriteLock.readLock(); lock.lock(); try { return map.get(key); } finally { lock.unlock(); } }
public void put(K key, V value) ——如果key已经存在,则先删后加(加在链表尾部),如果容器已满,则先删除第一个元素再add。
public void put(K key, V value){ if(key == null){ throw new IllegalArgumentException("Key object cannot be null."); } Lock lock = readWriteLock.writeLock(); lock.lock(); try { if(map.containsKey(key)){ map.remove(key); }else{ if(capacity == 0){ return; } //体现LRU算法:如果容器满了,则将最老的元素逐出, //在这里最老的元素放置在LinkHashMap第一个位置上 if(map.size()==capacity){ // reach the limit of key list K rmKey = map.keySet().iterator().next(); // remove the eldest(LRU) one V rmVal = map.remove(rmKey); if(exProcess != null){ exProcess.remove(rmKey); } notifyListeners(rmKey,rmVal); } if(exProcess != null){ exProcess.put(key,System.currentTimeMillis()); } } map.put(key,value); } finally { lock.unlock(); } }
public int size() ——容器当前大小
public int size(){ Lock lock = readWriteLock.readLock(); lock.lock(); try{ return map.size(); }finally{ lock.unlock(); } }
public int getCapacity() ——获得容器容量
public void setCapacity(int newSize) ——设置容器容量,如果新设置的容量大小(newSize)小于容器已经包含的元素数(oldSize),需要将部分元素丢弃掉,从 LinkedHashMap头开始 删除(oldSize-newSize)个元素。
public void setCapacity(int newSize){
Lock lock = readWriteLock.writeLock();
lock.lock();
try {
this.capacity = newSize;
if(map.size() > capacity){
int count = map.size()-capacity;
//体现LRU算法
for(Iterator<K> itr = map.keySet().iterator();itr.hasNext()&&(count > 0);count--){ // shrink the map
K rmKey = itr.next(); // remove the eldest(LRU) one
V rmVal = map.get(rmKey);
itr.remove();
if(exProcess != null){
exProcess.remove(rmKey);
}
notifyListeners(rmKey,rmVal);
}
}
} finally {
lock.unlock();
}
}
public V remove(K key) ——将元素从LRUMap容器中及“阎王线程”持有的死亡名单中删除。
public V remove(K key) { Lock lock = readWriteLock.writeLock(); lock.lock(); try { if(exProcess != null){ exProcess.remove(key); } return map.remove(key); }finally{ lock.unlock(); } }
public V evict(K key) ——与remove差别,多了notifyListeners(key,val)
public V evict(K key) { Lock lock = readWriteLock.writeLock(); lock.lock(); try { if(exProcess != null){ exProcess.remove(key); } V val = map.remove(key); if(val != null){ notifyListeners(key,val); } return val; }finally{ lock.unlock(); } }
public List<K> keys() ——获得key的列表
public List<K> keys(){
Lock lock = readWriteLock.readLock(); lock.lock(); try{ return new LinkedList<K>(map.keySet()); }finally{ lock.unlock(); } }
public List<K> getMRUKeys(int num) ——获得排在后面num个元素的key。后面num个元素一般是比较活跃的元素。
Listener相关方法:
(注:运用了观察者模式,模式详见参考1,当LRUMap的状态发生变化时,比如调用了evict、setCapacity、put方法时,通知观察者(监听器Listener)做相应处理,具体监听器会实现 LRUMapEvictionListener接口 )
public void addListener(LRUMapEvictionListener<K,V> listener) ——将Listener实例加到listeners queue里
public boolean removeListener(LRUMapEvictionListener<K,V> listener) ——从listeners queue里删除该Listener实例
private void notifyListeners(final K rmKey,final V rmVal) ——在evict、setCapacity、put里调用
private void notifyListeners(final K rmKey,final V rmVal) { if(listeners.isEmpty()){ return; } poolExecutor.execute(new Runnable() { public void run() { doNotifyListeners(rmKey,rmVal); } }); }
private void doNotifyListeners(final K rmKey,final V rmVal)
private void doNotifyListeners(final K rmKey,final V rmVal) { if(listeners.isEmpty()){ return; } for (LRUMapEvictionListener<K,V> l : listeners) { l.objectEvicted(rmKey,rmVal); } }
监听器接口:
public interface LRUMapEvictionListener<K, V> { void objectEvicted(K key, V val); }
构造LRUMap后,通过 addListener注册监听器实例(可以多次注册,监听器实例存放在LRUMap的成员属性 listeners中 )。
void objectEvicted(K key, V val)传入key和value,从方法名看叫做“对象逐出方法”,一般是在调用了LRUMap的一些操作如 evict、setCapacity、put(按照LRU算法这些操作通常涉及到元素的添加和删除以及位置的变化)时,会调用该处理程序,该处理程序针对不同应用场景有不同实现。
如下示例
private LRUMap<String, IndexWriter> writerCache = new LRUMap<String, IndexWriter>(writerCacheSize, expireTime * 60); //注册监听器 writerCache.addListener(new LRUMapEvictionListener<String, IndexWriter>() { //监听器处理程序 @Override public void objectEvicted(String name, IndexWriter writer) { if (log.isInfoEnabled()) { log.info("IndexWriter of :" + name + " is evicted,going to evict correspondent IndexReader ."); } readerCache.evict(name); numberOfWriterEvicted.incrementAndGet(); try { writer.close(); }catch (Exception e) { log.warn("failed to close writer of :"+name, e); } } });
线程工厂:
后记
1.体会读写锁的使用
http://nemogu.iteye.com/blog/1409879
2.java.util和java.util.concurrent中集合类
3.实现LRUMap时为什么使用观察者模式
LinkedHashMap<K,V> map中的元素被逐出(Evicte)后,如果想对这个被逐出的对象做处理(比如close)或者做一些其他相关操作,使用观察者模式,可以在map中的元素被逐出时,调用观察者类(监听器类)。
参考
1.观察者模式 http://nemogu.iteye.com/admin/blogs/1407857
发表评论
-
【Java IO】Java的序列化机制
2012-06-12 18:07 981Java序列化机制采用的序列化算法: 1.所有保存到磁盘 ... -
LRU算法介绍
2012-06-05 22:30 3708问题背景 在操作系统的内存管理里,如何节省有限的内存并为尽可 ... -
关于 Java 对象序列化【转载】
2012-06-04 16:45 1330简介: Java 对象序列化(Java Object Seri ... -
数据结构之位图bitmap
2012-05-10 23:12 0http://dongxicheng.org/structur ... -
常见数据结构与算法汇总
2012-05-10 23:01 10731、常见数据结构 线性:数组,链表,队列, ... -
数据结构之位图
2012-05-10 18:34 5611介绍 (20120511)位图就是通过将数组下标与应用中 ... -
CRC循环校验
2012-05-10 15:11 1319http://www.360doc.com/content/1 ... -
map3搜索与存储的一道面试题
2012-05-10 15:10 881假设一个mp3搜索引擎收录了2^24首歌曲,并记录了可收听这些 ... -
字符串匹配算法——Edit distance
2012-05-09 11:20 2483如何比较两个字符串之间的相似程度(或者差异)? 想要比较 ... -
JavaCC/JJTree入门
2012-05-03 18:17 1361JavaCC 介绍 JJTree JJTree为了让 ... -
【Java NIO】内存映射文件
2012-04-24 14:16 1319java.nio包包含对下列特性的支持: 1.字符集 ... -
排序算法
2012-04-21 23:06 638插入排序 shell排序 ... -
【编程珠矶】开篇 千万号码的排序问题
2012-04-21 12:52 909注:学习了《编程珠矶》第一章,将涉及的一些知识点整理如下 ... -
【Core Java】正则表达式
2012-04-05 23:40 01 -
【Core Java】类加载
2012-04-02 21:16 825主要内容包括: 1.类加载 / 类连接 / 类初始化 2. ... -
【****Core Java提纲****】
2012-04-02 18:54 771Java IO NIO Java并发编程 ... -
Java编程中“为了性能”尽量要做到的一些地方[zz]
2012-03-19 23:31 8161. 尽量在合适的场合使用单例 使用单例可以减轻 ... -
【Java并发】线程安全
2012-03-10 15:44 1023什么是线程安全? 当多个线程访问一个类时,如果不用考 ... -
【Java Socket】
2012-03-07 18:49 2712 -
各个rules里代码分析
2012-03-06 10:54 734InternalChannelRule private ...
相关推荐
起点小说解锁.js
299-煤炭大数据智能分析解决方案.pptx
299-教育行业信息化与数据平台建设分享.pptx
网络技术和计算机技术发展至今,已经拥有了深厚的理论基础,并在现实中进行了充分运用,尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代,所以对于信息的宣传和管理就很关键。系统化是必要的,设计网上系统不仅会节约人力和管理成本,还会安全保存庞大的数据量,对于信息的维护和检索也不需要花费很多时间,非常的便利。 网上系统是在MySQL中建立数据表保存信息,运用SpringBoot框架和Java语言编写。并按照软件设计开发流程进行设计实现。系统具备友好性且功能完善。 网上系统在让售信息规范化的同时,也能及时通过数据输入的有效性规则检测出错误数据,让数据的录入达到准确性的目的,进而提升数据的可靠性,让系统数据的错误率降至最低。 关键词:vue;MySQL;SpringBoot框架 【引流】 Java、Python、Node.js、Spring Boot、Django、Express、MySQL、PostgreSQL、MongoDB、React、Angular、Vue、Bootstrap、Material-UI、Redis、Docker、Kubernetes
时间复杂度是计算机科学中用来评估算法效率的一个重要指标。它表示了算法执行时间随输入数据规模增长而变化的趋势。当我们比较不同算法的时间复杂度时,实际上是在比较它们在不同输入规模下的执行效率。 时间复杂度通常用大O符号来表示,它描述了算法执行时间上限的增长率。例如,O(n)表示算法执行时间与输入数据规模n呈线性关系,而O(n^2)则表示算法执行时间与n的平方成正比。当n增大时,O(n^2)算法的执行时间会比O(n)算法增长得更快。 在比较时间复杂度时,我们主要关注复杂度的增长趋势,而不是具体的执行时间。这是因为不同计算机硬件、操作系统和编译器等因素都会影响算法的实际执行时间,而时间复杂度则提供了一个与具体实现无关的评估标准。 一般来说,时间复杂度越低,算法的执行效率就越高。因此,在设计和选择算法时,我们通常希望找到时间复杂度尽可能低的方案。例如,在排序算法中,冒泡排序的时间复杂度为O(n^2),而快速排序的时间复杂度在平均情况下为O(nlogn),因此在处理大规模数据时,快速排序通常比冒泡排序更高效。 总之,时间复杂度是评估算法效率的重要工具,它帮助我们了解算法在不同输入规模下的性
5G通信行业、网络优化、通信工程建设资料
网络技术和计算机技术发展至今,已经拥有了深厚的理论基础,并在现实中进行了充分运用,尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代,所以对于信息的宣传和管理就很关键。系统化是必要的,设计网上系统不仅会节约人力和管理成本,还会安全保存庞大的数据量,对于信息的维护和检索也不需要花费很多时间,非常的便利。 网上系统是在MySQL中建立数据表保存信息,运用SpringBoot框架和Java语言编写。并按照软件设计开发流程进行设计实现。系统具备友好性且功能完善。 网上系统在让售信息规范化的同时,也能及时通过数据输入的有效性规则检测出错误数据,让数据的录入达到准确性的目的,进而提升数据的可靠性,让系统数据的错误率降至最低。 关键词:vue;MySQL;SpringBoot框架 【引流】 Java、Python、Node.js、Spring Boot、Django、Express、MySQL、PostgreSQL、MongoDB、React、Angular、Vue、Bootstrap、Material-UI、Redis、Docker、Kubernetes
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
5G通信行业、网络优化、通信工程建设资料
《基于小程序的交友系统的设计与实现》是一个融合了小程序技术和社交功能的毕业设计项目。该项目旨在通过开发一款小程序,为用户提供一个便捷、有趣的交友平台,满足用户寻找新朋友、拓展社交圈的需求。 一、项目背景与目标 随着移动互联网的普及,小程序以其轻便、易用的特性受到了广大用户的喜爱。本项目旨在利用小程序技术开发一款交友系统,通过简洁明了的界面设计和丰富多样的社交功能,吸引用户参与并提升用户体验。通过实现这一系统,旨在帮助用户拓展社交圈,增进人际关系,并推动社交领域的创新与发展。 二、系统设计与功能实现 用户注册与登录:系统提供用户注册与登录功能,确保用户信息的真实性和安全性。用户可以通过手机号或第三方社交账号进行注册和登录。 个人资料展示:用户可以在个人资料页面展示自己的基本信息、兴趣爱好、照片等,以便其他用户了解并产生互动。 附近的人:系统通过定位功能展示附近的其他用户,用户可以浏览附近的人的信息,并主动发起聊天或交友请求。 聊天功能:系统提供一对一的聊天功能,用户可以与感兴趣的人进行实时交流,增进彼此的了解。 活动组织:用户可以发起或参与各类线下活动,如聚会、运动、旅行
5G通信行业、网络优化、通信工程建设资料
shampoo-sales.csv
59-《煤矿测量规程(1989版)》150.pdf
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
5G通信行业、网络优化、通信工程建设资料。
AXIS T864 系列多通道 AXIS T8646 PoE+ 同轴电缆刀片套件 AXIS T8648 PoE+ 同轴电缆刀片紧凑型套件安装指南
MATLAB学习个人笔记总结.7z
【资源说明】【毕业设计】 1、该资源内项目代码都是经过测试运行成功,功能正常的情况下才上传的,请放心下载使用。 2、适用人群:主要针对计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、数学、电子信息等)的同学或企业员工下载使用,具有较高的学习借鉴价值。 3、不仅适合小白学习实战练习,也可作为大作业、课程设计、毕设项目、初期项目立项演示等,欢迎下载,互相学习,共同进步!
5G通信、网络优化与通信建设