JAva実装のページ置換アルゴリズム

原理は言わないで、直接コード

に行きます

FIFO

import java.util.ArrayList;
import java.util.List;

import utils.ListUtils;


/**
 * 
 * 
 * @author cnkeysky
 *
 */

public class FIFO {

    public void run() {
        String[] inputStr = {"1", "2", "3", "4", "2", "1", "2", "3", "5", "2", "3", "7", "6"};
        //    
        int memory = 3;
        List list = new ArrayList<>();
        for(int i = 0; i < inputStr.length; i++){
            if(i == 0){
                list.add(inputStr[i]);
                System.out.println(" "+ i +"   ：\t\t" + ListUtils.listToString(list));
            }else {
                if(ListUtils.find(list, inputStr[i])){
                    System.out.println(" " + i + " " + "  ：\t\t" + ListUtils.listToString(list));
                }else{
                    if(list.size() < memory){
                        list.add(inputStr[i]);
                    }else{
                    list.remove(0);
                    list.add(inputStr[i]);

                    }
                    System.out.println(" " + i + " " + "  ：\t\t" + ListUtils.listToString(list));
                }
            }
        }
    }

}

LRU

import utils.ListUtils;

import java.util.ArrayList;
import java.util.List;

/**
 *           
 * @author cnkeysky
 *
 */

public class LRU {

    public static void main(String[] args) {
        String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
        //    
        int memory = 3;
        List list = new ArrayList<>();
        for(int i = 0; i < inputStr.length; i++){
            if(i == 0){
                list.add(inputStr[i]);
                System.out.println(" "+ i +"   ：\t\t" + ListUtils.listToString(list));
            }else {
                if(ListUtils.find(list, inputStr[i])){
                    //      ，      
                    int index = ListUtils.findIndex(list, inputStr[i]);
                    //         ， list    1 
                    if(!(list.get(list.size() - 1)).equals(inputStr[i]) && list.size() != 1) {
                        String str = list.get(index);
                        list.remove(index);
                        list.add(str);
                    }
                    System.out.println(" " + i + " " + "  ：\t\t" + ListUtils.listToString(list));
                }else{
                    if(list.size()>= memory) {
                        list.remove(0);
                        list.add(inputStr[i]);
                        System.out.println(" " + i + " " + "  ：\t\t" + ListUtils.listToString(list));
                    }else {
                        list.add(inputStr[i]);
                        System.out.println(" " + i + " " + "  ：\t\t" + ListUtils.listToString(list));
                    }
                }
            }
        }
    }
}

Clock

import java.util.ArrayList;
import java.util.List;

import utils.ListUtils;

/**
 * 
 * 
 * @author cnkeysky
 *
 */
public class Clock {

    public static void main(String[] args) {
        String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
        List list = new ArrayList<>();
        //    
        int memory = 3;
        //     
        int count = 0;
        String[] clock = new String[memory];
        int indexNext = 0;
        int index = 0;
        //      
        for(int i = 0; i < memory; i++) {
            clock[i] = "0";
        }
        for(int i = 0; i < inputStr.length; i++) {
            int indexPre = 0;
            if (i == 0) {
                list.add(inputStr[i]);
                clock[indexNext] = "1";
                indexNext++;
                System.out.println(" "+ i +"   ：\t\t" + ListUtils.listToString(list));
            }else {

                if(ListUtils.find(list, inputStr[i])) {
                    indexPre = ListUtils.findIndex(list, inputStr[i]);
                    if(clock[indexPre].equals("0")) {
                        clock[indexPre] = "1";
                    }
                    count++;
                    System.out.println(" "+ i +"   ：\t\t" + ListUtils.listToString(list));
                }else {
                    if(list.size() < memory) {
                        list.add(inputStr[i]);
                        clock[indexNext] = "1";
                        indexNext++;
                        System.out.println(" "+ i +"   ：\t\t" + ListUtils.listToString(list));
                    }else {
                        index = ListUtils.findZero(indexNext, clock, memory);
                        list.remove(index);
                        list.add(index, inputStr[i]);
                        clock[index] = "1";
                        indexNext = index + 1;
                        System.out.println(" "+ i +"   ：\t\t" + ListUtils.listToString(list));
                    }
                }
            }
            if(indexNext > memory - 1) {
                indexNext = Math.abs(memory - indexNext);
            }
        }
        System.out.println("    ：" + (inputStr.length-count));
    }

}

工具類ListUtils

import java.util.List;

public class ListUtils {

    public ListUtils() {

    }

    /**
     *   
     * @param list  List       , out: 2, 3, 4 
     * @return
     */
    public static String listToString(List list){

        StringBuffer content = new StringBuffer();
        for(int i = 0; i < list.size(); i++){
            content.append(list.get(i));
            if(i < list.size() - 1){
                content.append(",");
            }
        }
        return content.toString();
    }

    /**
     *  list      str
     * @param list
     * @param str
     * @return
     */
    public static boolean find(List list, String str){
        boolean flag = false;
        for(String lis : list){
            if(lis.equals(str)){
                flag = true;
            }
        }
        return flag;
    }

    /**
     *  List      String,       ,      -1
     * @param list
     * @param str
     * @return
     */
    public static int findIndex(List list, String str) {

        int index = 0;
        for(String lis : list) {
            if(lis.equals(str)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public static boolean clockJudge(String[] clock, int index) {
        if(clock[index].equals("0")) {
            return true;
        }
        return false;
    }
    /**
     * 
     * @param index   
     * @param clock   
     * @param range        
     * @return
     */
    public static int findZero(int index, String[] clock, int range) {

        while(true) {

            if(clock[index].equals("0")) {
                break;
            }else {
                clock[index] = "0";
                index++;
                if(index > range-1) {
                    index = Math.abs(range - index);
                }
            }
        }
        return index;
    }

    /**
     *               
     * @param obj
     * @param str
     * @return
     */
    public static boolean strJudge(Object[] obj, String str) {
        boolean flag = false;
        if(obj == null) {
            return flag;
        }
        for(int i = 0; i < obj.length; i++) {
            if(str.equals(obj[i])) {
                flag = true;
                break;
            }
        }
        return flag;
    }

    /**
     *                
     * @param str   
     * @param length       
     * @param memory    
     * @return
     * 
     */

    public static int findNull(Object[][] str, int length, int memory) {

        int index = 0;
        if(str == null) {
            return -1;
        }
        for(int i = 0; i < memory; i++) {
            if(str[i][length] != null) {
                index = i;
            }
        }
        return index;
    }
}