LRUアルゴリズムの単純な実装(Least Recently Usedの最近の最小使用)

12551 ワード

LRUはLeast Recently Usedの略であり、最近最も少なく使用されており、ルーティングまたは淘汰アルゴリズムとして使用することができる.
アルゴリズムの考え方は,1つのデータが最近アクセスされていない場合,将来アクセスされる可能性も低いということである.この特性のため、使用できないデータを淘汰することができます.
チェーンテーブルに基づくLRU実装[ヘッダは最新のデータ(アクセスまたは挿入)]構想:データを新しく挿入するたびに新しいデータをチェーンテーブルのヘッダに挿入する;キャッシュがヒットするたびに(すなわち、データがアクセスされる)、データをチェーンテーブルのヘッダに移動します.では、チェーンテーブルがいっぱいになると、チェーンテーブルの末尾のデータを淘汰します.
主にgetとputの2つのメソッドgetがある場合にアクセスするデータをヘッダ(アクセス)putに置く場合には2つのケースがある.最大容量に達していない場合は、直接ヘッダにデータを挿入します(挿入).2.最大容量に達したら、末尾のデータを削除(最小使用を淘汰)し、頭にデータを挿入(挿入)する.
public class LRUSimple {
	
	private int cap = 0;
	private LinkedList<User> link = new LinkedList<>(); 
	LRUSimple(int capcity){
		this.cap=capcity;
	}
	public User get(String user){
		User u = null;
		for(User tmp:link){
			u=tmp;
			if(tmp.getUser()==user){
			//-------       ----------
				link.remove(tmp);
				link.addFirst(tmp);
			//------------------------------
			}
		}
		return u;
	}
	
	public void put(User u){
		if(link.size()==cap){//              (      )
			link.removeLast();
		}
		link.addFirst(u);//      
	}
	
	public static void main(String[] args) {
		//   
		LRUSimple lru = new LRUSimple(3);
		lru.put(new User("hzc","5"));
		lru.put(new User("hc","5"));
		lru.put(new User("h","5"));
		lru.get("hzc");
		lru.put(new User("h2c","5"));
		System.out.println(lru.toString());
	}
	
	
	@Override
	public String toString() {
		return link.toString();
	}

//---------------------   ----------------------------
	static class User{
		private String user;
		private String age;
		
		
		public User(String user, String age) {
			super();
			this.user = user;
			this.age = age;
		}
		public String getUser() {
			return user;
		}
		public void setUser(String user) {
			this.user = user;
		}
		public String getAge() {
			return age;
		}
		public void setAge(String age) {
			this.age = age;
		}
		@Override
		public String toString() {
			return "User [user=" + user + ", age=" + age + "]";
		}
		
	}
}