Pascal Triangle Recursive Program Optimization en C++

He construido una función recursiva para calcular los valores del triángulo de Pascal.Pascal Triangle Recursive Program Optimization en C++

¿Hay alguna manera de optimizarlo?

recordatorio cortos sobre el triángulo de Pascal: C (n, k) = C (n-1, k-1) + C (n-1, k) Mi código es:

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); 
}

La ineficiencia Lo que veo es que almacena algunos valores dos veces. Ejemplo: C (6,2) = C (5,1) + C (5,2) C (6,2) = C (4,0) + C (4,1) + C (4, 1) + C (4,2) llamará C (4,1) dos veces

¿Alguna idea de cómo optimizar esta función?

Gracias

Fuente

2011-02-23 JohnG

Creo que este es un problema clásico con recursividad su visión, en lugar de volver a calcular estos valores se debe almacenar en una "mesa", como estructura de datos a continuación, en lugar de volver a ejecutar la función que hace una búsqueda en la tabla. Precisamente lo que ha identificado, la superposición de llamar a la función con el mismo valor es un desperdicio del tiempo de procesamiento (transacción clásica de tiempo de proceso/memoria desactivada). No tengo una solución directa para esto, pero definitivamente tienes la idea correcta. – shaunhusain

Una optimización menor es devolver 1 cuando n == k, esto aumentará la velocidad de 'O (Suma (C (n, i) para i de 0 a k))' a 'O (C (n, k)) '. – Neil

@shaunhusain gracias, está claro, ¡asignaré algo de memoria! @Neil buena idea también. – JohnG

La siguiente rutina calculará n-choose-k, utilizando la definición recursiva y la memorización. La rutina es extremadamente rápido y preciso:

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; 
}

Fuente

2011-02-24 03:06:59

Gracias !!! algunos conceptos son nuevos para mí Es bueno ver cómo "memorizar" – JohnG

Mantenga una tabla de resultados obtenidos previamente (indexado por sus n y k valores); la técnica utilizada allí es memoization. También puede cambiar la recursión a una iteración y usar dynamic programming para completar una matriz que contiene el triángulo para n y k valores más pequeños que el que está tratando de evaluar, y luego solo obtener un elemento de él.

Fuente

2011-02-23 19:52:52

Pascal Triangle Recursive Program Optimization en C++

Respuesta

Cuestiones relacionadas