Каков наилучший способ представления древовидной структуры в памяти как кеш?

Question

Привет всем У меня есть дерево с узлами. Узлы построены по значению ответа на запрос TCP API. Чтобы делать меньше запросов, я хотел бы представить дерево в структуре кэша, которая будет каждый раз, когда будет вызываться TCP-запрос Сначала он проверит кеш. Каков наилучший способ сделать это? Я имею в виду часть дерева кеша, в моем случае я использую Qt и C ++.

Answer 1

Вы можете использовать std:map<TCPRequest, TCPResponse> для достижения этой цели.Ваш запрос и ответ могут быть строковыми, и в этом случае они могут сократиться до std:map<std::string, std::string>.в противном случае вам необходимо убедиться, что ваш класс TCPRequest поддерживает operator<, чтобы разрешить двоичный поиск по карте.

Ваш код может выглядеть примерно так:

#include <map>

std::map<TCPRequest, TCPResponse> responseCache;
typedef std::map<TCPRequest, TCPResponse>::const_iterator cacheCIterator;

TCPRequest nextRequest;
cacheCIterator iter = responseCache.find(nextRequest);
if (iter != responseCache.end())
{
  return iter->second;  // found cached response
}
else
{
  // issue the request
  TCPResponse response = issueRequest(nextRequest);

  //save the response
  responseCache[nextRequest] = response;
  return response;
}  

Вы такжеНужно учитывать срок действия кэша, если ваш трафик не достаточно мал, чтобы вы могли просто кэшировать все ответы.В какой-то момент вы хотите erase() TCPResponse объектов с карты, возможно, сохраняя отдельную структуру, которая сообщает вам, какой ответ использовался реже всего (LRU).

Имея это в виду, некоторый уникальный идентификатор (монотонно увеличивающийся int будет работать) может использоваться в ваших TCPResponse объектах в качестве прокси для полных объектов, позволяя вам идентифицировать кэш иLRU отвечает, используя int s вместо полных экземпляров класса.Тем не менее, вам все равно нужно полное сравнение TCPRequest, чтобы гарантировать, что кеш работает должным образом.

Answer 2

Возможно, вы захотите рассмотреть хеш-карту в случае, если количество ожидающих запросов велико. Смотрите QHash в библиотеке QT или std :: hash_map (в зависимости от разновидности используемого вами STL).