Памятная рекурсивная факториальная функция?

Question

Я знаю, как легко делать заметки в Python, но мне нужен более быстрый способ их вычисления, поэтому я использую C ++. Тем не менее, я понятия не имею, как запоминать. Я понимаю, что речь идет о сохранении значений в массиве или векторе, а затем о его поиске при извлечении, но было бы очень полезно посмотреть, как это делается, чтобы я мог попробовать его скорость.

Answer 1

Просто для забавы, вот небольшой общий мемоизер, который я написал некоторое время назад.Естественно, для этого требуются различные шаблоны:

template <template <typename...> class Container, typename...> struct Memo;

template <typename R, typename... Args, template <typename...> class Container>
struct Memo<Container, R, std::tuple<Args...>>
{
  Memo(std::function<R(Args...)> f) : func(f) { }

  R operator()(Args && ...args)
  {
    const auto arg = std::make_tuple(args...);
    typename CacheContainer::const_iterator it = cache.find(arg);

    if (it == cache.cend())
    {
      it = cache.insert(typename CacheContainer::value_type(arg, func(std::forward<Args>(args)...))).first;
      std::cout << "New call, memoizing..." << std::endl;
    }
    else
    {
      std::cout << "Found it in the cache!" << std::endl;
    }

    return it->second;
  }

private:

  typedef Container<typename std::tuple<Args...>, R> CacheContainer;

  std::function<R(Args...)> func;
  CacheContainer cache;
};


template <typename R, typename... Args>
Memo<std::map, R, std::tuple<Args...>> OMapMemoize(R(&f)(Args...))
{
  return Memo<std::map, R, std::tuple<Args...>>(f);
}
template <typename R, typename... Args>
Memo<std::unordered_map, R, std::tuple<Args...>> UMapMemoize(R(&f)(Args...))
{
  return Memo<std::unordered_map, R, std::tuple<Args...>>(f);
}

Я не совсем уверен, правильно ли я понял rvalue-forwardiness, так как я давно это написал.Во всяком случае, вот контрольный пример:

int foo(double, char) { return 5; }

int main()
{
  auto f = OMapMemoize(foo);
  auto g = UMapMemoize(foo);

  int a, b;

  a = f(1.0, 'a');
  a = f(1.0, 'a');
  a = f(1.0, 'a');
  a = f(1.0, 'a');

  b = g(1.0, 'a');
  b = g(1.0, 'a');
  b = g(1.0, 'a');
  b = g(1.0, 'a');

  return a;
}

Answer 2

Что ж, самый лучший способ сделать это в C ++ - это использовать функциональный объект для хранения запомненных значений. Я думаю, что это, вероятно, немного похоже на ваш декоратор Python, хотя я никогда не делал Python. Код будет выглядеть примерно так:

template <typename T, T (*calc)(T)>
class mem {
  std::map<T,T> mem_map;

public:
  T operator()(T input) {
    typename std::map<T,T>::iterator it;

    it = mem_map.find(input);
    if (it != mem_map.end()) {
      return it->second;
    } else {
      T output = calc(input);
      mem_map[input] = output;
      return output;
    }
  }
};

Код определяет класс шаблона, который принимает имя типа и указатель на функцию, затем в классе определяется оператор функции, позволяющий вызывать его. Оператор функции принимает входное значение, проверяет, присутствует ли указанное значение на карте, затем либо просто возвращает его с карты, либо вычисляет его (используя указатель функции), добавляет его на карту и затем возвращает.

Итак, если вы определили некоторую функцию обработки, например, скажем:

int unity(int in) { return in; }

Вы бы использовали код, подобный этому:

mem<int, unity> mem_unity;
int y;
y = mem_unity(10);

Итак, мы определяем экземпляр класса mem, который принимает наш тип значения и функцию обработки в качестве параметров шаблона, а затем просто вызываем этот класс как функцию.

Answer 3

Никто, кроме студенческой рекурсии, не будет рассчитывать факториалы таким образом.

Запоминание - очень хорошая идея, особенно если вы собираетесь вызывать метод повторно.Зачем выбрасывать хорошую работу?

Еще одним соображением является лучший способ вычисления факториалов: используйте натуральный логарифм гамма-функции.Это будет дольше противостоять переполнению, потому что вы возвращаете двойное значение.Натуральное бревно будет расти медленнее, чем значение.Если вы рассчитываете комбинации, натуральный логарифм меняет умножение и деление на сложение и вычитание.

Но, безусловно, запомните любую реализацию, которую вы используете.Если вы пишете это на C ++, я бы рекомендовал использовать std:map с аргументом x в качестве ключа и ln(gamma(x)) в качестве значения.

Извините, это слишком долго, так как янаписал C ++ и STL.Я бы предпочел использовать хэш-карту с O(1) временем доступа для чтения, чтобы перебирать ключи в O(n).

Answer 4

Мне нравится полагаться на лямбда-захват как в (использует std=c++14)

template<typename R, typename... Args>
auto memoize(std::function<R(Args...)>&& f)
{
  using F = std::function<R(Args...)>;
  std::map<std::tuple<Args...>,R> cache;
  return ([cache = std::map<std::tuple<Args...>,R>{}, 
           f = std::forward<F>(f)](Args&&... args) mutable
    {
      std::tuple<Args...> t(args...);
      if (cache.find(t) == cache.end())
        {
          R r = f(std::forward<Args...>(args)...);
          cache[t] = r;
        }
      return cache[t];
    });
}