本帖最后由 梦缠绕的时候 于 2018-11-1 09:51 编辑
1. 题目要求:对Cache进行程序模拟操作,Cache最多容纳100个Item,进行新增和淘汰的处理逻辑。 1. Item:Cache item为单向链表结构,每秒钟所有Item的age加1。 2. 新增:每秒钟在队列的随机位置新增1~3个Item。 3. 淘汰:每秒钟至少淘汰一个item。 4. 淘汰条件是: 1) 要么item的age大于10。 2) 要么Cache已满又无{age>10}的item,则淘汰第一个item。 2. 程序需求:Cache单向链表中已有50个Item,写简单程序模拟新增和淘汰的过程,至少需模拟200个item的新增或淘汰。 Cache的Item基本结构,参考如下: Item { int id; // item的id int age; // 表示过期时间 item next; // 单向链表的下一个item } 3. 举例:一个单向链表,从第10秒到第11秒,数据链表上有三个变化: a) 因Age>10、淘汰ID为8 Item b) 随机位置新增ID为14 Item c) 所有item age增加了1岁
4. 具体实现:代码清单1:
- package cn.itsource.entity;
- /**
- * 该类是单向链表结构
- * @author lv
- */
- public class Item {
- private int id; // item的id
- private int age ;
- private Item next; // 单向链表的下一个item
- public Item() {
- super();
- }
- public Item(int id) {
- this.id = id;
- age++;
- }
- public int getId() {
- return id;
- }
- public void setId(int id) {
- this.id = id;
- }
- public int getAge() {
- return age;
- }
- public void setAge(int age) {
- this.age = age;
- }
- public void addAge(){
- this.age++;
- }
- public Item getNext() {
- return next;
- }
- public void setNext(Item next) {
- this.next = next;
- }
- @Override
- public String toString() {
- return id + "";
- }
- }
[color=rgb(255, 178, 1) !important]复制代码
代码清单2:
- package cn.itsource.algorithm;
- import java.util.NoSuchElementException;
- import entity.Item;
- /**
- * Cache模拟
- * @author lv
- *
- */
- public class Cache<E> {
- private Item item;
- private int elementCount; //元素个数
- private static int maxId = 1 ; //管理每个Item的id
- public Cache(){
- super();
- }
- /**
- * 获取当前链表的长度
- * @return
- */
- public synchronized int size(){
- return elementCount;
- }
- /**
- * 检验Cache 是否为空
- * @return
- */
- public synchronized boolean isEmpty() {
- return elementCount == 0;
- }
- /**
- * 插入节点到指定位置
- * @param index
- * @param item
- */
- public synchronized void insertItemByIndex(int index,Item item) {
- if(item == null)
- throw new IllegalArgumentException(item+":null值");
- int size = this.size();
- if(index <0) {
- throw new ArrayIndexOutOfBoundsException(index+"下标越界");
- } else if(index == 0){
- if(size == 0)
- this.item = item;
- else{
- Item oldItem = getItemByIndex(index);
- item.setNext(oldItem);
- this.item = item;
- }
- elementCount ++;
- idController();
- } else {
- if(index < size){
- Item oldItem = getItemByIndex(index);
- Item oldItemParent = getItemByIndex(index-1);
- item.setNext(oldItem);
- oldItemParent.setNext(item);
- elementCount ++;
- idController();
- } else if(index == size) {
- add(item);
- } else {
- throw new ArrayIndexOutOfBoundsException(index+"下标越界");
- }
- }
- }
- /**
- * 队尾追加Item元素
- * @param item
- * @return
- */
- public synchronized boolean add(Item item){
- if(size() == 0) {
- this.item = item;
- }else {
- getItemByIndex(this.size()-1).setNext(item);
- }
- elementCount ++;
- idController();
- return true;
- }
- /**
- * 移除指定位置元素
- * @param index
- */
- public synchronized void removeItemByIndex(int index){
- if(size() <= 0){
- System.out.println("[ ] : 单向链表为空");
- return;
- }
- if(index <0) {
- throw new ArrayIndexOutOfBoundsException(index+"下标越界");
- }else if(index == 0) {
- this.item = this.item.getNext();
- elementCount --;
- } else {
- if(index < size()-1){
- Item oldItemNext = getItemByIndex(index+1);
- Item oldItemParent = getItemByIndex(index-1);
- oldItemParent.setNext(oldItemNext);
- elementCount --;
- }else if(index == size()-1){
- Item oldItemParent = getItemByIndex(index-1);
- oldItemParent.setNext(null);
- elementCount --;
- }else{
- throw new ArrayIndexOutOfBoundsException(index+"下标越界");
- }
- }
- }
- /**
- * 当item的age为maxAge是获取其下标并按下标删除
- * @param maxAge
- */
- public synchronized void removeItemByAge(int maxAge){
- if(size() <= 0){
- System.out.println("[ ] : 单向链表为空");
- return;
- } else {
- Item item = this.item;
- int index = 0;
- while(item != null){
- int age = item.getAge();
- if(age==maxAge){
- // System.out.println("age : "+age+" index : "+index);
- removeItemByIndex(index);
- } else {
- ++index;
- }
- if(item.getNext() != null){
- item = item.getNext();
- } else {
- break;
- }
- }
- return;
- }
- }
- /**
- * 获取指定下标的Item元素
- * @param index
- * @return
- */
- public synchronized Item getItemByIndex(int index){
- if(size() <0) {
- throw new NoSuchElementException("Cache是空");
- }
- int count = 0;
- if(index < 0) {
- throw new ArrayIndexOutOfBoundsException(index+"下标越界");
- } else if(index == 0) {
- return this.item;
- } else {
- if(index > this.size()-1){
- // System.out.println( "size :"+this.size()+" index :"+index);
- throw new ArrayIndexOutOfBoundsException("[ "+index+" ]下标越界");
- }
- Item next = this.item.getNext();
- while(next != null){
- count++;
- if(count == index){
- return next;
- }
- next = next.getNext();
- }
- }
- return null;
- }
- /**
- * 打印Cache 中Item的 id 和 age
- * @throws Exception
- */
- public void printCache() throws Exception{
- if(item == null){
- System.out.println("[ ]");
- return;
- }
- Item item = this.item;
- while(item.getNext() != null){
- System.out.println("itemID : "+item.getId()+" itemAge : "+item.getAge());
- item = item.getNext();
- }
- System.out.println("itemID : "+item.getId()+" itemAge : "+item.getAge());
- }
- /**
- * 临时用来模拟50个Item
- * 创建 指定个数元素的 单向链表
- * @param size 指定个数元素
- */
- public void createItem(int size){
- Item it = null;
- for(int i = 1;i <= size; i++){
- it = new Item(maxId);
- if(i%10 == 0) {
- it.setAge(10);
- } else {
- it.setAge(i%10);
- }
- add(it);
- // System.out.println("id : "+it.getId()+" age : "+it.getAge());
- }
- }
- /**
- * 创建Item
- * @return
- */
- public synchronized Item createItem(){
- Item item = new Item(maxId);
- return item;
- }
- /**
- * 清空Cache
- */
- public synchronized void clear(){
- elementCount = 0;
- item = null;
- }
- /**
- * id控制器 当id的值为 Integer.MAX_VALUE 时重新从 1 开始生成
- */
- public void idController(){
- if(maxId == Integer.MAX_VALUE){
- maxId = 1;
- maxId++;
- } else {
- maxId++;
- }
- return;
- }
- /**
- * age控制器 ,所以Item的age+1
- */
- public synchronized void ageController(){
- Item it = this.item;
- while(it != null){
- it.addAge();
- if(it.getNext() != null) {
- it = it.getNext();
- } else {
- break;
- }
- }
- }
- /**
- * 获取最大id值
- * @return
- */
- public static int getMaxId() {
- return maxId;
- }
- }
[color=rgb(255, 178, 1) !important]复制代码
代码清单3:- package cn.itsource.algorithm;
- import java.util.Random;
- import entity.Item;
- public class CacheTest {
- /**
- * @param args
- */
- public static void main(String[] args) {
- Cache<Item> cache = new Cache<Item>();
- try {
- cache.createItem(50);
- cache.clear();
- cache.printCache();
- System.out.println("********************");
- cache.createItem(50);
- cache.printCache();
- // 可以用工具类Thread.sleep(1000)+循环200次控制
- Random ran = new Random();
- for(int i=0;i<200;i++){
- Thread.sleep(1000);
- cacheModel(cache, ran);
- }
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- /**
- * 模仿内存操作
- * 每秒钟要做的工作如下:
- * 1、先添加,添加之前,先获取cache的size,判断应该最多添加几个item,防止
- * 出现cache的size>100时,内存溢出的错误逻辑情况
- * 2、每个Item的age+1
- * 3、获取Item中age>10的元素删除,若无则再获取cache的size,判断应该最多删除几
- * 个item,防止cache的size=0时,还能删除的错误逻辑情况。
- * 注:(具体顺序也可以是 3、2、1或3、1、2)
- * @param cache
- * @param ran
- */
- public static void cacheModel(Cache<Item> cache,Random ran){
- //由题意已知 cache.size()是>=50,故这里就不做合法性检验了
- // 1、
- int index = randomNumberGenerator(ran,cache.size()); //最大是99
- System.out.println("=======cache.size===="+cache.size()+"===========");
- Item item = cache.createItem();
- int pcs;
- switch(index){
- case 97:
- pcs = randomNumberGenerator(ran,2); //最多新增Item2个
- randomNumberController(pcs, pcs, item, cache, ran);
- break;
- case 98:
- pcs = randomNumberGenerator(ran,1); //最多新增Item1个
- randomNumberController(pcs, pcs, item, cache, ran);
- break;
- default:
- pcs = randomNumberGenerator(ran,3); //新增Item3个
- randomNumberController(pcs, pcs, item, cache, ran);
- break;
- }
- try {
- cache.printCache();
- System.out.println("____________________________________________________");
- // 2、age+1
- cache.ageController();
- cache.printCache();
- // 3、删除满足条件的元素(两种情况)
- cache.removeItemByAge(11); // 情况一:age==11时,删除
- cache.printCache();
- if(cache.size()>=100){
- cache.removeItemByIndex(0); //情况二:cache.size()==100时,删除队首元素
- cache.printCache();
- }
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- /**
- * @param pcs 随机生成次数
- * @param index cache下标
- * @param item Item 实例
- * @param cache Cache实例
- * @param ran Random实例
- */
- public static void randomNumberController(int pcs,int index,Item item,Cache<Item> cache,Random ran){
- System.out.println("……………最大3…………index : "+index + " pcs : "+pcs);
- if(pcs==1){
- cache.insertItemByIndex(index, item);
- System.out.println("………1…… cache.size : "+cache.size()+"…index…"+index);
- }else if(pcs==2){
- cache.insertItemByIndex(index, item);
- System.out.println("……2-1… cache.size : "+cache.size()+"……index…"+index);
- index = randomNumberGenerator(ran,cache.size()); //最大是99
- item = cache.createItem();
- cache.insertItemByIndex(index, item);
- System.out.println("……2-2…… cache.size : "+cache.size()+"…index…"+index);
- }else{
- cache.insertItemByIndex(index, item);
- System.out.println("…3-1…… cache.size : "+cache.size()+"…index……"+index);
- index = randomNumberGenerator(ran,cache.size()); //最大是99
- item = cache.createItem();
- cache.insertItemByIndex(index, item);
- System.out.println("…3-2…… cache.size : "+cache.size()+"…index……"+index);
- index = randomNumberGenerator(ran,cache.size()); //最大是99
- item = cache.createItem();
- cache.insertItemByIndex(index, item);
- System.out.println("…3-3…… cache.size : "+cache.size()+"…index……"+index);
- }
- }
- /**
- * 随机数字生成器:用于随机生成新增多少个Item(1~3) 和 生成队列的随机位置(注意:应先
- * 获取队列的size)
- * 每秒钟在队列的随机位置新增1~3个Item
- * @param n 该参数是 随机生成数字的最大值
- * @param ran
- * @return
- */
- public synchronized static int randomNumberGenerator(Random ran,int n){
- if(ran == null) {
- ran = new Random();
- }
- return ran.nextInt(n)+1;
- }
- }
|