CACHE PART II

PYTHON PROGRAMMING !!!

PYTHON PROGRAMMING !!!

PYTHON PROGRAMMING !!!

(Before reading the following description, please read the introduction first.) In this problem, you need to implement an LRU cache. When CPU needs to access data, the following steps are performed. 1. If the required data is stored in the cache, then a cache hit occurs; CPU can immediately access the data, and the access time of the accessed data is updated. Otherwise, a cache miss occurs. 2. If a cache miss occurs and the cache is full, we erase the data that is least recently accessed from the cache. Then we copy the required data from main memory into the cache and record the access time. Now we give an example. In this example, the capacity of the cache is 2, and we use a sequence to represent the addresses of data stored in the cache, where data least recently accessed from the cache is listed first. At first, the content of the cache is () (the empty sequence). CPU accesses data as follows. 1. CPU accesses data at address 0. A cache miss occurs, now the content of cache is (0) 2. CPU accesses data at address 1. A cache miss occurs, now the content of cache is (0,1). 3. CPU accesses data at address 0. A cache hit occurs; now the content of cache is (1.0). 4. CPU accesses data at address 2. A cache miss occurs; now the content of cache is (0,2). 5. CPU accesses data at address 0. A cache hit occurs, now the content of cache is (2.0). 6. CPU accesses data at address 2. A cache hit occurs, now the content of cache is (0.2). Now given the sequence of addresses of data that CPU accesses, you are asked to count the number of cache misses (i.e., the number of times that accessed data does not occur in the cache). Input Format The first line contains two positive integers n and c, where n is the number of data accesses and c is the capacity of the cache. The second line contains the addresses 21, 22, ...,an of accessed data. Output Format Output the number of cache misses. Limits 1