Divide y vencerás es un paradigma algorítmico (a veces llamado por error Divide y Concurrir - una adaptación en broma), similar a los paradigmas de programación Dinámica y Algoritmos ávidos o glotones. Un algoritmo Divide y Vencerás típico resuelve un problema siguiendo estos 3 pasos.

1. Dividir: Descomponer el problema en sub-problemas del mismo tipo. Este paso involucra descomponer el problema original en pequeños sub-problemas. Cada sub-problema debe representar una parte del problema original. Por lo general, este paso emplea un enfoque recursivo para dividir el problema hasta que no es posible crear un sub-problema más.
2. Vencer:  Resolver los sub-problemas recursivamente. Este paso recibe un gran conjunto de sub-problemas a ser resueltos. Generalmente a este nivel, los problemas se resuelven por sí solos.
3. Combinar: Combinar las respuestas apropiadamente. Cuando los sub-problemas son resueltos, esta fase los combina recursivamente hasta que estos formulan la solución al problema original. Este enfoque algorítmico trabaja recursivamente y los pasos de conquista y fusión trabajan tan a la par que parece un sólo paso.

Usualmente este método nos permite hacer una reducción bastante significativa en la complejidad tiempo del algoritmo a emplear.

Por ejemplo, el método de la burbuja conlleva una complejidad de  O(n^2), mientras que el quicksort (una aplicación de Dividir y Vencer) reduce la complejidad a O(nlog(n)). La búsqueda linear tiene una complejidad de O(n), mientras que la búsqueda binaria(otra aplicación de dividir y vencer) reduce la complejidad a  O(log(n)).

A continuación algunos de los algoritmos estándar de la variedad dividir y vencer

Búsqueda Binaria, es un algoritmo de búsqueda. En cada paso, el algoritmo compara el parámetro de entrada (x) con el valor del elemento en la mitad del arreglo. Si los valores coinciden, retorna el índice del elemento medio. De lo contrario, si x es mejor al elemento medio, el algoritmo recurre a la mitad izquierda del elemento medio, de lo contrario retorna la mitad a la derecha del elemento medio.

Quicksort, es un algoritmo de ordenamiento. El algoritmo elige un elemento pivote, reordena los elementos del arreglo de forma que todos los elementos de menor valor al del elemento pivote se mueven hacia su izquierda y los elementos de mayor valor hacia su derecha. Finalmente, el algoritmo ordena los sub-arreglos recursivamente hacia la izquierda y derecha del elemento pivote.

Merge Sort, es también un algoritmo de ordenamiento. Este algoritmo divide el arreglo en dos partes, ordenada cada una de ellas recursivamente, y finalmente une las dos partes ya ordenadas. El tiempo de complejidad de este algoritmo es de  O(nLogn), en el mejor caso, caso medio y en el peor de los casos. La complejidad de tiempo puede ser entendida fácilmente recurriendo a la ecuación: T(n) = 2T(n/2) + n.

Par de puntos más cercanos, El problema es encontrar el par de puntos más cercano a otra par dado en el plano XY. Este problema puede ser resuelto en un tiempo O(n^2) calculando la distancia de cada par de puntos y comparando las distancias hasta encontrar la menor. El algoritmo de tipo Dividir y Vencer resuelve este problema en un tiempo  O(nLogn).

Algoritmo de Strassen es un algoritmo eficiente para multiplicar dos matrices. Un método simple para multiplicar dos matrices requiere 3 bucles anidados lo que nos da una complejidad de  O(n^3).  El algoritmo de Strassen multiplica dos matrices en un tiempo de  O(n^2.8974).

El Algoritmo Cooley–Tukey de Transformación Rápida de Fourier (FFT) es el algoritmo más común de FFT (Transformación Rápida de Fourier en inglés). Es un algoritmo de tipo Dividir y Vencer que opera en un tiempo de O(nlogn).

El algortimo de Karatsuba, este fue el primer algoritmo de multiplicación más rápido asintóticamente que el algoritmo cuadrático clásico de multiplicación. Este algoritmo consigue reducir la multiplicación de dos números de n dígitos a como máximo de  n^1.585( que es la aproximación del logaritmo de 3 en base 2) multiplicaciones de un dígito. Por lo tanto es más rápido que el algoritmo clásico que requiere el producto de n^2 de números de un dígito.

Dividir y vencer (D & V) vs programación dinámica (DP)

Ambos paradigmas (D & V y PD) dividen un problema cualquiera en sub problema y resuelve cada uno de ellos. ¿Cómo elegir uno de ellos para un problema? Dividir y Vencer debe ser empleado cuando los sub problemas no son evaluados muchas veces. De lo contrario programación dinámica o memoización debería emplearse en su lugar.

Por ejemplo, la Búsqueda Binaria es un algoritmo Dividir y Vencer, nunca evaluaremos los sub problema más de una vez. Por otro lado, el cálculo del Número Fibonacci se debe preferir la aplicación de Programación Dinámica.

Traducción del Artículo - Divide and Conquer Algorithm Meaning: Explained with Examples

Hace poco creé mi propia cuenta personal en Gitlab solo por el hecho que GitLab me ofrecía una forma muy fácil de automatizar mi proceso de compilación y despliegue de una aplicación simple de una página en React usando tan solo un archivo  .gitlab-ci.yml

Sin embargo, cuando obtuve acceso al beta de GitHub Actions tenía que darle un intento. Así que decidí construir algo similar.

¡Muéstrame el código!

Si ya tienes una idea de qué acciones son y solo quieres ver el código relacionado, siéntete libre de explorar el repositorio para este artículo en el siguiente enlace: https://github.com/pedsm/tryGithubAction

Un breve descargo

Toda mi experiencia con GitHub Action hasta el momento está basada en su versión beta, así tenlo en consideración. Pueda que muchas de las cosas de las que hablo aquí no sean liberadas en versión final, además ignoraré los errores y comportamientos raros que he ido encontrando.

¿Qué es?

GitHub Actions te permite automatizar tareas a ser completadas cuando algo sucede en tus repositorios (como pushes, issues, versión y demás). Esto significa que puedes configurar tu repositorio de manera tal que pueda ser automáticamente probado y desplegado cada vez hay un nuevo commit, que es exactamente lo que yo hice.

Como ya mencioné, la única razón por la que decidí crear una cuenta en GitLab fue la posibilidad de tener un flujo de trabajo en el cual todo nuevo código agregado al Master sea desplegado directamente al sitio web, entonces decidí recrear esto exactamente.

La Configuración

Una vez que tienes acceso a GitHub Action, verás una nueva pestaña con el nombre de Actions en tus repositorios. En ella podrás crear tu primer flujo de trabajo. Un flujo de trabajo es un archivo de flujo de trabajo que vive dentro del .github que ya se usa para otras cosas, como plantillas de relaciones públicas y otras configuraciones de GitHub específicas del repositorio.

GitHub Actions viene con un editor gráfico completamente equipado para tus flujos de trabajo. Esto es un soplo de aire fresco si pensaste que ibas a tener que aprender un nuevo esquema YAML or algún lenguaje específico a la tecnología como en el caso de Jenkinsfile. Por otro lado, si no quieres usar ninguna de estas alucinantes herramientas gráficas siempre puedes editar el archivo .workflow a tu gusto.

Los archivos de Workflow usan el lenguaje de configuración HashiCorp(conocido también como HCL). Si conoces de Terraform, este lenguaje se te hará familiar.

Las diferencias

Si has implementado algún tipo de prueba automatizada, todo esto se te hará muy familiar. Quizá aparte de tener acceso a un editor gráfico. De todas maneras, encontraremos menos similitudes a medida que avancemos.

GitHub Actions, como el nombre lo sugiere, es una serie de actions que son ejecuciones de comandos individuales, lo cual es bastante inusual. Si le prestas atención al archivo de flujo de trabajo, habrás notado que la definición de las acciones tiene un parámetro uses. Si usas una acción npm podrías crear una solo tarea NPM como npm install y luego otra acción para hacer la prueba npm test. Esto es inusual, ya que algunas tareas lógicas como "instalar dependencias" podrían requerir más de un comando y usualmente están agrupadas en "Etapas" en otras soluciones de integración continua.

Al usar el editor gráfico y agregas una nueva acción, lo primero que se te muestra es una lista de acciones disponibles. Luego aparece un formulario simple en el cual solo debes ingresar texto en los campos label, args y run.

El campo label, como podrías inferir, es solo un nombre amigable para lo que hace tu acción, como por ejemplo "Testing". La acción luego realizas un ‘runs args’  en la terminal considerando que runs no está siendo sobreescrito. Esto significa que para ejecutar npm install en una acción que use npm, tendrías que dejar el campo runs con el texto por defecto (vacío) y en el campo args escribir install

A este momento me provoca un poco de decepción, porque al parecer GitHub quiere restringir la funcionalidad de esta característica a solo las cosas que la plataforma determine. Npm está disponible por el momento, pero si usas pip para tu proyecto en Python entonces tendrás que implementar una acción propia o buscar una alternativa de código abierto. Ya es posible crear tus propias acciones personalizadas, pero dado que aún está en su versión beta es poco probable que encuentres gran variedad. Mirando el lado positivo, si tenían las dos cosas que necesitaba, NMP y Heroku.

El Proyecto

La idea del proyecto es bastante simple: Quería construir una aplicación en Vue(ya que es lo que estoy aprendiendo actualmente) y tener un despliegue automático a un servicio de alojamiento.

Después quería crearlo de manera que el contenido del sitio web refleje un archivo json con una serie de nombres de usuario de GitHub. De esta manera cualquier podría crear un PR con su nombre de usuario de GitHub y yo podría darle clic a un botón y tener todo desplegado mágicamente.

Omitiré todo el contenido en Vue.js e iré directamente a los Actions. Luego de construir esta simple aplicación, sólo tenía que hacer las siguientes acciones:

1. Instalar las dependencias
2. Ejecutar los linters (muy importante para prevenir cualquier mala estructura en el archivo json)
3. Construir el código listo para ir a producción
4. Desplegar en algún sitio web. (Decidí usar Heroku ya que parece ser el menos complicado en términos de servidores y que hay acciones disponible para esta plataforma).

Con los 3 primeros pasos tuve la experiencia más intuitiva automatizando cualquier cosa. Me recordó mucho a la plataforma IFTT. Solo tienes que darle clic a la acción NPM y luego escoger que quieres que NPM haga. Sé que mencioné que me sentí un poco restringido al solo tener una par de acciones, pero la realidad es que en ningún momento tuve que preocuparme sobre la distribución de Linux que estaba usando, si NPM estaba empaquetado con la instalación Node.js, y lo más importante cero preocupación si es que la sintaxis HCL estaba correcta. Un par de clic en la interfaz gráfica y listo. El proceso completo tomó 4 acciones y menos de 5 minutos.

Luego pasé a la fase de despliegue. Sabía que esta iba a ser un poco más complicada, porque a pesar de saber cómo funciona Heroku, nunca antes lo había utilizado. Sin embargo, en el repositorio actions/heroku  encontré instrucciones claras que me ayudaron a hacer exactamente lo que quería hacer. Al final, fue un tema de más clics y listo.

Secretos

Creo que esté el momento perfecto para hablar sobre mi funcionalidad favorita de GitHub Actions, los secretos. Como podrás suponer, Heroku requiere una API Key para poder permitirle a alguien desplegar la aplicación. De lo contrario, cualquiera leyendo este artículo podría reemplazar mi aplicación con lo que le plazca. Usualmente, esto es algo molesto al encargarse de un proyecto de código abierto, ya que no puedes almacenarlo dentro del mismo repositorio. AWS tiene incluso un servicio dedicado a esta clase de problema. A pesar de ellos, GitHub ha implementado una elegante solución a este problema.

Los secretos son valores que puedes almacenar al mismo nivel del repositorio y que será automáticamente encriptados y luego enviados como variables de entorno a las acciones que definas que tengan acceso a estos valores.

Si le has pegado una mirada al repositorio de la acción de Heroku, te habrás dado cuenta de que HEROKU_API_KEY está listado como un secreto requerido. El proceso para hacer esto en el editor es tan simple como darle clic a *new secret*, y luego darle un nombre y valor. A partir de ellos, puedes marcar el checkbox para cualquier acción que quieras que tenga acceso a esta información.

Ya que estos secretos se convierten en variable de entorno, no te quedas limitado a las acciones. Por ejemplo, tu framework de pruebas podría recibir las credenciales para un base de datos ya existente para guardar los resultados de tus pruebas, entonces podrías enviar estos secretos mediante una acción npm test.

Env

Env es otra opción dentro del editor gráfico que básicamente hace lo mismo que Secrets, pero omite todos los malabares de encriptar tu información. No es un gran problema, ya que la información no sensible podría ser almacenada en un archivo .env dentro del mismo repositorio.

Mis reflexiones sobre GitHub Actions

GitHub Actions no está haciendo nada novedoso. Hay docenas si no cientos de soluciones disponibles ya sea comerciales o gratuitas que hacen lo mismo que hace Actions. Incluso GitHub tiene toda una categoría de marketplace para la automatización de tareas para tu repositorio.

Sin embargo, personalmente nunca he tenido tan buena experiencia de usuarios configurando una canalización de CI/CD. GitHub actions no está reinventando la rueda, solo la está haciendo más económica.

Como desarrolladores, siempre tenemos que encontrar el balance entre simplicidad de uso y cuántas funcionalidades queremos agregarle a algo. El eternos dilema entre usar la terminal de Git o su interfaz gráfica. Por otra parte, GitHub está súper consciente de lo que el mercado tiene disponible y que ellos no están tratando de ser competidores de los grandes. No, no te vas a deshacer de Jenkins, Circle o cualquier otra solución que tu organización esté ya usando. Pero si tienes un pequeño proyecto propio, definitivamente vale la pena darle una chance con GitHub Actions.

Contribuye

Todo el código para éste artículo es abierto y disponible en https://github.com/pedsm/tryGithubActions. Si deseas registrar algún issue y agregar tu usuario de GitHub al proyecto, siéntete libre de crear un PR.

Traducido del artículo de Pedro Mendonça - A first look at GitHub Actions with Heroku de Pedro Mendonça