C++ / folding

Bienvenidos sean a este post, hoy veremos otro concepto de iteracion.

Tambien conocido como reduccion es el proceso de combinar una coleccion de valores juntos para generaar un numero reducido de resultados pero la mayoria del tiempo estaremos hablando de un solo resultado. Por esto podemos considerar que folding abstrae el proceso de la iteracion sobre estructuras que son recursivas de manera natural. Por ejemplo, tomemos a vector los cuales tienen una naturaleza recursiva en terminos de acceso a sus elementos. Si bien su naturaleza recursiva es discutible, podemos consideraar a vector recursivo porque para acceder a sus elementos incrementamos su indice. Para poder utilizar a tales estructuras, debemos mantener un seguimiento del resultado en cada paso y luego procesar al siguiente elemento para ser combinado con el resultado previo mas adelante. A folding tambien se lo denomina como left o right folding dependiendo de la direccion donde se procesan los elementos en la coleccion.

Tomemos como ejemplo a la funcion accumulate, esta es un perfecto ejemplo de funcionalidad de folding porque combina valores en una coleccion. Analicemos el siguiente ejemplo:

#include <iostream>
#include <numeric>
#include <vector>

int main()
{
        std::vector<double> vec{1.9, 2.2, 3.4, 4.7, 5.1};
        double sum = std::accumulate(vec.begin(), vec.end(), 0.0);
        std::cout << sum << std::endl;

        return 0;
}

Para poder utilizarlo necesitamos a la libreria numeric. En el main, definimos un vector con algunos valores para luego definir una variabble donde almacenaremos el resultado devuelto por la funcion accumulate. El primer argumento sera un objeto iterador y sera desde cual elemento empezaremos, por eso es begin, el siguiente es para indicar cual es el ultimo objeto iterador para definir el rango de trabajo, y el ultimo argumento sera el valor inicial con el cual comenzaremos a acumular. Por ultimo, mostraremos el resultado almacenado en la variable sum. Compilemos y veamos la salida:

$ ./folding
17.3
$

Un tema a tener en cuenta a la hora de usar accumulate es el valor inicial. Por ejemplo, si pasan el valor 0 la funcion solo sumara los valores enteros e ignorara los decimales. Por ejemplo, en el codigo anterior devuelve el valor de 15, lo cual es correcto si solo consideramos los valores enteros. Tomemos el codigo anterior y hagamos el siguiente cambio:

#include <iostream>
#include <numeric>
#include <vector>

int main()
{
        std::vector<double> vec{1.9, 2.2, 3.4, 4.7, 5.1};
        auto sum = std::accumulate(vec.begin(), vec.end(), 1,
                std::multiplies<int>());
        std::cout << sum << std::endl;

        return 0;
}

Una caracteristica que no mencionamos de accumulate es que tambien es una funcion de orden superior. Por lo tanto, podemos usar lo producido para otra funcion. En este nuevo codigo, no acumularemos los valores del vector sino que calcularemos el producto de todos ellos. Como usaremos una multiplicacion debemos cambiar el valor de 0 a 1 como valor inicial. Luego tenemos la encargada de realizar esta tarea, multiplies, que toma el valor previo y lo multiplica por el actual. Y el resultado lo tomara como previo para multiplicarlo por el nuevo que es el actual, y asi sucesivamente hasta finalizar el vector. Compilemos y veamos como es la nueva salida:

$ ./folding
120
$

Pero tambien tenemos una alternativa a accumulate como es reduce. Tomemos el codigo anterior y hagamos el siguiente cambio:

#include <iostream>
#include <numeric>
#include <vector>

int main()
{
        std::vector<double> vec{1.9, 2.2, 3.4, 4.7, 5.1};
        auto sum = std::reduce(vec.begin(), vec.end(), 1,
                std::multiplies<int>());
        std::cout << sum << std::endl;

        return 0;
}

En lugar de usar accumulate le pasamos reduce sin necesitar ninguna modificacion extra. Debemos obtener la misma salida si lo compilan y ejecutan. Una ventaja principal con respecto a accumulate es que no lo procesa necesariamente en orden secuencial a los elementos de la coleccion. Tambien permite aplicar politicas para poder manipular la informacion. Por ejemplo, en lugar de procesarlas en forma secuencial lo podemos hacer en paralelo, por citar un ejemplo. Y si bien reduce puede ser mas rapido que accumulate, debemos ser cuidadosos al momento de operar con operaciones binarias no conmutativas.

En resumen, hoy hemos visto a folding, que es, para que sirve, como se aplica, para que nos puede ser util, asi un par de ejemplos practicos para verlo en accion. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.