Least Recently Used

Problem

Cache memory is a high-speed temporary memory between the CPU and main memory (DRAM). It is very expensive and has a small capacity, so it must be used efficiently. The cache memory usage rules of the computer of the withdrawal follow the LRU algorithm. LRU algorithm is an abbreviation of Least Recently Used, and literally means the least recently used. Algorithm that when a job is removed from the cache, it will remove the one that has not been used for the longest time.

If the size of the cache is 5 and the jobs are stored in the order of | 2 | 3 | 1 | 6 | 7 |, (the first one is the most recently used and the last one is the least used for the longest time).

1. Cache Miss: In the above state, if the CPU uses task 5, a new task, it becomes a cache miss, and all tasks are pushed back, and task 5 is located at the front of the cache.

| 5 | 2 | 3 | 1 | 6 | (Job 7 is deleted from the cache.)

2. Cache Hit: The task to be done is in the cache. In the above state, if task 3 is used by the CPU, it becomes a cache hit, and tasks 5 and 2 in front of number 63 are pushed back one space, and task 3 is forward. will be located.

| 5 | 2 | 3 | 1 | 6 | —> | 3 | 5 | 2 | 1 | 6 |

If the size of the cache is given and the CPU processes N tasks one after the other when the cache is empty, write a program that processes the N tasks and outputs the state of the cache memory in order, starting with the most recently used task.

input

• In the first line, the cache size S(3<=S<=10) and the number of jobs N(5<=N<=1,000) are entered.
• In the second line, N job numbers are given in order of processing. The job number is 1 to 100.

59

1 2 3 2 6 2 3 5 7

output

After the last operation, the status of the cache memory is output in order from the most recently used operation.

7 5 3 2 6

Solution

use splice , includes and unshift

function solution(size, arr) {
	let answer = Array.from({ length: size }, () => 0);

	for (let x of arr) {
		if (answer.includes(x)) answer.splice(answer.indexOf(x), 1);
		else answer.pop();

		answer.unshift(x);
	}

	return answer;
}

without indexOf

function solution(size, arr) {
	let answer = Array.from({ length: size }, () => 0);

	arr.forEach((x) => {
		let pos = -1;
		for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;

		if (pos === -1) {
			answer.unshift(x);
			if (answer.length > size) answer.pop();
		} else {
			answer.splice(pos, 1);
			answer.unshift(x);
		}
		answer[0] = x;
	});

	return answer;
}

without all methods

function solution(size, arr) {
	let answer = Array.from({ length: size }, () => 0);

	arr.forEach((x) => {
		let pos = -1;
		for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;

		if (pos === -1) {
			for (let j = size - 1; j >= 1; j--) {
				answer[j] = answer[j - 1];
			}
		} else {
			for (let k = pos; k >= 1; k--) {
				answer[k] = answer[k - 1];
			}
		}
		answer[0] = x;
	});

	return answer;
}