LRUアルゴリズムの単純な実装(Least Recently Usedの最近の最小使用)
12551 ワード
LRUはLeast Recently Usedの略であり、最近最も少なく使用されており、ルーティングまたは淘汰アルゴリズムとして使用することができる.
アルゴリズムの考え方は,1つのデータが最近アクセスされていない場合,将来アクセスされる可能性も低いということである.この特性のため、使用できないデータを淘汰することができます.
チェーンテーブルに基づくLRU実装[ヘッダは最新のデータ(アクセスまたは挿入)]構想:データを新しく挿入するたびに新しいデータをチェーンテーブルのヘッダに挿入する;キャッシュがヒットするたびに(すなわち、データがアクセスされる)、データをチェーンテーブルのヘッダに移動します.では、チェーンテーブルがいっぱいになると、チェーンテーブルの末尾のデータを淘汰します.
主にgetとputの2つのメソッドgetがある場合にアクセスするデータをヘッダ(アクセス)putに置く場合には2つのケースがある.最大容量に達していない場合は、直接ヘッダにデータを挿入します(挿入).2.最大容量に達したら、末尾のデータを削除(最小使用を淘汰)し、頭にデータを挿入(挿入)する.
アルゴリズムの考え方は,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 + "]";
}
}
}