Técnicas para Algoritmos: Sliding Windows #1

Estos ejercicios que presentaremos a continuación se fundamentan en la estrategia Slinding Windows. Aplicar esta técnica a problemas donde sea necesario recorrer una lista de elementos en donde tengas que buscar o calcular algo a partir de sub arreglos con elementos consecutivos de un tamaño k elementos.

Escenario de pruebas:

Dado un arreglo, encuentra el promedio de todos los sub arreglos de tamaño k.

Input: arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];  k= 5

Output: [ 2.2, 2.8, 2.4, 3.6, 2.8]

Este problema puede tener varias soluciones posibles que pueden ser válidas,  en esta introducción tomaremos dos soluciones posibles. La primera solución no sigue ninguna estrategia en particular que le llamaremos fuerza bruta (FB) y la segunda solución si sigue una estrategia en este caso Sliding Windows (SW). Con estas dos estrategias vamos a resaltar la importancia de tener un plan a seguir bien pensado para resolver este tipo de problemas. 

Problema (fácil):

Promedio de sub arreglos de tamaño k.

Estrategia de Fuerza Bruta:

La primera idea que se nos puede ocurrir para resolver este problema es usar ciclos anidados. El primer ciclo recorre los elementos del arreglo desde el índice 0 hasta  (tamaño del arreglo - k + 1). El ciclo anidado  recorre k elementos, haciendo las operaciones correspondientes para obtener el promedio.

Esta estrategia nos arroja que para un n = 9  tendremos 25 operaciones,  para el escenario de pruebas anterior, claramente la O(n*m) es la big Oh que representa esta solución donde m representa el tamaño del arreglo -k y  m el tamaño del sub arreglo k. En definitiva se puede decir que es un O(n²) algo que no resulta ser una solución muy eficiente.

Estrategia de Slinding Window:

En la siguiente solución implementamos la estrategia de sliding windows, esta estrategia busca eliminar el ciclo anidado  de la solución presentada por fuerza bruta. La idea principal se basa en ir sacando el último elemento de la ventana  y agregando el siguiente, solo hay que tener en consideración los índices de los elementos a sacar cuando el arreglo ha recorrido el tamaño de k en adelante.

El centro de la estrategia esta en esta parte del código, en donde se realiza la salida del primer elemento de la ventana desde que i alcanza valores igual o superiores a k:

En la solución usando la estrategia de sliding windows podemos notar que las operaciones se reducen a 5, siendo mucho menos operaciones que las necesarias para la estrategia de Fuerza Bruta. Los dos algoritmos llegan al mismo resultado pero su eficiencia es muy distinta. La big Oh de este algoritmo con la estrategia de Sliding Windows es O(n).

Debugger con el escenario de prueba:

En esta parte del proyecto es bueno aprender a usar las herramientas de debugger para VSCode así pueden ver paso a paso como trabajan estos dos algoritmos. Más info.

Código en Github, podrás encontrar otros algoritmos y sus soluciones. Si te sirve de ayuda deja una estrella para el repositorio.