Stack Overflow на русском Asked on November 20, 2021
Самое близкое, что смог придумать (читать лучше снизу):
#include <iostream>
#include <unordered_map>
#include <list>
#include <type_traits>
struct CacheInfo{
size_t hits;
size_t misses;
size_t currsize;
};
std::ostream& operator << (std::ostream& out, CacheInfo ci){
return out << "hits: " << ci.hits << ", misses: " << ci.misses << ", currsize: " << ci.currsize;
}
// std::hash не поддерживает кортежи, приходится извращаться
template<class T>
struct TupleHash;
template <class... Args>
struct TupleHash<std::tuple<Args...>>{
std::size_t operator()(const std::tuple<Args...>& k) const
{
return combine(k, std::make_index_sequence<sizeof...(Args)>());
}
template<class T> static size_t hashValue(const T& v){ return std::hash<T>()(v);}
static void hashCombine(std::size_t& seed, std::size_t hash_value){
seed ^= hash_value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<size_t... I>
static std::size_t combine(const std::tuple<Args...>& k, std::index_sequence<I...>){
std::size_t result = 0;
for(auto hash: {hashValue(std::get<I>(k))...})
{
hashCombine(result, hash);
}
return result;
}
};
// Кэширование вызовов функций реализуем через странно-рекурсивный шаблон.
// Наследник должен реализовать метод impl с сигнатурой Signature, но рекурсивно вызывать себя через operator()
template<class Signature, size_t MaxSize, class Derived>
class LruCacheBase;
template<class R, class... Args, size_t MaxSize, class Derived>
class LruCacheBase<R(Args...), MaxSize, Derived>{
static_assert(MaxSize > 0);
using args_key = std::tuple<std::remove_reference_t<Args>...>;
using saved_results_list = std::list<std::pair<R, args_key>>;
using saved_results_iter = typename saved_results_list::const_iterator;
// Список сохраненных результатов. Наиболее актуальные в начале списка.
mutable saved_results_list cacheList_;
// Карта для поиска элементиов в списке. Итераторы списка остаются валидными при изменении списка.
mutable std::unordered_map<args_key, saved_results_iter, TupleHash<args_key>> cacheMap_;
// Статистика использования
mutable CacheInfo cacheInfo_;
public:
CacheInfo cacheInfo() const{ return cacheInfo_;}
R operator()(Args... args)const{
auto it = cacheMap_.find(std::tie(args...));
if(it != cacheMap_.end()){
++cacheInfo_.hits;
auto clIt = it->second;
if(clIt != cacheList_.begin()){
auto secondIt = clIt;
++secondIt;
// Переносим узел в начало списка
cacheList_.splice(cacheList_.cbegin(), cacheList_, clIt, secondIt);
}
return clIt->first;
}
++cacheInfo_.misses;
auto ret = static_cast<const Derived&>(*this).impl(args...);
if(cacheList_.size() >= MaxSize){
auto list_it = cacheList_.rbegin();
auto map_it = cacheMap_.find(list_it->second);
cacheMap_.erase(map_it);
cacheList_.pop_back();
}
cacheList_.emplace_front(std::make_pair(ret, std::forward_as_tuple(args...)));
cacheMap_.emplace(std::forward_as_tuple(std::move(args)...), cacheList_.begin());
cacheInfo_.currsize = cacheList_.size();
return ret;
}
};
std::uint64_t simple_fib(std::uint64_t n){
if(n < 2){
return n;
}
return simple_fib(n - 1) + simple_fib(n - 2);
}
struct CachedFib: public LruCacheBase<std::uint64_t(std::uint64_t), 30, CachedFib>{
// Собственно, рекурсивная реализация
std::uint64_t impl(std::uint64_t n) const{
// operator () делает ссылку на this похожей на функцию, которая
// внутри кэширует значение и вызывает impl(...), если нужно
auto& fib = *this;
if(n < 2){
return n;
}
return fib(n - 1) + fib(n - 2);
}
};
int main()
{
const CachedFib cachedFib{};
for(std::uint64_t i = 0; i < 70; ++i){
std::cout << cachedFib(i) << " ";
}
std::cout << std::endl << cachedFib.cacheInfo()<< std::endl;
// У меня зависает на 50 из-за рекурсии.
for(std::uint64_t i = 0; i < 40; ++i){
std::cout << simple_fib(i) << " ";
}
std::cout << std::endl;
return 0;
}
Answered by Ariox on November 20, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP