C ++ реализация алгоритма замены кэша

Контекст: В рамках задания я должен подумать о новом алгоритме замены кэша. Существует ряд таких алгоритмов, как «Наименее недавно использованные», «Сначала пришел — первым вышел», но я не могу использовать ни один из них. Итак, я подумал о новом алгоритме, который работает в соответствии с индексом. Индекс будет начинаться с 0 и продолжаться до n-1, где n — размер кэша.

Если кэш не заполнен, я помещаю элементы с индексами 0,1,2, …, n-1, пока он не будет заполнен. После того, как кеш заполнен, я просто заменяю блоки по индексу (th) индексу блока кеша (в данном случае представлен как массив).

Проблема:
После просмотра кода вы поймете, что это довольно просто, так как я просто добавляю элементы к ключу и значению моего массива и увеличиваю размер массива. Если массив заполняется, я заменяю элемент index (th) новым элементом и увеличиваю его, чтобы заменить следующий блок / index в следующих итерациях.

Но проблема в том, что при вставке элементов одни и те же элементы помещаются в index = 0, и мне очень трудно понять, почему. Любая помощь будет высоко оценена.

В заключение,

//This is the faulty output
/*
*****---Executing print function---*****

Block 0 Memory Address: 10010 Value: 10
Block 1 Memory Address: 10010 Value: 10
Block 2 Memory Address: 10010 Value: 10
Block 3 Memory Address: 10010 Value: 10
*/

//While it should have been
/*
Block 0 Memory Address: 10010 Value: 10
Block 1 Memory Address: 10011 Value: 11
Block 2 Memory Address: 10100 Value: 12
Block 3 Memory Address: 10101 Value: 13
*/

Код:

#include <iostream>
using namespace std;

//We will have 2 primary functions. get(key) and set(key, value).
//get is used to retreive the value if key exists in cache. Otherwise it will return -1.
//set is used to set (key,value) by replacing the block. if value is already existent it should not do anything.
//Using this struct, we will add key value and a data structure for holding a pair of key and value.
typedef struct
{
int key, value; //to store address and data
}cache_set;

class algorithm_implement
{
public:
cache_set* cache;//array to hold information
int capacity; //number of blocks per set
int size; //total current elements in the cache
int index;

algorithm_implement(int total_size)
{
cache = new cache_set[capacity];
size = 0;
capacity = total_size;
index = 0;
}
int get (int mem_address)
{
//if the cache already has the address in it then retreive the value and do nothing. Else return -1
for (int i = 0; i < capacity; i++ )
{
if (cache[i].key == mem_address)
{
int req_val = cache[i].value;
return req_val;
}
}
return -1;
}
void set(int mem_address, int data)
{
for (int i = 0; i< capacity; i++){
if (cache[i].key == mem_address)
{
cout << "This memory address is already present in the cache. No replacement necessary."<<endl<<endl;
return;
}
//if item is not present and blocks are full then put key and value at index(th) position and increment the index. Don't let index be greater than capacity.
if (size == capacity)
{
index = index % capacity;
cache[index].key = mem_address;
cache[index].value = data;
index ++;

}
//if item is not present and some blocks are empty then put key and value at the index of size and increment size until cache is full.
else if (size < capacity)
{
cache[size].key = mem_address;
cache[size].value = data;
size ++;
}
}
}
void print()
{
cout << "*****---Executing print function---*****"<<endl<<endl;
for (int i = 0; i< capacity; i++)
{
cout << "Block "<< i << " Memory Address: "<<cache[i].key << " Value: "<<cache[i].value<<endl;
}
}
};

int main(){
int num_blocks = 4;
algorithm_implement index_based = *new algorithm_implement(num_blocks);
index_based.set(10010, 10);
index_based.set(10011, 11);
index_based.set(10100, 12);
index_based.set(10101, 13);
//Trying to put pre-existing element in the cache.
index_based.set(10010, 10);
//Printing the elements present in the cache
index_based.print();
}
//This is the output
/*
*****---Executing print function---*****

Block 0 Memory Address: 10010 Value: 10
Block 1 Memory Address: 10010 Value: 10
Block 2 Memory Address: 10010 Value: 10
Block 3 Memory Address: 10010 Value: 10
*/

//The output should have been
/*
Block 0 Memory Address: 10010 Value: 10
Block 1 Memory Address: 10011 Value: 11
Block 2 Memory Address: 10100 Value: 12
Block 3 Memory Address: 10101 Value: 13
*/

1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]