Este algoritmo inteligente puede acelerar sus programas e inspirar su trabajo con matrices.
Realizar operaciones en secuencias de números y caracteres es un aspecto crucial de la programación. El algoritmo de ventana deslizante es uno de los algoritmos estándar para hacerlo.
Es una solución elegante y versátil que se ha abierto camino en múltiples dominios. Desde la manipulación de cadenas hasta el recorrido de matrices y la optimización del rendimiento, este algoritmo puede desempeñar un papel importante.
Entonces, ¿cómo funciona el algoritmo de ventana deslizante y cómo se puede implementar en Go?
Comprender el algoritmo de ventana deslizante
Hay muchos algoritmos superiores que es útil conocer como programador, y la ventana deslizante es una de ellas. Este algoritmo gira en torno a un concepto simple de mantener una ventana dinámica sobre una secuencia de datos, para procesar y analizar de manera eficiente subconjuntos de esos datos.
Puede aplicar el algoritmo al resolver problemas computacionales que involucran matrices, cadenas o secuencias de datos.
La idea central detrás del algoritmo de ventana deslizante es definir una ventana de tamaño fijo o variable y moverla a través de los datos de entrada. Esto le permite explorar diferentes subconjuntos de la entrada sin cálculos redundantes que puedan obstaculizar el rendimiento.
Aquí hay una representación visual de cómo funciona:
Los límites de la ventana pueden ajustarse según los requisitos del problema específico.
Implementación del algoritmo de ventana deslizante en Go
Puede utilizar un problema de codificación popular para aprender cómo funciona el algoritmo de ventana deslizante: encontrar la suma más grande de una submatriz con una longitud determinada.
El objetivo de este problema de muestra es encontrar el subconjunto de tamaño k cuyos elementos suman el mayor valor. La función de solución toma dos parámetros: la matriz de entrada y un número entero positivo que representa k.
Sea la matriz de muestra números, como muestra el siguiente código:
nums := []int{1, 5, 4, 8, 7, 1, 9}
Y sea la longitud del subconjunto k, con un valor de 3:
k := 3
Luego puede declarar una función para encontrar la suma máxima de subarreglos con longitud k:
funcmaximumSubarraySum(nums []int, k int)int {
// body
}
Quizás esté pensando que la ventana tiene que ser una matriz que almacene copias de los elementos de destino. Si bien es una opción, su rendimiento es deficiente.
En su lugar, sólo necesita definir los límites de la ventana para realizar un seguimiento. Por ejemplo, en este caso, la primera ventana tendrá un índice inicial de 0 y un índice final de k-1. En el proceso de deslizar la ventana, actualizará estos límites.
El primer paso para resolver este problema es obtener la suma del primer subconjunto de tamaño k. Agregue el siguiente código a su función:
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
El código anterior declara las variables necesarias para el algoritmo y encuentra la suma de la primera ventana de la matriz. Luego se inicializa sumamax con la suma de la primera ventana.
El siguiente paso es desliza la ventana iterando a través del números matriz del índice k hasta el final. En cada paso de deslizar la ventana:
- Actualizar ventanaSuma sumando el elemento actual y restando el elemento en ventanaInicio.
- Actualizar sumamax si el nuevo valor de ventanaSuma es mayor que él.
El siguiente código implementa la ventana deslizante. Agréguelo al sumasubarray máxima función.
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
Cuando se complete el ciclo, tendrás la suma más grande en sumamax, que puedes devolver como resultado de la función:
return maxSum
Su función completa debería verse así:
funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for i := 0; i < k; i++ {
windowSum += nums[i]
}maxSum = windowSum
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]if windowSum > maxSum {
maxSum = windowSum
}// slide window forward
windowStart++
}
return maxSum
}
Puede definir una función principal para probar el algoritmo, utilizando los valores de números y k de antes:
funcmain() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
La salida en este caso será 19, que es la suma del subconjunto [4, 8, 7], que es el más grande.
Ahora puedes aplicar la misma técnica a problemas similares, incluso en otros lenguajes, como manejar elementos repetidos dentro de una ventana usando un mapa hash de Java, Por ejemplo.
Los algoritmos óptimos dan como resultado aplicaciones eficientes
Este algoritmo es un testimonio del poder de las soluciones eficientes cuando se trata de resolución de problemas. La ventana deslizante maximiza el rendimiento y elimina cálculos innecesarios.
Una comprensión sólida del algoritmo de ventana deslizante y su implementación en Go lo capacita para abordar escenarios del mundo real al crear aplicaciones.
