java中的OPT算法實現(xiàn)方式
更新時間：2022年07月11日 09:44:46 作者：Gee_Zer
這篇文章主要介紹了java中的OPT算法實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
java實現(xiàn)OPT算法
1966年，Belady提出最佳頁面替換算法(OPTimal replacement，OPT)。是操作系統(tǒng)存儲管理中的一種全局頁面替換策略 。
當要調入一頁而必須淘汰舊頁時，應該淘汰以后不再訪問的頁，或距最長時間后要訪問的頁面。
它所產生的缺頁數(shù)最少，然而，卻需要預測程序的頁面引用串，這是無法預知的，不可能對程序的運行過程做出精確的斷言，不過此理論算法可用作衡量各種具體算法的標準。
例子：
OPT?? ??? ?4?? ?3?? ?2?? ?1?? ?4?? ?3?? ?5?? ?4?? ?3?? ?2?? ?1?? ?5 頁1?? ??? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?2?? ?2?? ?2 頁2?? ??? ??? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?1?? ?1 頁3?? ??? ??? ??? ?2?? ?1?? ?1?? ?1?? ?5?? ?5?? ?5?? ?5?? ?5?? ?5 缺頁中斷?? ?x?? ?x?? ?x?? ?x?? ?v?? ?v?? ?x?? ?v?? ?v?? ?x?? ?x?? ?v 共缺頁中斷7次
摘自百度百科
由上面的解釋可知，opt算法就是將最遠要訪問到的頁或者不再訪問的頁淘汰掉。
直接上代碼：
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
/*
* 說明：
* 數(shù)據(jù)由文件讀入，需要自己創(chuàng)建文件，然后將數(shù)據(jù)放入其中
* 第一個數(shù)據(jù)代表內存中的頁數(shù)
* 接下來為訪問次序，數(shù)據(jù)已回車分隔*/
public class OPTTest {
public static void main(String[] args) {
OPT opt = new OPT("E:\\java\\io_copy\\opt.txt");
opt.algorithm();
}
}
class OPT {
public OPT(String filePath) {
memoryList = new ArrayList<Integer>();
rd = new ReadData(filePath);
memoryMaxSize = rd.readNext();
processList = rd.read();
}
ReadData rd;
List<Integer> processList;
List<Integer> memoryList;
int memoryMaxSize;
public void algorithm() {//opt算法
int missPage = 0;
for (int i = 0; i < processList.size(); i++) {
int nowProcess = processList.get(i);
if (memoryList.contains(nowProcess)) {
;
} else if (memoryList.size() < memoryMaxSize) {
missPage++;
memoryList.add(nowProcess);
} else {
int val = 0, index = 0;
for (int j = 0; j < memoryList.size(); j++) {
int now = processList.lastIndexOf(memoryList.get(j));
if (now > index || now < i) {
index = now < i ? Integer.MAX_VALUE : now;
val = memoryList.get(j);
}
}
memoryList.remove(memoryList.indexOf(val));
memoryList.add(nowProcess);
missPage++;
}
for (int k = 0; k < memoryList.size(); k++) {
System.out.println(memoryList.get(k));
}
System.out.println("-------------");
}
System.out.println(missPage);
}
}
class ReadData {//讀取數(shù)據(jù)
public ReadData(String filePath) {
dataList = new ArrayList<Integer>();
try {
bfr = new BufferedReader(new FileReader(filePath));
} catch (FileNotFoundException e) {
// TODO 自動生成的 catch 塊
e.printStackTrace();
}
}
private BufferedReader bfr = null;
private List<Integer> dataList;
public List<Integer> read() {
Integer i;
while ((i = readNext()) != -1) {
dataList.add(i);
}
return dataList;
};
public Integer readNext() {
try {
String data = bfr.readLine();
if (data == null) {
return -1;
}
return Integer.parseInt(data);
} catch (IOException e) {
// TODO 自動生成的 catch 塊
e.printStackTrace();
}
return -1;
}
}FIFO LRU OPT 算法java實現(xiàn)
public static void OPT(int len ,int page[]){
int block[] = new int[len];
double hit = 0;
int key = 0;
int m =0;
for(int i =0;i<page.length;i++){
if(m>=block.length){
for(int j=0;j<block.length;j++) {
if(block[j]==page[i]){
hit++;
System.out.println("命中");
key = 1;
break;
}
}
if(key==1)
{
key = 0;
continue;
}
else{
int temp[] = new int[block.length];
Arrays.fill(temp, page.length);
for(int f=0;f<block.length;f++){
for(int k=i;k<page.length;k++){
if(block[f]==page[k]){
temp[f] = k;
break;
}
}
}
int tag=0;
for(int u=0;u<temp.length;u++){
if(temp[u]>temp[tag]) tag = u;
}
System.out.println(block[tag]+"->"+page[i]);
block[tag]=page[i];
}
}
else {
for(int j=0;j<m;j++) {
if(block[j]==page[i]){
hit++;
System.out.println("命中");
key = 1;
break;
}
}
if(key==1)
{
key = 0;
continue;
}
else {System.out.println("*null->"+page[i]);block[m]=page[i];m++;}
}
}
System.out.println("命中率= "+hit/page.length);
}
public static void LRU(int len , int page[]){
int block[] = new int[len];
double hit = 0;
int key = 0;
int m=0;
for(int i =0;i<page.length;i++){
if(m>=block.length) {
for(int j=0;j<block.length;j++){
if(block[j]==page[i]){
hit++;
System.out.println("命中");
int temp = block[j];
for(int v=j;v<block.length-1;v++) block[v]=block[v+1];
block[block.length-1]=temp;
key = 1;
break;
}
}
if(key==1)
{
key = 0;
continue;
}
else{
System.out.println(block[0]+"->"+page[i]);
for(int j=0;j<block.length-1;j++) block[j]=block[j+1];
block[block.length-1]=page[i];
}
}
else {
for(int j=0;j<m;j++) {
if(block[j]==page[i]){
hit++;
System.out.println("命中");
key = 1;
break;
}
}
if(key==1)
{
key = 0;
continue;
}
else {System.out.println("*null->"+page[i]);block[m]=page[i];m++;}
}
}
System.out.println("命中率= "+hit/page.length);
}
public static void FIFO(int len,int page[]){
int block[] = new int[len];
double hit=0;
int key=0;
int m =0;
for(int i =0;i<page.length;i++){
if(m>=block.length) {
for(int j=0;j<block.length;j++) {
if(block[j]==page[i]){
hit++;
System.out.println("命中");
key = 1;
break;
}
}
if(key==1)
{
key = 0;
continue;
}
else{
System.out.println(block[0]+"->"+page[i]);
for(int j=0;j<block.length-1;j++) block[j]=block[j+1];
block[block.length-1]=page[i];
}
}
else {
for(int j=0;j<m;j++) {
if(block[j]==page[i]){
hit++;
System.out.println("命中");
key = 1;
break;
}
}
if(key==1)
{
key = 0;
continue;
}
else {System.out.println("*null->"+page[i]);block[m]=page[i];m++;}
}
}
System.out.println("命中率= "+hit/page.length);
}
測試代碼請自行編寫 ，這里OPT算法中用了一個額外的數(shù)組用來標記接下來頁面中該數(shù)據(jù)出現(xiàn)的位置，然后通過這個標記值判斷替換哪個，是我自己想出來覺得還不錯的一個方法，沒有標注注釋，請諒解。
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
本文講述了如何安裝Nacos 2.0.3版本,包括下載、解壓、配置和啟動服務的步驟,結合圖文給大家講解的非常詳細,感興趣的朋友一起看看吧2024-12-12
java連接池Druid連接回收DestroyConnectionThread&DestroyTask
這篇文章主要為大家介紹了java連接池Druid連接回收DestroyConnectionThread&DestroyTask示例分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
接口請求時間的快慢就代表著獲取到對應的數(shù)據(jù)的快慢,也代表著用戶請求頁面數(shù)據(jù)的快慢,常常可以借助接口請求快慢進行相應的優(yōu)化,本文給大家介紹了SpringBoot統(tǒng)計接口請求耗時的方法,需要的朋友可以參考下2024-12-12
本篇文章主要介紹Java中的異常、如何處理函數(shù)拋出的異常、處理異常的原則、異常處理時，性能開銷大的地方，感興趣的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了springboot緩存的使用，spring針對各種緩存實現(xiàn)，抽象出了CacheManager接口，用戶使用該接口處理緩存，而無需關心底層實現(xiàn)，感興趣的小伙伴們可以參考一下2018-06-06
Spring?AI?+?ollama?本地搭建聊天?AI?功能
這篇文章主要介紹了Spring?AI?+?ollama?本地搭建聊天?AI?,本文通過實例圖文相結合給大家講解的非常詳細,需要的朋友可以參考下2024-11-11
這篇文章主要介紹了java程序打包成exe與jar的圖文教程，有需要的朋友可以參考一下2014-01-01
今天一個偶然的機會我突然想看看JDK的動態(tài)代理，因為以前也知道一點，而且只是簡單的想測試一下使用，使用很快里就寫好了這么幾個接口和類，需要的朋友可以參考下2012-11-11
java創(chuàng)建excel示例(jxl使用方法)
Java Excel是一開放源碼項目，通過它Java開發(fā)人員可以讀取Excel文件的內容、創(chuàng)建新的Excel文件、更新 已經存在的Excel文件。下面是使用方法,包括去掉網格線、字體設置、單元格設置、對齊方式等設置2014-03-03
今天給大家?guī)淼氖顷P于Java的相關知識,文章圍繞著springboot中一些比較常用的注解展開,文中有非常詳細的總結,需要的朋友可以參考下2021-06-06