кэширование хеша нескольких ключей

Question

Я хочу сделать кеширование в моем проекте.

Пусть мой API int foo(int a, float b, float c, int d, char e)

Теперь в моем проекте много обращений к API, занимающему много времени с более длительным временем, с повторяющимися значениями a, b, c, d и e. Теперь я хочу сохранить возвращаемое значение этой функции с этими аргументами в качестве ключей.

предположим, что моя последовательность вызовов

foo(23, 3.45, 4.5, 90, 'd') // returns 1000, so I need to store it in cache as (23,3.45, 4.5, 90, 'd')->1000

foo(30, 1.2, 3.5, 100, 'e') // returns 2000, so I need to store it in cache as (30, 1.2, 3.5, 100, 'e')->2000

foo(23, 3.45, 4.5, 90, 'd') // No need to call this API, I just check in my cache value associated with    
//(23, 3.45, 4.5, 90, 'd'), which is already stored as 1000

Какую стратегию лучше всего реализовать на C ++? какую структуру данных лучше всего составить кеш-таблице?

Answer 1

Одно ключевое замечание: кэширование сложно.

Часто люди думают, что кеширование решит все их проблемы, но они забывают принять во внимание те проблемы, которые оно приносит. Неуправляемый кеш - это не что иное, как гигантская утечка памяти. Следует отметить две стратегии:

• Ограничение размера: всякий раз, когда кэш заполнен, добавление новой записи приводит к выселению другой записи (поэтому вам нужна схема, чтобы решить, когда удалять запись)
• Ограничение по времени: записи удаляются по истечении определенного времени

Обычно, когда мы слышим о кэшах, мы думаем, что LRU (наименее недавно использованный) кэш. Размер кэша ограничен по размеру, и при заполнении кэша запись, которая использовалась в последнее время, удаляется. Примечание: может вызвать конфликт при многопоточности, поскольку доступ только для чтения фактически подразумевает изменение значения .

Такой кеш реализован в терминах двух элементов:

• Отображение (ключ -> значение) с использованием дерева или хэш-карты
• Список приоритетов, который чередуется внутри узлов для эффективности

Если вы пойдете по этому пути, я бы предложил использовать библиотеку Boost.MultiIndex. Существует пример реализации MRU , которая очень похожа на ваши потребности.

Answer 2

Если вы можете использовать boost, посмотрите на boost :: unordered_map , в противном случае вы можете использовать std :: map .Вам нужно будет предоставить функтор для генерации ключа.

Answer 3

Я предлагаю использовать Хеш-таблицу .Вам нужно будет только вычислить хеш-функцию данных.Если хеш достаточно сильный, его можно сохранить и вывести значение без сохранения аргументов.Кроме того, этот метод должен работать быстрее, чем использование std :: map.

В C ++ это может быть реализовано с помощью unordered_map или std :: hash_map.Подойдет очень простая хеш-функция, например Хеш-функция String .

Кстати, метод хранения выходных значений для аргументов называется Memoization

Answer 4

Я бы использовал вложенные карты, поэтому вы используете первый параметр для поиска карты по карте, пока не будет найдена последняя карта, где вы выполняете поиск с использованием последнего параметра, и в результате вы получите ранее кэшированное значение foo.

Когда вы доберетесь до последней карты и обнаружите, что foo не был вызван для этой настройки параметров, вам нужно только сохранить результат foo для последнего параметра.

Answer 5

Поместите их все в структуру

struct mykey{ int a; float b; float c; int d; char e; };

Затем запишите их, хешируйте структуру и используйте ее в качестве ключа

int foo(int a, float b, float c, int d, char e)
{
    mykey tk = { a, b, c, d, e };
    guid key = md5( &tk, sizeof( tk ) );

Answer 6

Хороший вопрос.У вас есть несколько вариантов.Прежде всего, поместите все значения в структуру:

struct values
{
   int a;
   float b;
    ...
};

1. Если одно из значений последовательности наиболее представительное , вы можете просто использоватьstd::map чтобы отобразить это репрезентативное значение в «корзину».Предположим, что наиболее представительным является float b:

   std::map< float, std::list < std::pair< values, int> > >

   , представленное std::list, в котором хранятся пары структур значений и значения результата (intcase).

2. Объявление карты из значений в результат, int.Для этого вы должны позволить сравнивать values struct с другими на карте, поэтому вы должны написать operator<()

:

 int operator<(values const& left, values const& right)
 {
    if (left.a < left.b) ... // compare two values objects
 }

и затем объявите карту как обычно:

std::map<values, int>

Есть другие вопросы, такие как конструкторы копирования и т. д., с которыми вам приходится иметь дело, но это идея.Вы также можете заменить std::map на unordered_map.

Answer 7

Это не всегда работает и в некоторой степени зависит от компилятора, но вы можете изучить использование атрибутов функции. Вас могут заинтересовать атрибуты const или pure . hot также может представлять интерес.