[アルゴリズム]Least Recently Used-ソート

質問する

キャッシュは、CPUとメインメモリ(DRAM)との間で高速化された一時メモリであり、CPUが処理するタスクを記憶し、直ちに処理速度を向上させる装置である.価格が高く、容量が小さいので、効率的に使います.チョルスのコンピュータのキャッシュ使用規則はLRUアルゴリズムに従う.LRUアルゴリズムは直訳して「最近使用」の略であり、その意味は最近使用されていないものに相当する.キャッシュからアクションを削除するときに、最も長く使用されていないアルゴリズムを削除します.
マンヨーキャッシュのサイズが5で、ジョブが2 3 1 6 7の順序で格納されている場合(一番前は最近使用したジョブ、後ろは最長時間未使用のジョブ).
1)Cache miss:キャッシュされていない場合、上記の状態でCPUが新しいタスク5番タスクを使用するとCache missとなり、すべてのタスクが後回しになり、5番タスクがキャッシュの一番前に位置する.
5 2 3 1 6(7番のタスクはキャッシュから削除されます)
2)Cache Hit:実行すべきタスクがキャッシュ中である場合、CPUが3番タスクを使用すると、Cache HitはキャッシュHitとなり、63番より前の5、2番タスクは1段後ろに押され、3番が一番前になる.
5 2 3 1 6 ---> 3 5 2 1 6

キャッシュサイズが与えられ、CPUがキャッシュが空の場合にN個のタスクを順次処理すると、最近使用したタスクから順にキャッシュの状態を出力するプログラムが作成される。

▼▼入力説明
1行目には、キャッシュのサイズS(3<=S<=10)と、操作の個数N(5<=N<=1000)が入力される.2行目にはN個のジョブ番号が処理順で与えられる.作業番号は1~100です.
▼▼出力説明
最後のタスクの後、最近使用したタスクから順にキャッシュの状態を出力します.
▼▼入力例1
5 9
1 2 3 2 6 2 3 5 7
▼▼出力例1
7 5 3 2 6
▼▼キャッシュ状態の変化
1 0 0 0 0
2 1 0 0 0
3 2 1 0 0
2 3 1 0 0
6 2 3 1 0
2 6 3 1 0
3 2 6 1 0
5 3 2 6 1
7 5 3 2 6

に答える

function solution(s,arr){
	const cache = [];
	arr.forEach(element => {
		let pos = -1;
        for(let i = 0; i < s; i++){
      		if(element === cache[i]) pos = i;
      	}
      	if(pos === -1){
        	answer.unshift(element);
        	if(answer.length > s) answer.pop();
      	} else {
        	answer.splice(pos,1);
        	answer.unshift(element);
      	}
    });
    return cache;
}

▼▼問題の出所

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard