黑马程序员技术交流社区

标题: 【上海校区】Cache模拟 [打印本页]

作者: 梦缠绕的时候 时间: 2018-11-1 09:39
标题: 【上海校区】Cache模拟
本帖最后由梦缠绕的时候于 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;
}
}

作者: 不二晨 时间: 2018-11-1 15:47

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2