Оптимизация рекурсивной программы Pascal Triangle на C++

Я построил рекурсивную функцию для вычисления значений треугольника Паскаля.

Есть ли способ оптимизировать его?

Краткое напоминание о треугольнике Паскаля: C(n, k) = C(n-1, k-1) + C(n-1, k) Мой код:

int Pascal(int n, int k) {
if (k == 0) return 1;
if (n == 0) return 0;
return Pascal(n - 1, k - 1) + Pascal(n - 1, k);
}

Неэффективность, которую я вижу, заключается в том, что он сохраняет некоторые значения дважды. Пример: С(6,2) = С(5,1) + С(5,2) С(6,2) = С(4,0) + С(4,1) + С(4,1) + C(4,2) дважды вызовет C(4,1)

Любая идея, как оптимизировать эту функцию?

Спасибо


c++ recursion combinatorics pascals-triangle
person JohnG    schedule 23.02.2011    source источник
comment
Я думаю, что это классическая проблема с рекурсией, которую вы видите, вместо того, чтобы пересчитывать эти значения, вы должны хранить их в таблице, такой как структура данных, а затем вместо повторного запуска функции вы выполняете поиск в таблице. Именно то, что вы определили, перекрытие вызова функции с одним и тем же значением является пустой тратой времени обработки (классический компромисс между временем обработки и памятью). У меня нет прямого решения для этого, но у вас определенно есть правильная идея.   -  person shaunhusain    schedule 23.02.2011
comment
Одна небольшая оптимизация состоит в том, чтобы вернуть 1, когда n == k, это увеличит скорость с O(Sum(C(n, i) for i from 0 to k)) до O(C(n, k)).   -  person Neil    schedule 23.02.2011
comment
@shaunhusain спасибо, все ясно, я выделю немного памяти! @Нил тоже хорошая идея.   -  person JohnG    schedule 24.02.2011

Ответы (2)


arrow_upward
9
arrow_downward

Следующая процедура будет вычислять n-выбор-k, используя рекурсивное определение и запоминание. Процедура чрезвычайно быстрая и точная:

inline unsigned long long n_choose_k(const unsigned long long& n,
                                     const unsigned long long& k)
{
   if (n  < k) return 0;
   if (0 == n) return 0;
   if (0 == k) return 1;
   if (n == k) return 1;
   if (1 == k) return n;

   typedef unsigned long long value_type;

   class n_choose_k_impl
   {
   public:

      n_choose_k_impl(value_type* table,const value_type& dimension)
      : table_(table),
      dimension_(dimension / 2)
      {}

      inline value_type& lookup(const value_type& n, const value_type& k)
      {
         const std::size_t difference = static_cast<std::size_t>(n - k);
         return table_[static_cast<std::size_t>((dimension_ * n) + ((k < difference) ? k : difference))];
      }

      inline value_type compute(const value_type& n, const value_type& k)
      {
         // n-Choose-k = (n-1)-Choose-(k-1) + (n-1)-Choose-k
         if ((0 == k) || (k == n))
            return 1;
         value_type v1 = lookup(n - 1,k - 1);
         if (0 == v1)
            v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);
         value_type v2 = lookup(n - 1,k);
         if (0 == v2)
            v2 = lookup(n - 1,k) = compute(n - 1,k);
         return v1 + v2;
      }

      value_type* table_;
      const value_type dimension_;
   };

   static const std::size_t static_table_dim = 100;
   static const std::size_t static_table_size = static_cast<std::size_t>((static_table_dim * static_table_dim) / 2);
   static value_type static_table[static_table_size];
   static bool static_table_initialized = false;

   if (!static_table_initialized && (n <= static_table_dim))
   {
      std::fill_n(static_table,static_table_size,0);
      static_table_initialized = true;
   }

   const std::size_t table_size = static_cast<std::size_t>(n * (n / 2) + (n & 1));

   unsigned long long dimension = static_table_dim;
   value_type* table = 0;

   if (table_size <= static_table_size)
      table = static_table;
   else
   {
      dimension = n;
      table = new value_type[table_size];
      std::fill_n(table,table_size,0LL);
   }

   value_type result = n_choose_k_impl(table,dimension).compute(n,k);

   if (table != static_table)
      delete [] table;

   return result;
}
person Community    schedule 24.02.2011

arrow_upward
7
arrow_downward

Сохраняйте таблицу ранее возвращенных результатов (индексированных по их значениям n и k); здесь используется метод запоминание. Вы также можете изменить рекурсию на итерацию и использовать динамическое программирование для заполнения массива, содержащего треугольник для значений n и k меньше, чем то, которое вы пытаетесь оценить, просто получите из него один элемент.

person Jeremiah Willcock    schedule 23.02.2011