TransWikia.com

Аналог lru_cache в C++

Stack Overflow на русском Asked on November 20, 2021

Есть ли в C++ аналог Python @lru_cache?

Если нет, то как можно написать что-то подобное?

One Answer

Самое близкое, что смог придумать (читать лучше снизу):

#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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP