Статическая переменная в функции шаблона не кажется уникальной для экземпляра шаблона

Я пытаюсь узнать об мемоизации с помощью C++ вместе с boost и спецификацией C++11. . Однако я столкнулся с проблемой, с которой у меня проблемы. Я следую руководству здесь: Запоминание в C и учебник говорит, что вы можете обобщить запоминание рекурсивных функций, используя шаблоны и лямбда-функции. В руководстве также перечислены рекурсивные функции факториала и Фибоначчи для использования с шаблоном. Однако руководство использует только функцию Фибоначчи.

Я написал тестовую программу, чтобы увидеть, как все это работает, и сделать как мемоизированную функцию Фибоначчи, так и факториал в одном запуске. Дело в том, что шаблон мемоизации использует статическую карту для хранения кэшированных значений, и похоже, что карта не уникальна для каждого экземпляра мемоизированных функций. Ожидается ли это? Что нужно сделать, чтобы сделать карту уникальной для каждого экземпляра шаблона? Прежде чем я начал использовать функции C++11, я пытался создать класс шаблона, который принимал бы функцию повышения для инкапсуляции этого процесса. Будет ли статическая карта уникальной в классе шаблона?

Основная логика создания мемоизированных функций

// Template function to create memoized versions of recursive lambda functions
template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   return [foo](inType n) {
      static std::map<inType, outType> memo;

      outType ret;
      if (memo.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = memo[n];
         return ret;
      }
      ret = foo(n);
      memo[n] = ret;
      return ret;
   };
}

// Recursive lambda fibonacci function
std::function<int(int) > fibonacci_r = [](int n) {
   if (n <= 1) {
      return n;
   } else {
      return fibonacci_r(n - 1) + fibonacci_r(n - 2);
   }
};

// Recursive lambda factorial function
std::function<int(int) > factorial_r = [](int n) {
   if (n == 0) {
      return 1;
   } else {
      return n * factorial_r(n - 1);
   }
};

Логика для тестирования мемоизированных функций

int position = 7;
cout << "Fibonacci:" << endl;
cout << "Non Memo Fibonacci" << endl;
cout << position << "-> " << fibonacci_r(position) << endl;
cout << "Memo Fibonacci" << endl;
fibonacci_r = memoize(fibonacci_r);
cout << position << " -> " << fibonacci_r(position) << endl;

cout << endl;

cout << "Non Memo Factorial" << endl;
cout << position << " -> " << factorial_r(position) << endl;
cout << "Memo Factorial" << endl;
factorial_r = memoize(factorial_r);
cout << position << " -> " << factorial_r(position) << endl;

Вывод

Fibonacci:
Non Memo Fibonacci
7-> 13
Memo Fibonacci
Cache Hit
Cache Hit
Cache Hit
Cache Hit
Cache Hit
7 -> 13

Non Memo Factorial
7 -> 5040
Memo Factorial
Cache Hit
7 -> 13

В конце вывода вы можете увидеть, что факториал Memo попал в кеш. Однако я не думаю, что он должен иметь только 1 попадание в кеш. В любом случае, 7! не равно 13, а 13 является значением кэша для 7 в лямбда-памятке Фибоначчи.


c++ boost templates static-variables c++11
person zero298    schedule 22.10.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Когда вы пишете

... кажется, что карта не уникальна для каждого экземпляра запоминаемых функций. Ожидается ли это?

вы, кажется, забываете, что экземпляр по отношению к static переменным основан на типах, а не на значении параметров. Тип std::function<outType(inType)> один и тот же в обоих случаях. Очевидно, что когда есть только один экземпляр, у вас также есть только один статический map.

Частичное решение может быть таким:

template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   static int i = 0;
   ++i;
   return [foo](inType n) {
      static std::map<int, std::map<inType, outType>> memo;
      auto& m = memo[i];
      outType ret;
      if (m.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = m[n];
         return ret;
      }
      ret = foo(n);
      m[n] = ret;
      return ret;
   };
}

Но обратите внимание, что теперь каждый вызов будет генерировать свой собственный независимый map. Если вы сделаете:

auto f1 = memoize(factorial_r);
auto f2 = memoize(factorial_r);

тогда f1 и f2 не будут использовать один и тот же map. Это также означает, что если вы делаете это очень часто, вы можете использовать много памяти.

person Daniel Frey    schedule 22.10.2013
comment
Хорошо, это имеет большой смысл. Я немного почитал и понял, как создаются экземпляры шаблонов функций, то есть во время компиляции посмотреть, что использует эту функцию шаблона и какие типы передаются, а затем создать новую функцию для использования. Однако не будет ли каждый вызов лямбды также создавать новую карту? Или лямбда работает так же, как она создается во время компиляции, и каждая лямбда, имеющая общую сигнатуру, будет использовать статическую карту? - person zero298; 23.10.2013
comment
@zero298 type лямбды (замыкание) существует только один раз. Каждый вызов дает вам еще один экземпляр этого типа, но, как и в случае с функциями, закодированный лямбда-код не копируется в каждый экземпляр. Сам код генерируется компилятором только один раз (за inType/outType, разумеется). - person Daniel Frey; 23.10.2013
comment
Ах, очень круто. На самом деле я не собирался использовать это ни в чем, просто как инструмент обучения. Приятно узнать некоторые аспекты этих вещей, которые я не совсем понял. Я собираюсь пойти дальше и принять ваш ответ, поскольку в нем говорится, почему он не работает, и это хорошая альтернатива. - person zero298; 23.10.2013