LRUCACHE - LRU cache
Implement the LRU cache replacement algorithm.
Input
The input consists of two lines. The first of these lines gives the size of the cache. The second of these lines describes a sequence of memory accesses. The sequence is described by N followed by x1, ..., xN: N is the length of the sequence, and each xk is a memory address.
The input is made out of whitespace-separated integers. All integers are positive and at most a million.
Output
The number of cache faults.
Example
Input: 2 5 1 2 1 3 1 Output: 3
We are supposed to simulate a LRU cache of size 2. The first two memory accesses cause faults, and locations 1 and 2 are loaded into the cache. The third access, to address 1, does not cause a fault. The fourth access, to location 3, causes a fault and location 3 is loaded into the cache as well; but, first, to make room for the value at address 3, location 2 is evicted. Location 2 is evicted because it is the oldest one to have been used -- this is what LRU means. Finally, the fifth access does not cause a fault, because location 1 is still in the cache.
In total, there are 3 faults.
See also: FIFOCACH and MINCACHE.
Added by: | Radu Grigore |
Date: | 2016-03-29 |
Time limit: | 1s-2s |
Source limit: | 11000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | folklore |