让每一名学员高薪就业
返回列表 发新帖

Cache模拟

[复制链接]

158

主题

165

帖子

1335

积分

精英

Rank: 5Rank: 5

积分
1335
发表于 2018-8-13 09:55:22  | 显示全部楼层 | 阅读模式
本帖最后由 往事随风 于 2018-8-13 09:58 编辑

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;                 // itemid
int  age;             // 表示过期时间
item next;             // 单向链表的下一个item
}
3.        举例:
一个单向链表,从第10秒到第11秒,数据链表上有三个变化:
a) 因Age>10、淘汰ID为8 Item
b) 随机位置新增ID为14 Item
c) 所有item age增加了1岁
图片1.png
4.        具体实现:代码清单1
  1. package cn.itsource.entity;
  2. /**
  3. * 该类是单向链表结构
  4. * @author lv
  5. */
  6. public class Item {
  7.         private int  id;                 // item的id
  8.         private int  age ;         
  9.         private Item next;             // 单向链表的下一个item
  10.         
  11.         public Item() {
  12.                 super();
  13.         }
  14.         
  15.         public Item(int id) {
  16.                 this.id = id;
  17.                 age++;
  18.         }

  19.         public int getId() {
  20.                 return id;
  21.         }
  22.         public void setId(int id) {
  23.                 this.id = id;
  24.         }
  25.         public int getAge() {
  26.                 return age;
  27.         }
  28.         public void setAge(int age) {
  29.                 this.age = age;
  30.         }
  31.         public void addAge(){
  32.                 this.age++;
  33.         }
  34.         
  35.         public Item getNext() {
  36.                 return next;
  37.         }
  38.         public void setNext(Item next) {
  39.                 this.next = next;
  40.         }

  41.         @Override
  42.         public String toString() {
  43.                 return id + "";
  44.         }

  45. }
复制代码
代码清单2
  1. package cn.itsource.algorithm;

  2. import java.util.NoSuchElementException;
  3. import entity.Item;

  4. /**
  5. * Cache模拟
  6. * @author lv
  7. *        
  8. */
  9. public class Cache<E> {
  10.         private Item item;
  11.         private int elementCount;                //元素个数
  12.         private static int maxId = 1 ;        //管理每个Item的id
  13.         
  14.         public Cache(){
  15.                 super();
  16.         }
  17.         
  18.         /**
  19.          * 获取当前链表的长度
  20.          * @return
  21.          */
  22.         public synchronized int size(){
  23.                 return elementCount;
  24.         }
  25.         
  26.         /**
  27.          *         检验Cache 是否为空
  28.          * @return
  29.          */
  30.         public synchronized boolean isEmpty() {
  31.                 return elementCount == 0;
  32.          }
  33.         
  34.         /**
  35.          * 插入节点到指定位置
  36.          * @param index
  37.          * @param item
  38.          */
  39.         public synchronized void insertItemByIndex(int index,Item item) {
  40.                 if(item == null)
  41.                         throw new IllegalArgumentException(item+":null值");
  42.                 int size = this.size();
  43.                 if(index <0) {
  44.                         throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  45.                 } else if(index == 0){        
  46.                         if(size == 0)
  47.                                 this.item = item;
  48.                         else{
  49.                                 Item oldItem = getItemByIndex(index);
  50.                                 item.setNext(oldItem);
  51.                                 this.item = item;
  52.                         }
  53.                         elementCount ++;
  54.                         idController();
  55.                 } else {
  56.                         if(index < size){
  57.                                 Item oldItem = getItemByIndex(index);
  58.                                 Item oldItemParent = getItemByIndex(index-1);
  59.                                 item.setNext(oldItem);
  60.                                 oldItemParent.setNext(item);
  61.                                 elementCount ++;
  62.                                 idController();
  63.                         } else if(index == size) {
  64.                                 add(item);
  65.                         } else {
  66.                                 throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  67.                         }
  68.                 }
  69.         }
  70.         
  71.         /**
  72.          *         队尾追加Item元素
  73.          * @param item
  74.          * @return
  75.          */
  76.         public synchronized boolean add(Item item){
  77.                 if(size() == 0) {
  78.                         this.item = item;
  79.                 }else {
  80.                         getItemByIndex(this.size()-1).setNext(item);
  81.                 }
  82.                 elementCount ++;
  83.                 idController();
  84.                 return true;
  85.         }
  86.         
  87.         /**
  88.          *  移除指定位置元素
  89.          * @param index
  90.          */
  91.         public synchronized void removeItemByIndex(int index){
  92.                 if(size() <= 0){
  93.                         System.out.println("[ ]  : 单向链表为空");
  94.                         return;
  95.                 }
  96.                 if(index <0) {
  97.                         throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  98.                 }else if(index == 0) {
  99.                         this.item = this.item.getNext();
  100.                         elementCount --;
  101.                 } else {
  102.                         if(index < size()-1){
  103.                                 Item oldItemNext = getItemByIndex(index+1);
  104.                                 Item oldItemParent = getItemByIndex(index-1);
  105.                                 oldItemParent.setNext(oldItemNext);
  106.                                 elementCount --;
  107.                         }else if(index == size()-1){
  108.                                 Item oldItemParent = getItemByIndex(index-1);
  109.                                 oldItemParent.setNext(null);
  110.                                 elementCount --;
  111.                         }else{
  112.                                 throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  113.                         }
  114.                 }
  115.         }
  116.         
  117.         /**
  118.          *         当item的age为maxAge是获取其下标并按下标删除
  119.          * @param maxAge
  120.          */
  121.         public synchronized void removeItemByAge(int maxAge){
  122.                 if(size() <= 0){
  123.                         System.out.println("[ ]  : 单向链表为空");
  124.                         return;
  125.                 } else {
  126.                         Item item = this.item;
  127.                         int index = 0;
  128.                         while(item != null){
  129.                                 int age = item.getAge();
  130.                                 if(age==maxAge){
  131. //                                        System.out.println("age :  "+age+"  index  :  "+index);
  132.                                         removeItemByIndex(index);
  133.                                 } else {
  134.                                         ++index;
  135.                                 }
  136.                                 if(item.getNext() != null){
  137.                                         item = item.getNext();
  138.                                 } else {
  139.                                         break;
  140.                                 }
  141.                         }
  142.                         return;
  143.                 }
  144.         }
  145.         
  146.         /**
  147.          * 获取指定下标的Item元素
  148.          * @param index
  149.          * @return
  150.          */
  151.         public synchronized Item getItemByIndex(int index){
  152.                 if(size() <0) {
  153.                         throw new NoSuchElementException("Cache是空");
  154.                 }
  155.                 int count = 0;
  156.                 if(index < 0) {
  157.                         throw new ArrayIndexOutOfBoundsException(index+"下标越界");
  158.                 } else if(index == 0) {
  159.                         return this.item;
  160.                 } else {
  161.                         if(index > this.size()-1){
  162. //                                System.out.println( "size    :"+this.size()+"     index    :"+index);
  163.                                 throw new ArrayIndexOutOfBoundsException("[ "+index+" ]下标越界");
  164.                         }
  165.                         Item next = this.item.getNext();
  166.                         while(next != null){
  167.                                 count++;
  168.                                 if(count == index){
  169.                                         return next;
  170.                                 }
  171.                                 next = next.getNext();
  172.                         }
  173.                 }
  174.                 return null;
  175.         }
  176.         
  177.         /**
  178.          *  打印Cache 中Item的 id 和 age
  179.          * @throws Exception
  180.          */
  181.         public void printCache() throws Exception{
  182.                 if(item == null){
  183.                         System.out.println("[ ]");
  184.                         return;
  185.                 }
  186.                 Item item = this.item;
  187.                 while(item.getNext() != null){
  188.                         System.out.println("itemID : "+item.getId()+"    itemAge : "+item.getAge());
  189.                         item = item.getNext();
  190.                 }
  191.                 System.out.println("itemID : "+item.getId()+"    itemAge : "+item.getAge());
  192.         }
  193.         
  194.         /**
  195.          * 临时用来模拟50个Item
  196.          * 创建 指定个数元素的 单向链表
  197.          * @param size 指定个数元素
  198.          */
  199.         public void createItem(int size){
  200.                 Item it = null;
  201.                 for(int i = 1;i <= size; i++){
  202.                         it = new Item(maxId);
  203.                         if(i%10 == 0) {
  204.                                 it.setAge(10);
  205.                         } else {
  206.                                 it.setAge(i%10);
  207.                         }
  208.                         add(it);
  209. //                        System.out.println("id  : "+it.getId()+"   age :  "+it.getAge());
  210.                 }
  211.         }
  212.         
  213.         /**
  214.          *         创建Item
  215.          * @return
  216.          */
  217.         public synchronized Item createItem(){
  218.                 Item item = new Item(maxId);
  219.                 return item;
  220.         }
  221.         
  222.         /**
  223.          * 清空Cache
  224.          */
  225.         public synchronized void clear(){
  226.                 elementCount = 0;
  227.                 item = null;
  228.         }
  229.         
  230.         /**
  231.          *         id控制器 当id的值为 Integer.MAX_VALUE 时重新从 1 开始生成
  232.          */
  233.         public void idController(){
  234.                 if(maxId == Integer.MAX_VALUE){
  235.                         maxId = 1;
  236.                         maxId++;
  237.                 } else {
  238.                         maxId++;
  239. }
  240.                 return;
  241.         }
  242.         
  243.         /**
  244.          * age控制器 ,所以Item的age+1
  245.          */
  246.         public synchronized void ageController(){
  247.                 Item it = this.item;
  248.                 while(it != null){
  249.                         it.addAge();
  250.                         if(it.getNext() != null) {
  251.                                 it = it.getNext();
  252.                         } else {
  253.                                 break;
  254.                         }
  255.                 }
  256.         }
  257.         
  258.         /**
  259.          *         获取最大id值
  260.          * @return
  261.          */
  262.         public static int getMaxId() {
  263.                 return maxId;
  264.         }
  265. }
复制代码
代码清单3
  1. package cn.itsource.algorithm;

  2. import java.util.Random;
  3. import entity.Item;

  4. public class CacheTest {

  5.         /**
  6.          * @param args
  7.          */
  8.         public static void main(String[] args) {
  9.                 Cache<Item> cache = new Cache<Item>();  
  10.                 try {
  11.                         cache.createItem(50);
  12.                         cache.clear();
  13.                         cache.printCache();
  14.                         System.out.println("********************");
  15.                         cache.createItem(50);
  16.                         cache.printCache();
  17.                        
  18.                         // 可以用工具类Thread.sleep(1000)+循环200次控制
  19.                         Random ran = new Random();
  20.                         for(int i=0;i<200;i++){
  21.                                 Thread.sleep(1000);
  22.                                 cacheModel(cache, ran);
  23.                         }
  24.                 } catch (Exception e) {
  25.                         e.printStackTrace();
  26.                 }
  27.         }
  28.        
  29.         /**
  30.          *  模仿内存操作
  31.          *  每秒钟要做的工作如下:
  32.          *  1、先添加,添加之前,先获取cache的size,判断应该最多添加几个item,防止
  33.          *           出现cache的size>100时,内存溢出的错误逻辑情况
  34.          *  2、每个Item的age+1
  35.          *  3、获取Item中age>10的元素删除,若无则再获取cache的size,判断应该最多删除几
  36.          *           个item,防止cache的size=0时,还能删除的错误逻辑情况。
  37.          *  注:(具体顺序也可以是 3、2、1或3、1、2)
  38.          * @param cache
  39.          * @param ran
  40.          */
  41.         public static void cacheModel(Cache<Item> cache,Random ran){
  42.                 //由题意已知 cache.size()是>=50,故这里就不做合法性检验了
  43.                 //        1、
  44.                 int index = randomNumberGenerator(ran,cache.size());        //最大是99
  45.                 System.out.println("=======cache.size===="+cache.size()+"===========");
  46.                 Item item =  cache.createItem();
  47.                 int pcs;
  48.                 switch(index){
  49.                         case 97:
  50.                                 pcs = randomNumberGenerator(ran,2);        //最多新增Item2个
  51.                                 randomNumberController(pcs, pcs, item, cache, ran);
  52.                                 break;
  53.                         case 98:
  54.                                 pcs = randomNumberGenerator(ran,1);        //最多新增Item1个
  55.                                 randomNumberController(pcs, pcs, item, cache, ran);
  56.                                 break;
  57.                         default:
  58.                                 pcs = randomNumberGenerator(ran,3);        //新增Item3个
  59.                                 randomNumberController(pcs, pcs, item, cache, ran);
  60.                                 break;
  61.                 }
  62.                 try {
  63.                         cache.printCache();
  64.                         System.out.println("____________________________________________________");
  65.                         // 2、age+1
  66.                         cache.ageController();
  67.                         cache.printCache();
  68.                         // 3、删除满足条件的元素(两种情况)
  69.                         cache.removeItemByAge(11);           // 情况一:age==11时,删除
  70.                         cache.printCache();
  71.                         if(cache.size()>=100){
  72.                                 cache.removeItemByIndex(0); //情况二:cache.size()==100时,删除队首元素
  73.                                 cache.printCache();
  74.                         }
  75.                 } catch (Exception e) {
  76.                         e.printStackTrace();
  77.                 }
  78.         }
  79.        
  80.         /**
  81.          * @param pcs                随机生成次数
  82.          * @param index                cache下标
  83.          * @param item                Item  实例
  84.          * @param cache                Cache实例
  85.          * @param ran                Random实例
  86.          */
  87.         public static void randomNumberController(int pcs,int index,Item item,Cache<Item> cache,Random ran){
  88.                 System.out.println("……………最大3…………index : "+index + "  pcs : "+pcs);
  89.                 if(pcs==1){
  90.                         cache.insertItemByIndex(index, item);
  91.                         System.out.println("………1…… cache.size : "+cache.size()+"…index…"+index);
  92.                 }else if(pcs==2){
  93.                         cache.insertItemByIndex(index, item);
  94.                         System.out.println("……2-1… cache.size : "+cache.size()+"……index…"+index);
  95.                         index = randomNumberGenerator(ran,cache.size());        //最大是99
  96.                         item =  cache.createItem();
  97.                         cache.insertItemByIndex(index, item);
  98.                         System.out.println("……2-2…… cache.size : "+cache.size()+"…index…"+index);
  99.                 }else{
  100.                         cache.insertItemByIndex(index, item);
  101.                         System.out.println("…3-1…… cache.size : "+cache.size()+"…index……"+index);
  102.                         index = randomNumberGenerator(ran,cache.size());        //最大是99
  103.                         item =  cache.createItem();
  104.                         cache.insertItemByIndex(index, item);
  105.                         System.out.println("…3-2…… cache.size : "+cache.size()+"…index……"+index);
  106.                         index = randomNumberGenerator(ran,cache.size());        //最大是99
  107.                         item =  cache.createItem();
  108.                         cache.insertItemByIndex(index, item);
  109.                         System.out.println("…3-3…… cache.size : "+cache.size()+"…index……"+index);
  110.                 }
  111.         }
  112.        
  113.         /**
  114. * 随机数字生成器:用于随机生成新增多少个Item(1~3) 和 生成队列的随机位置(注意:应先
  115. * 获取队列的size)
  116.           * 每秒钟在队列的随机位置新增1~3个Item
  117.           * @param        n 该参数是 随机生成数字的最大值
  118.           * @param        ran
  119.           * @return
  120.           */
  121.         public synchronized static int randomNumberGenerator(Random ran,int n){
  122.                 if(ran == null) {
  123.                         ran = new Random();
  124.                 }
  125.                 return ran.nextInt(n)+1;
  126.         }

  127. }
复制代码


回复

使用道具 举报

0

主题

11

帖子

11

积分

菜鸟

Rank: 1

积分
11
发表于 2018-8-13 09:56:24  | 显示全部楼层
好贴,我要帮楼主顶上去!
回复 支持 反对

使用道具 举报

0

主题

9

帖子

5

积分

菜鸟

Rank: 1

积分
5
发表于 2018-8-13 10:32:28  | 显示全部楼层
源码现在有几个学科
回复 支持 反对

使用道具 举报

0

主题

6

帖子

11

积分

菜鸟

Rank: 1

积分
11
发表于 2018-8-13 10:35:06  | 显示全部楼层
好贴,我要帮楼主顶上去!
回复 支持 反对

使用道具 举报

0

主题

8

帖子

7

积分

菜鸟

Rank: 1

积分
7
发表于 2018-8-13 10:35:17  | 显示全部楼层
好贴,我要帮楼主顶上去!
回复 支持 反对

使用道具 举报

0

主题

8

帖子

11

积分

菜鸟

Rank: 1

积分
11
发表于 2018-8-13 10:35:23  | 显示全部楼层
源码的老师都是好样的
回复 支持 反对

使用道具 举报

0

主题

6

帖子

11

积分

菜鸟

Rank: 1

积分
11
发表于 2018-8-13 10:35:27  | 显示全部楼层
什么都不说,先赞一个!
回复 支持 反对

使用道具 举报

0

主题

10

帖子

12

积分

菜鸟

Rank: 1

积分
12
发表于 2018-8-13 10:35:30  | 显示全部楼层
老师们都好严格
回复 支持 反对

使用道具 举报

发表回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

最新活动

联系我们

Java培训  |   PHP培训  |   UI培训  |   H5培训  |   Python培训  |   大数据培训  |   如何报名  |   视频下载
快速回复 返回顶部 返回列表