Автоматическое запоминание с поддержкой рекурсивной функции
Сообщение в блоге Автоматическая памятка в c ++ 0x предоставляет функцию для создания запомненной версии существующей функции. Сообщение в блоге и связанный с ним код были обсуждены ранее на стековом потоке (например, Что делает этот код C ++ 11?), однако, ни одно из этих решений не может обеспечить полностью универсальный мемоизер, который также способен правильно запоминать рекурсивные функции.
Конечно, есть хитрость в изменении рекурсивного вызова с помощью чего-то вроде этого (если предположить, что у нас есть мемоизер, такой как тот, который представлен в посте блога под названием memoize уже на месте)
std::function<int (int)> f;
int fib(int n) {
if (n < 2) return n;
return f(n-1) + f(n-2);
}
int main(void) {
f = memoize(std::function<int (int)>(fib));
}
Но это больше похоже на обходной путь, чем на правильное решение, потому что нам все еще нужен доступ к функции, которую мы хотим запомнить. Надлежащее решение должно быть в состоянии полностью запомнить любую функцию, в том числе те, которые определены в некоторой библиотеке. Однако создание такого решения, как мне кажется, за пределами моей досягаемости (при условии, что это возможно), поэтому я спрашиваю:
Возможна ли действительно универсальная функция запоминания?
Как можно ли достичь такого подвига?
И если это невозможно, есть ли способ обобщить вышеуказанный подход. Что-то вроде (не компилируется и не является допустимым C ++):
int fib(int n){
if (n < 2) return n;
return this_func(n-1) + this_func(n-2);
}
куда this_func это то, что похоже на this указатель класса, но для функции. [Редактировать: Это, вероятно, все еще страдает от проблемы this_func указатель будет указывать на fib вместо запомненного fib]
Решение
Поскольку кэш должен быть разделен между вызовами функций, вам придется либо передать его в качестве аргумента, либо поделиться им в противном случае. Одним из способов поделиться им является использование функционального объекта:
struct fib
{
std::map<std::tuple<int>, int> cache;
int operator()(int n)
{
if(n < 2) return n;
auto memoize = [this](int p)
{
auto i = cache.find(p);
if(i == cache.end()) i = cache.insert({p, (*this)(p)}).first;
return i->second;
};
return memoize(n-1) + memoize(n-2);
}
};
Где вы можете выделить memoize часть.
Есть также трюк с временным временем жизни, чтобы передать запомненную функцию в качестве аргумента; что-то вроде этого:
struct recurse // possibly a class template
{
std::function<int(int, recurse const&)> f; // possibly `mutable`
template<class T>
recurse(T&& p) : f( memoize(decltype(f){p}) )
{}
int operator()(int x) const
{
return f(x, *this);
}
};
int fib(int n, recurse const& f);
int fib(int n, recurse const& f = {fib})
{
if(n < 2) return n;
return f(n-1) + f(n-2); // or `fib(n-1, f) + fib(n-2, f)`
}
Тем не менее, это требует изменения memoizeкак recurse const& не может (и не должен) быть частью внутреннего map,
Нотабене те const& также может быть && для продления жизни, однако, это может сбивать с толку из-за семантики перемещения
Другие решения
Следующие могут помочь, но это все-таки взломать, и это некрасиво …
int fib(void* f, int n)
{
if (n < 2) return n;
auto this_func = *reinterpret_cast<std::function<int (void*, int)>*>(f);
return this_func(f, n - 1) + this_func(f, n - 2);
}int main(int argc, char *argv[])
{
std::function<int (void*, int n)> fib1 = &fib;
std::cout << fib1(reinterpret_cast<void*>(&fib1), 5) << std::endl;
auto f = memoize(fib1);
std::cout << f(reinterpret_cast<void*>(&f), 5) << std::endl;
return 0;
}
я использую void* поскольку правильная подпись является рекурсивной: — /
Я предполагаю, что это невозможно, оставаясь в рамках определенного поведения, потому что нет способа абстрагировать рекурсивный вызов. На самом деле, я не могу придумать ничего лучше, чем предоставленная вами версия глобальной переменной.
Одна очевидная идея предоставить абстракцию, более надежную, чем глобальная переменная, состоит в том, чтобы добавить функцию для рекурсии в качестве первого аргумента:
int fib(std::function<int (int)> rec, int n)
{
if (n < 2) return n;
return rec(n - 1) + rec(n - 2);
}
Затем вы можете изменить функцию memoize, чтобы передать записанную версию в первый аргумент, и все должно работать. Этот прием часто используется для достижения той же цели в функциональных языках (однотипных / нетипизированных), таких как схемы.
Тем не менее, этот вид трюка опирается на то, что называется «Y комбинатор» который, я думаю, не может существовать в C ++, поскольку он имеет бесконечный тип.