Um guia para o algoritmo de janela deslizante e como implementá-lo em Go

A execução de operações em sequências de números e caracteres é um aspecto crucial da programação. O algoritmo de janela deslizante é um dos algoritmos padrão para fazer isso.

É uma solução elegante e versátil que chegou a vários domínios. Da manipulação de strings até travessias de array e otimização de desempenho, esse algoritmo pode desempenhar um papel.

Então, como funciona o algoritmo da janela deslizante e como você pode implementá-lo no Go?

Compreendendo o algoritmo da janela deslizante

Há muitos algoritmos principais que são úteis para um programador conhecer, e a janela deslizante é uma delas. Este algoritmo gira em torno de um conceito simples de manter uma janela dinâmica sobre uma sequência de dados, para processar e analisar eficientemente subconjuntos desses dados.

Você pode aplicar o algoritmo ao resolver problemas computacionais que envolvem matrizes, strings ou sequências de dados.

A ideia central por trás do algoritmo de janela deslizante é definir uma janela de tamanho fixo ou variável e movê-la através dos dados de entrada. Isso permite explorar diferentes subconjuntos da entrada sem cálculos redundantes que podem prejudicar o desempenho.

Aqui está uma representação visual de como funciona:

Os limites da janela podem ser ajustados de acordo com os requisitos específicos do problema.

Implementando o algoritmo de janela deslizante em Go

Você pode usar um problema de codificação popular para aprender como funciona o algoritmo de janela deslizante: encontrar a maior soma de uma submatriz com um determinado comprimento.

O objetivo deste problema de amostra é encontrar a submatriz de tamanho k cujos elementos somam o maior valor. A função de solução recebe dois parâmetros: a matriz de entrada e um número inteiro positivo representando k.

Deixe a matriz de amostra ser números, como mostra o código abaixo:

nums := []int{1, 5, 4, 8, 7, 1, 9}

E deixe o comprimento da submatriz ser k, com um valor de 3:

k := 3

Você pode então declarar uma função para encontrar a soma máxima de submatrizes com comprimento k:

funcmaximumSubarraySum(nums []int, k int)int {
// body
}

Você pode estar pensando que a janela deve ser um array que armazena cópias dos elementos de destino. Embora seja uma opção, seu desempenho é ruim.

Em vez disso, você só precisa definir os limites da janela para controlá-la. Por exemplo, neste caso, a primeira janela terá um índice inicial de 0 e um índice final de k-1. No processo de deslizar a janela, você atualizará esses limites.

O primeiro passo para resolver este problema é obter a soma da primeira submatriz de tamanho k. Adicione o seguinte código à sua função:

var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
}
maxSum = windowSum

O código acima declara as variáveis ​​necessárias para o algoritmo e encontra a soma da primeira janela do array. Em seguida, ele inicializa somamáx com a soma da primeira janela.

O próximo passo é deslize a janela iterando através do números matriz do índice k até o fim. Em cada etapa de deslizamento da janela:

1. Atualizar janelaSoma adicionando o elemento atual e subtraindo o elemento em janelaIniciar.
2. Atualizar somamáx se o novo valor de janelaSoma é maior que isso.

O código a seguir implementa a janela deslizante. Adicione-o ao máximoSubarraySoma função.

for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++
}

Quando o loop for concluído, você terá a maior soma somamáx, que você pode retornar como resultado da função:

return maxSum

Sua função completa deve ficar assim:

funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
 windowStart = 0
for 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
}

Você pode definir uma função principal para testar o algoritmo, usando os valores de números e k de antes:

funcmain() {
 nums := []int{1, 5, 4, 8, 7, 1, 9}
 k := 3
 fmt.Println(maximumSubarraySum(nums, k))
}

A saída neste caso será 19, que é a soma da submatriz [4, 8, 7], que é a maior.

Agora você pode aplicar a mesma técnica a problemas semelhantes, mesmo em outras linguagens, como lidar com elementos repetidos dentro de uma janela usando um Mapa de hash Java, por exemplo.

Algoritmos ideais resultam em aplicações eficientes

Este algoritmo é uma prova do poder de soluções eficientes quando se trata de resolução de problemas. A janela deslizante maximiza o desempenho e elimina cálculos desnecessários.

Uma sólida compreensão do algoritmo de janela deslizante e sua implementação em Go prepara você para enfrentar cenários do mundo real ao construir aplicativos.