El usuario tiene una máquina de memoria. Tiene una capa para el almacenamiento de datos y otra capa para el caché . El usuario ha almacenado una array con longitud N en la primera capa. Cuando la CPU necesita datos, comprueba inmediatamente en la memoria caché si tiene datos o no. Si hay datos presentes, da como resultado CACHE HITS , de lo contrario, CACHE MISS , es decir, los datos no están en la memoria caché, por lo que recupera datos de la memoria principal e inserta un bloque de datos en la capa de caché.
La pregunta que surge es: ¿Cuántas veces la máquina necesitará cargar un bloque en la capa de caché, es decir, determinar el número de CACHE MISS?
Ejemplo
Supongamos una array y denotemos sus elementos por A0, A1, …, ¿AN? Ahora el usuario quiere cargar algunos elementos de esta array en el caché.
La máquina carga la array en bloques con tamaño B:
Suponga que el tamaño del bloque es 4.
1 2 3 4 viene en el Bloque 1 , 5 6 7 8 viene en el Bloque 2 y 9,10 viene en el Bloque 3.
A0, A1, …, AB? 1 formar un bloque; AB, AB+1, … , A2B? 1 forma otro bloque, y así sucesivamente. El último bloque puede contener menos de B elementos de la array del usuario.
El caché solo puede contener como máximo un bloque a la vez. Cada vez que el usuario intenta acceder a un elemento Ai, la máquina verifica si el bloque donde se encuentra Ai ya está en la memoria caché y, si no lo está, carga este bloque en la capa de memoria caché, para que pueda acceder rápidamente a cualquier dato que contenga.
Sin embargo, tan pronto como el usuario intenta acceder a un elemento que está fuera del bloque actualmente cargado en la memoria caché, el bloque que se cargó previamente en la memoria caché se elimina de la memoria caché, ya que la máquina carga un nuevo bloque que contiene el elemento al que se está accediendo.
Ejemplo:
el usuario tiene una secuencia de elementos Ax1, Ax2, …, AxM a los que desea acceder, en este orden. Inicialmente, la memoria caché está vacía. Necesitamos averiguar cuántas veces la máquina necesitará cargar un bloque en la capa de caché.
Formato de entrada:
- La primera línea de cada caso de prueba contiene tres números enteros N, B y M separados por espacios.
- La segunda línea contiene M enteros separados por espacios x1, x2, …, xM.
Aporte :
5 3 3 0 3 4
Producción :
2
Explicación:
la máquina almacena elementos [A0, A1, A2] en un bloque y [A3, A4] en otro bloque. Al acceder a A0, se carga el bloque [A0, A1, A2]. Luego, acceder a A3 elimina el bloque anterior del caché y carga el bloque [A3, A4]. Finalmente, cuando el usuario accede a A4, no se carga un nuevo bloque, ya que el bloque que contiene A4 está actualmente cargado en caché.
Acercarse :
- Inicialmente, la pérdida de caché ocurre porque la capa de caché está vacía y encontramos el siguiente multiplicador y el elemento inicial.
- Obtenga el valor del usuario y encuentre el siguiente número multiplicador que es divisible por el tamaño del bloque.
- Encuentra los elementos iniciales del bloque actual.
- Si el valor del usuario es mayor que el siguiente multiplicador y menor que el elemento inicial, se produce un error de caché.
Implementación:
C++
// C++ program to implement Cache Hits
#include <iostream>
using namespace std;
// Function to find the next multiplier
int findnextmultiplier(int i, int b)
{
for (int j = i; j <= i * b; j++) {
if (j % b == 0)
return j;
}
}
// Function to find the cache hits
int ans(int n, int b, int m, int user[])
{
// Initially cache miss occurs
int start, cacheMiss = 1, nextmultiplier;
// Find next multiplier for ith user and start
nextmultiplier= findnextmultiplier(user[0] + 1, b);
start = nextmultiplier - b + 1;
for (int i = 1; i < m; i++) {
// If ith user is greater than nextmultiplier or lesser
// than start then cache miss occurs
if (user[i] + 1 > nextmultiplier || user[i] + 1 < start) {
cacheMiss++;
nextmultiplier= findnextmultiplier(user[i] + 1, b);
start = nextmultiplier - b + 1;
}
}
// Printing cache hits
cout << cacheMiss << endl;
return 0;
}
// Driver code
int main()
{
int n=5, b=3, m=3;
int user[3] = {0, 3, 4};
ans(n, b, m, user);
return 0;
}
Java
// Java program to implement Cache Hits
public class Main
{
// Function to find the next multiplier
public static int findnextmultiplier(int i, int b)
{
for (int j = i; j <= i * b; j++)
{
if (j % b == 0)
return j;
}
return 0;
}
// Function to find the cache hits
public static int ans(int n, int b, int m, int user[])
{
// Initially cache miss occurs
int start, ch = 1, nextmultiplier;
// Find next multiplier for ith user and start
nextmultiplier= findnextmultiplier(user[0] + 1, b);
start = nextmultiplier - b + 1;
for (int i = 1; i < m; i++)
{
// If ith user is greater than nextmultiplier or lesser
// than start then cache hit occurs
if (user[i] + 1 > nextmultiplier || user[i] + 1 < start)
{
ch++;
nextmultiplier= findnextmultiplier(user[i] + 1, b);
start = nextmultiplier - b + 1;
}
}
// Printing cache hits
System.out.println(ch);
return 0;
}
public static void main(String[] args)
{
int n=5, b=3, m=3;
int user[] = {0, 3, 4};
ans(n, b, m, user);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement Cache Hits # Function to find the next multiplier def findnextmultiplier(i, b): for j in range(i, (i * b) + 1): if (j % b == 0): return j # Function to find the cache hits def ans(n, b, m, user): # Initially cache hit occurs ch = 1 # Find next multiplier for ith user and start nextmultiplier = findnextmultiplier(user[0] + 1, b) start = nextmultiplier - b + 1 for i in range(1, m): # If ith user is greater than nextmultiplier # or lesser than start then cache hit occurs if (user[i] + 1 > nextmultiplier or user[i] + 1 < start): ch += 1 nextmultiplier = findnextmultiplier( user[i] + 1, b) start = nextmultiplier - b + 1 # Printing cache hits print(ch) # Driver code n = 5 b = 3 m = 3 user = [ 0, 3, 4 ] ans(n, b, m, user) # This code is contributed by rag2127
C#
// C# program to implement Cache Hits
using System;
class GFG{
// Function to find the next multiplier
static int findnextmultiplier(int i, int b)
{
for(int j = i; j <= i * b; j++)
{
if (j % b == 0)
return j;
}
return 0;
}
// Function to find the cache hits
static int ans(int n, int b, int m, int[] user)
{
// Initially cache hit occurs
int start, ch = 1, nextmultiplier;
// Find next multiplier for ith user and start
nextmultiplier = findnextmultiplier(
user[0] + 1, b);
start = nextmultiplier - b + 1;
for(int i = 1; i < m; i++)
{
// If ith user is greater than nextmultiplier
// or lesser than start then cache hit occurs
if (user[i] + 1 > nextmultiplier ||
user[i] + 1 < start)
{
ch++;
nextmultiplier = findnextmultiplier(
user[i] + 1, b);
start = nextmultiplier - b + 1;
}
}
// Printing cache hits
Console.WriteLine(ch);
return 0;
}
// Driver Code
static void Main()
{
int n = 5, b = 3, m = 3;
int[] user = { 0, 3, 4 };
ans(n, b, m, user);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to implement
// Cache Hits
// Function to find the next multiplier
function findnextmultiplier(i, b)
{
for(let j = i; j <= i * b; j++)
{
if (j % b == 0)
return j;
}
return 0;
}
// Function to find the cache hits
function ans(n, b, m, user)
{
// Initially cache hit occurs
let start, ch = 1, nextmultiplier;
// Find next multiplier for ith user and start
nextmultiplier =
findnextmultiplier(user[0] + 1, b);
start = nextmultiplier - b + 1;
for(let i = 1; i < m; i++)
{
// If ith user is greater than nextmultiplier
// or lesser than start then cache hit occurs
if (user[i] + 1 > nextmultiplier
|| user[i] + 1 < start)
{
ch++;
nextmultiplier =
findnextmultiplier(user[i] + 1, b);
start = nextmultiplier - b + 1;
}
}
// Printing cache hits
document.write(ch + "</br>");
return 0;
}
let n = 5, b = 3, m = 3;
let user = [ 0, 3, 4 ];
ans(n, b, m, user);
</script>
Producción :
2
Tiempo Complejidad : O(m)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por rajasek155 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA