Кэшированные или предварительно вычисленные Неизменяемые функции в C # / C ++
-
06-07-2019 - |
Вопрос
Под "неизменяемой функцией" или "неизменяемым методом" я подразумеваю функцию, результат которой никогда не изменится, если вы зададите ей одни и те же аргументы.
Мне было бы интересно узнать, знает ли кто-нибудь о более общем или менее подробном решении, когда вы хотите кэшировать предварительно вычисленные значения неизменяемой функции.
Позвольте мне объяснить, что я имею в виду, на простом примере:
//Let's assume that ComputeStuff() returns a widely used value
//and that
//1. It is immutable (it will always return the same result)
//2. its performance is critical, and it cannot be accepted to compute
// the result at each call, because the computation is too slow
//I show here a way to solve the problem, based on a cached result.
//(this example works in a case of a method with no arguments.
// A hash would be required in order to store multiple precomputed results
//depending upon the arguments)
private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
if (mComputeStuff_Cached != null)
return mComputeStuff_Cached ;
string result;
//
// ...
//Do lots of cpu intensive computation in order to compute "result"
//or whatever you want to compute
//(for example the hash of a long file)
//...
//
mComputeStuff_Cached = result;
return mComputeStuff_Cached ;
}
Примечания:
- Я добавил тег C ++, поскольку решение на C ++ также могло бы меня заинтересовать
- Концепция "неизменяемых функций" является общей для разработчиков баз данных, поскольку функция может быть определена как "неизменяемая" или "неизменяемая в транзакции" (это хороший способ повысить производительность запросов).
Заранее спасибо
Решение
"Запоминание" здесь может оказаться полезным термин.Существует несколько библиотек запоминания (я мог бы поклясться, что в повышение, но в данный момент я не могу его найти).Выполнив поиск в Интернете по "memoize" или "запоминание" и выбранному вами языку, вы обнаружите несколько обращений.
Вот отличная статья в Wikibooks: Оптимизация C ++/Общие методы оптимизации/Запоминание
Другие советы
Ну, используя делегат, такой как Func<T>
может сделать его более пригодным для повторного использования, не требуя полиморфизма / наследования - но в C нет ничего более "встроенного"#:
using System;
static class Program {
static void Main() {
var func = CachedFunc.Create(() => int.Parse(Console.ReadLine()));
Console.WriteLine(func.Value);
Console.WriteLine(func.Value);
}
}
static class CachedFunc {
public static CachedFunc<T> Create<T>(Func<T> func) {
return new CachedFunc<T>(func);
}
}
class CachedFunc<T> {
T value;
Func<T> func;
public CachedFunc(Func<T> func){
if (func == null) throw new ArgumentNullException("func");
this.func = func;
}
public T Value {
get {
if (func != null) {
value = func();
func = null;
}
return value;
}
}
public static explicit operator T(CachedFunc<T> func) {
return func.Value; }
}
вы могли бы попробовать что-то вроде этого:
#include <functional>
#include <type_traits>
#include <map>
#include <tuple>
//requires c++14
auto add_function_cache = [](auto fun) {
using fun_type = decltype(fun);
return ([=](auto... run_args){
using fun_return_type = std::result_of_t<fun_type(decltype(run_args)...)>;
static std::map<
std::tuple<decltype(run_args)...>,
fun_return_type
> result_cache;
std::tuple<decltype(run_args)...> tuple(run_args...);
if (result_cache.find(tuple) == result_cache.end()) {
fun_return_type rv = fun(run_args...);
result_cache[tuple] = rv;
return rv;
}
else {
return result_cache[tuple];
}
});
};
template <typename R, class... Args> auto
add_function_cache_old(std::function<R(Args...)> fun)
-> std::function<R(Args...)>
{
std::map<std::tuple<Args...>, R> cache;
return [=](Args... args) mutable {
std::tuple<Args...> t(args...);
if (cache.find(t) == cache.end()) {
R rv = fun(args...);
cache[t] = rv;
return rv;
}
else {
return cache[t];
}
};
};
А затем используйте его следующим образом:
//function_cache - usage
auto fib_cache = add_function_cache(&fib);
//function_cache_old - usage
function<decltype(fib)> fib_fn = &fib;
auto fib_cache_old = add_function_cache_old(fib_fn);
fib_cache(10);
fib_cache(10);
Идея состоит в том, чтобы создать функцию, которая принимает функцию (fun) в качестве аргумента и возвращает другую функцию.Возвращаемая функция обертывает fun и предоставляет в результаты входные параметры формы сопоставления (run_args).Таким образом, он имеет ту же подпись, что и fun, утомляет поиск результата для заданных параметров (run_args) на карте (кэш).Затем он возвращает кэшированное значение или результат, вычисленный fun.Очевидно, что результат fun должен быть добавлен в кэш в случае неудачного поиска.
С уважением
Янв.
Вы можете сделать его немного менее подробным:
private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
if (mComputeStuff_Cached == null) {
string result;
//
// ...
//Do lots of cpu intensive computation in order to compute "result"
//or whatever you want to compute
//(for example the hash of a long file)
//...
//
mComputeStuff_Cached = result;
}
return mComputeStuff_Cached ;
}
Другие примечания по этому типу рисунка:
- Если вы используете C ++, и такой метод
const
, тогда изменение элементов будет невозможно , поскольку они также обрабатываются какconst
в контексте этого метода.Однако вы можете переопределить это, пометив элемент (ы), который (которые) вам нужно изменить, какmutable
. - Существует разница между "семантической константой" и "побитовой константой".Когда автор отмечает что - то как
const
, обычно они означают "семантическую константу" (именно это вы имеете в виду в данном случае), но компилятор может применять только "побитовую константу". const
методы обычно создают у вызывающего объекта впечатление, что они могут быть вызваны из нескольких потоков одновременно, поскольку у них нет побочных эффектов.В этом типе шаблона у вас есть "побитовый" побочный эффект, но нет "семантического" побочного эффекта.Поэтому, если возможно, что такой метод могут вызывать несколько потоков, вы должны внутренне защитить эту инициализацию.
Вы можете сделать свою переменную-член изменяемой (ключевое слово).
Это позволит функции-члену const изменять это значение.Я использую его постоянно для кэширования промежуточных результатов.
Вы можете переписать этот код почти дословно на C ++
class CClass
{
private:
std::string* mComputeStuff_Cached;
public:
CClass()
mComputeStuff_Cached(NULL)
{
}
~CClass()
{
delete mComputeStuff_Cached;
}
std::string ComputeStuff()
{
if (mComputeStuff_Cached != NULL)
{
return mComputeStuff_Cached
}
else
{
std::string calcedAnswer;
...
// store away answer
mComputeStuff_Cached = new std::string(calcedAnswer);
}
}
};
Я не уверен, достаточно ли проверки, чтобы убедиться, что mComputeStuff_Cached пуст().Возможно, что empty() - это законно кэшированный результат.
Вы могли бы использовать static
ключевое слово внутри функции.Он будет вычислен только один раз:
std::string GetWidelyUsedValue()
{
static std::string value = ComputeStuff() ;
return value ;
}
std::string ComputeStuff()
{
// Compute the string here.
}
Решение на C ++ было бы очень похоже на то, что вы описали, отличаясь только пьянящим сочетанием const
квалифицированный публичный интерфейс (ы) и (некоторые) mutable
Участники:
class Computer {
mutable string cache;
public:
// I wouldn't call it ComputeXXX
// since I want to hide the implementation
// details from my client: for the client
// there is no change in state due to a call
// to this function
const string& StringVal() const {
if (cache.empty()) {
// compute cache
}
return cache;
}
// ...
};