OPT算法代码
简介：这是作者在操作系统实验课上写下的代码,OPT算法，通过了老师的测试，大家如果也遇到了这个实验课，拿去吧我的代码。
最佳页面替换算法：最佳页面替换算法，当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距最长时间后要访问的页面。它所产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言，不过此理论算法可用作衡量各种具体算法的标准。
数据：
代码实现：
import sun.plugin.javascript.navig.Link; import java.util.*; // Pair类，模仿的C++里面的对组 class Pair { // first是数字，second是对应的索引 public Pair(int first, int second) { this.first = first; this.second = second; } public int first; public int second; } // opt算法的思路是 // 将每个数字和它的出现了的索引的队列做成映射表 // 每次比较内存里面的元素的索引队列的对首元素谁最大 // 最大的那个滚 public class Main { // 遍历列表的方法 static void ListTrave(List<Integer> list) { System.out.print("list: "); for (int i = 0; i < list.size(); ++ i) { System.out.print(list.get(i) + " "); } System.out.println(); } // 遍历队列的方法 static void QueueTrave(Queue<Integer> q) { System.out.print("Queue:"); Iterator<Integer> it = q.iterator(); while(it.hasNext()) { System.out.print(it.next() + " "); } System.out.println(); } // 遍历字典的方法 static void MapTrave(Map<Integer, Queue<Integer> > map) { System.out.println("map:"); for (Integer i : map.keySet()) { System.out.print(i + ": "); Iterator it = map.get(i).iterator(); while(it.hasNext()) { System.out.print(it.next() + " "); } System.out.println(); } } public static void main(String[] args) { Scanner in = new Scanner (System.in); // 内存访问顺序 System.out.println("内存的访问顺序："); int numPage = in.nextInt(); // System.out.println(numPage); // 页面中断的次数 int cnt = 0; // 内存块的数量 System.out.println("内存的数量："); int numMemory = in.nextInt(); System.out.println("输入内存："); Map<Integer, Queue<Integer> > map = new HashMap<>(); // 把每个元素存一遍 // 用队列的好处是 可以保证查询的效率是O(1) Queue<Integer> q = new LinkedList<>(); // 存放当前内存中的元素 List<Integer> list = new ArrayList<>(); // 把每个元素和它的索引队列做成映射表 for (int i = 0; i < numPage; ++ i) { int num = in.nextInt(); q.add(num); if (map.containsKey(num)) { Queue<Integer> queue = map.get(num); queue.add(i); map.put(num, queue); } else { Queue<Integer> queue = new LinkedList<>(); queue.add(i); map.put(num, queue); } } // 检查 // QueueTrave(q); // MapTrave(map); for (int i = 0; i < numPage; ++ i) { int num = q.poll(); if (list.size() < numMemory) { if (!list.contains(num)) { list.add(num); map.get(num).poll(); cnt ++; } } else { if (list.contains(num)) { // 这里是就算 内存里面存在这个元素 但是也是还要假替换的 就是 // 把这次新来的num的对应的队列的索引也删掉 map.get(num).poll(); } else { check((ArrayList<Integer>) list, map); cnt ++; list.add(num); // 把num对应的索引删掉一个 map.get(num).poll(); } } // ListTrave(list); } // System.out.println("cnt: " + cnt); System.out.printf("%.1f%%", (double)cnt / (double)numPage * 100); } // 返回那个要滚的数字 static int check(ArrayList<Integer> list, Map<Integer, Queue<Integer> > map) { // System.out.println("enter:"); // ListTrave(list); // MapTrave(map); // 最后要滚的数字 和 对应的索引 // 先设置为list的第一个元素 // 如果这个数字对应的队列映射为空那么 用负数代表索引 表示无穷远 int t = list.get(0); // t是内存中的数字 int idx = 0; // t对应的索引 int t2 = map.get(t).size(); // 索引对应的数字对应的队列的大小 int t3; // 队列第一个数字的索引 // 判断是否为空的情况 if (t2 == 0) t3 = -1; else t3 = map.get(t).peek(); // System.out.println("t1 + idx + t2 + t3=" + t + " " + idx + " " + t2 + " " + t3); Pair num = new Pair(idx, t3); // num存放需要删除的数字的索引和这个数字对应的队列的队首 if (num.second == -1) // 如果找到-1的后面的就不用找了 { list.remove(num.first); // remove是按照索引删除 return list.get(num.first); } // System.out.println("t1 + idx + t2 + t3=" + t + " " + idx + " " + t2 + " " + t3); for (int i = 1; i < list.size(); ++ i) { // ListTrave(list); t = list.get(i); idx = i; t2 = map.get(t).size(); if (t2 == 0) t3 = -1; else t3 = map.get(t).peek(); // System.out.println("t1 + idx + t2 + t3=" + t + " " + idx + " " + t2 + " " + t3); if(t3 == -1) { list.remove(idx); return list.get(num.first); } else { // 让更远的代替 if (num.second < t3) { num = new Pair(idx, t3); } } } // 最后second最大的滚 list.remove(num.first); return list.get(num.first); } }
运行结果：
