- 浏览: 34412 次
- 性别:
- 来自: 北京
最新评论
-
cjf068:
LuckYes 写道楼主如果用最小堆的话,最好用调整堆的方式来 ...
求最小的k个数问题 -
LuckYes:
楼主如果用最小堆的话,最好用调整堆的方式来构建堆,这样效率更高 ...
求最小的k个数问题 -
cjf068:
这个算法的基本思路, ...
大数乘法 -
liujunsong:
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算 ...
大数乘法 -
shuidexiongdi:
去年我也写了一个http://shuidexiongdi.it ...
大数乘法
MyLRUCache 缓存类
访问次数记录类
package org.jf.alg.lru; import java.util.Collections; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; /** * 限定容量二叉堆+HashMap实现LRU * * @author junfeng.chen * */ public class MyLRUCache { private Map<Object,ValueEntry> container = Collections.synchronizedMap( new HashMap<Object,ValueEntry>()); private List<Object> visistList = Collections.synchronizedList(new LinkedList<Object>());//key值的访问历史 private KeyVisitCounter[] heap_array ; private int increaseStep = 500 ; private int initSize = 2000; //访问记录列表 每次访问元素,将其访问记录放入列表,并有后台线程处理 private long reset_interval = 2000*60;//刷新时间默认为2分钟 private int capacity = 100000; private int size = 0; private boolean bln_started = false; private PerlocateThread perlocateThd ; public MyLRUCache() { init(); } public MyLRUCache(int capacity) { this.capacity = capacity; init(); } /** * * @param capacity 最大容量 * @param time_cycle 计数时间周期 */ public MyLRUCache(int capacity,int time_cycle) { this.capacity = capacity; this.reset_interval = time_cycle; init(); } public void start() { this.perlocateThd = new PerlocateThread(); perlocateThd.start(); this.bln_started = true; } public void stop() { if(perlocateThd != null) perlocateThd.exit(); this.bln_started = false; this.heap_array = new KeyVisitCounter[this.initSize+1]; this.visistList.clear(); this.container.clear(); } private void init() { this.heap_array = new KeyVisitCounter[this.initSize+1]; } public void resetCount() { for(KeyVisitCounter counter:heap_array) { if(counter != null) counter.reSet(); else break; } } // public void remove(Object key) // { // not support remove explicity // } // public Object get(Object key) { assertStatus(); ValueEntry valueEntry = this.container.get(key); if(valueEntry != null) { //在堆中查找当前key,并对其count加1 visistList.add(key); return valueEntry.getData(); } return null; } public void put(Object key,Object value) { assertStatus(); ValueEntry entry = new ValueEntry(value); this.visistList.add(key); this.container.put(key, entry);//实际上 保存的元素可能比capacity多 } public int getSize() { return this.size; } /***********************some help methods****************************************************/ private void assertStatus() { if(!this.bln_started) throw new RuntimeException("Illegle Cache Staus,not started"); } /** * * @param key * @return 该key值对应的索引 */ private int perlocateUp(Object key/* , ValueEntry entry*/) { int indx = -1; ValueEntry entry = container.get(key); if(entry.getKeyIndx()==-1) { if(size<this.capacity&&size==this.heap_array.length-1) { int step = this.capacity - this.size; step = step<=this.increaseStep?step:increaseStep; KeyVisitCounter []newArray = new KeyVisitCounter[heap_array.length+step]; System.arraycopy(heap_array, 1, newArray,1, size); heap_array = newArray; } KeyVisitCounter key_counter = new KeyVisitCounter(key); key_counter.visit();//缓存已满时,防止最后一个元素总是被删除 刚插入的元素给予特殊待遇 //新加入一个记录值 if(this.size==this.capacity)//heap满 { if(heap_array[size].compareTo(key_counter)<=0) { heap_array[size] = key_counter; indx = size; }//else indx = -1 }else { heap_array[size+1] = key_counter; indx = size+1; size++; } entry.setKeyIndex(indx); } else { indx = entry.getKeyIndx(); } if(indx == -1)// return -1; //fix up heap_array to ensure it's heap character int parent = indx/2; KeyVisitCounter counter = this.heap_array[indx]; counter.visit(); while(parent!=0) { if(this.heap_array[indx].compareTo(this.heap_array[parent])>0) { KeyVisitCounter tmp = heap_array[indx]; heap_array[indx] = heap_array[parent]; heap_array[parent] = tmp; indx = parent; //设置key对应的索引 this.container.get(heap_array[indx].getKey()).setKeyIndex(indx); this.container.get(heap_array[parent].getKey()).setKeyIndex(parent); parent = indx/2; }else { break; } } return indx; } private class PerlocateThread extends Thread { boolean run = true; public void run() { int count = 200; long last_reset_time = System.currentTimeMillis(); while(run) { while(count>0&&visistList.size()>0) { Object key = visistList.remove(0); int indx = perlocateUp(key); if(indx == -1) container.remove(key); } if(System.currentTimeMillis() - last_reset_time >reset_interval) { resetCount(); last_reset_time = System.currentTimeMillis(); } try { this.sleep(500); } catch (InterruptedException e) { e.printStackTrace(); break; } } } public void exit() { run = false; } } }
访问次数记录类
package org.jf.alg.lru; public class KeyVisitCounter implements Comparable{ private Object key; private int count; public KeyVisitCounter(Object key) { this.key = key; } public void visit() { count++; } public void visit(int times) { this.count += times ; } public int getVisitTimes() { return count; } public Object getKey() { return this.key; } public void reSet() { this.count = 0; } @Override public int compareTo(Object o) { if(!(o instanceof KeyVisitCounter)) return 1; KeyVisitCounter counter = (KeyVisitCounter) o; if(this.count > counter.count) return 1; if(this.count == counter.count) return 0; return -1; } }
package org.jf.alg.lru; public class ValueEntry { private int keyIndx = -1;//key在heap数组中的下标 private Object data; public ValueEntry(Object data) { this.data = data; } public Object getData() { return this.data; } public void setKeyIndex(int indx) { this.keyIndx = indx; } public int getKeyIndx() { return this.keyIndx; } }
发表评论
-
中文数字到阿拉伯数字转换
2012-04-24 10:18 1874昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 956package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 734插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 862简单日期计算类: 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 2006已知int数组a按升序排列,要求用线性时间复杂的算法,判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1303求最大子数组之和的线性解法:本算法受编程珠玑中提示而得 /** ... -
求变位词组合
2012-03-13 22:53 853public class CharComp { ... -
计算24点
2012-03-13 21:49 1260计算n个数的全排列 package org.jf.alg. ... -
表达式计算
2012-03-10 23:02 906中缀表达式转后缀 后缀表达式计算 支持整型 分数计算,只支持 ... -
Many2One缓冲
2012-03-06 12:35 932多线程并发操作中,为了尽量减少同步锁的开销,一般都会尽可能减少 ... -
红黑树
2012-03-03 21:47 1229红黑树 规则 * 1.每个 ... -
行文件分组统计
2012-03-02 22:57 831有些情况下,对于一个结构化的以行为记录的文本文件,需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1070链表保存键值,由于没有权值策略,简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1419大根堆,可用于优先级队列 package org.jf.a ... -
固定容量二叉堆
2012-02-08 17:26 996固定容量的二叉堆实现,可用于快速求top k 问题。如要求一个 ... -
大数乘法
2012-02-07 00:16 2885论坛看到的一个面试题,实现任意大整数字符串相乘,返回结果字符串 ...
相关推荐
LRUCache(Least Recently Used Cache)是一种常用的缓存淘汰策略,它基于“最近最少使用”的原则,当缓存满时,会优先淘汰最近最不常使用的数据。在Java中,虽然标准库没有直接提供LRUCache,但我们可以通过自定义...
`LruCache`是Android SDK提供的一种基于最近最少使用(Least Recently Used)算法的内存缓存机制,常用于图片、数据等对象的缓存,以减少磁盘读取和网络加载的次数。本文将详细介绍如何在Android应用中使用`LruCache...
`LruCache`是Android SDK提供的一种内存缓存机制,它可以帮助我们优化应用程序的性能,减少对内存的消耗,提升用户体验。本文将深入探讨如何使用基于`LruCache`的图片加载工具类在ListView中实现图片缓存。 首先,`...
`LruCache`是Android SDK提供的一种基于最近最少使用(Least Recently Used)算法的内存缓存机制。本篇文章将深入探讨`LruCache`的原理、使用方法以及在实际应用中的注意事项。 首先,我们需要理解`LruCache`的工作...
"LruCache缓存网络图片"这个主题主要涉及到Android内存缓存的一种实现方式——LRU(Least Recently Used)最近最少使用算法。LRUCache是Android SDK提供的一种基于LRU算法的内存缓存工具,它被广泛应用于存储像图片...
### Android LRUCache机制详解 #### 一、LRUCache简介 在Android开发过程中,缓存技术是一项重要的优化手段,可以显著提升应用性能并改善用户体验。LRUCache(Least Recently Used Cache,最近最少使用缓存)是一种...
本篇文章将深入探讨如何使用LRUCache来解决Android图片墙中的OOM问题。 一、Android OOM简介 当应用程序请求的内存超过系统分配的最大内存时,就会发生OOM。在Android中,每个应用都有自己的Dalvik虚拟机实例,其...
本文将深入探讨如何使用`LruCache`和`DiskLruCache`实现一个二级缓存的自定义`ImageLoader`。 `LruCache`是Android SDK提供的内存缓存解决方案,全称为"Least Recently Used Cache"(最近最少使用缓存)。它的原理...
《PhotosWallDemo结合LruCache和DiskLruCache在Android中的应用详解》 在Android开发中,优化内存管理和数据缓存是提升应用性能的关键环节。本文将深入探讨一个名为PhotosWallDemo的项目,该项目巧妙地结合了...
本DEMO深入探讨了三种实现帧动画的方法,并结合LruCache内存缓存策略来优化性能,防止因大量图片加载导致的内存溢出(OOM)问题。 一、FrameAnimation+xml方式 在Android中,通过XML资源文件可以方便地创建帧动画。...
在Android系统中,LRUCache是Android SDK提供的一种基于LRU策略的内存缓存工具,主要用于图片、数据库记录等对象的缓存,以提高应用性能。 标题“LruCache缓存demo”指的是一个关于如何使用LRUCache进行缓存操作的...
LRUCache(Least Recently Used Cache)是Android系统提供的一个基于最近最少使用算法(LRU)的内存缓存机制。在Android开发中,特别是在处理大量图片或者数据时,LRUCache可以帮助我们有效地管理内存,避免因内存...
LRUCache(Least Recently Used Cache)是一种常用的缓存淘汰策略,它将最近最少使用的数据优先淘汰。在C++中,实现LRU缓存通常需要利用STL中的容器,如unordered_map来存储键值对,同时结合双向链表来维护数据的...
在Android开发中,`LruCache`是Google提供的一种基于LRU算法实现的缓存机制,它被广泛应用于图片、数据库查询结果等数据的缓存,以提高应用性能和用户体验。 ### LRU算法原理 LRU算法的基本思想是:当内存空间满时...
异步下载图片,使用LruCache和手机目录缓存,GridView滑动的时候取消下载图片,效果流畅,这里是代码,更多的介绍http://blog.csdn.net/xiaanming/article/details/9825113
`LruCache`是Android SDK提供的一种基于最近最少使用(Least Recently Used, LRU)算法的内存缓存机制,用于高效地管理应用程序的内存资源。本篇文章将深入探讨`LruCache`的工作原理,以及如何在实际项目中使用它。 ...
AsyncTask的使用及ListView的常见优化 asyncTask异步加载数据 使用了LruCache优化图片加载 通过滑动监听提高ListView滑动流畅度.rar,太多无法一一验证是否可用,程序如果跑不起来需要自调,部分代码功能进行参考学习...
简易单链表增删改查功能实现。新增内容:新增单链表LruCache算法增删改查,对学习LruCache 算法有一定帮助。
这个Demo项目涵盖了多个关键知识点,包括异步加载、网络编程、JSON解析以及LruCache图片缓存策略,这些都是在实际开发中处理数据流和用户体验优化的重要技术。 1. **异步加载**: 在Android中,为了防止UI线程被...
你可以使用它们来创建自定义的LRUCache类,提供Insert、Get、Remove等方法,以支持缓存的操作。 在`cachedemo`文件中,可能包含了LRU缓存的C#实现示例代码,你可以通过查看和学习这个示例来进一步理解和掌握C# LRU...