Olá amigos, tudo bem com vocês?
Imagine que um belo dia você entra em sua livraria favorita e visualiza um conjunto de 6 livros dos quais você tem profundo interesse:
| Livro | Preço |
|---|---|
| Livro 1 | R$ 100,00 |
| Livro 2 | R$ 67,00 |
| Livro 3 | R$ 300,00 |
| Livro 4 | R$ 30,00 |
| Livro 5 | R$ 50,00 |
| Livro 6 | R$ 25,00 |
Você tem R$ 195,00 no bolso e gostaria de levar a maior quantidade de livros possível. Como você resolveria?
Estante de livros de diversas cores
A resposta mais plausível (comprar os Livros 2,4,5,6 cuja soma resulta em R$ 172,00 e guardar os R$ 23,00 restantes) não é tão complexa de calcular uma vez que temos um conjunto pequeno de apenas 6 livros.
Contudo para analisar um conjunto de 1 milhão de livros talvez você precise da ajuda de computador, que por sua vez vai necessitar da ajuda de algoritmo bem eficiente para realizar o trabalho.
Um desses algoritmos será o assunto do nosso artigo de hoje: Sliding Window (ou Janelas Deslizantes em português).
O Algoritmo
Para encontramos os livros que cabem do nosso orçamento, iremos comparar o preço de cada um dos livros, a partir do primeiro.
Quando o valor do orçamento for atingido, nós atualizaremos a lista de livros disponíveis e reiniciaremos a análise. Porém, nessa segunda etapa vamos iniciar a análise a partir do segundo livro da lista e o processo irá se repetir até o fim.
Veja abaixo a visualização gráfica do algoritmo sendo executado.
Inicio da execução
Na inicio de execução do algoritmo, a soma de preços está apenas como o primeiro livro: R$ 100,00 e não fizemos nenhuma aquisição de um novo livro.
Inicio de execução. O livro de R$ 100,00 já está na sacola. O objetivo agora é adquirir os outros.
Na segunda varredura do algoritmo, adicionamos o livro de R$ 67,00. Uma vez que a soma de R$ 167,00 está dentro de nosso orçamento.
Segunda varredura e podemos verificar que o livro de 67,00 pode ser adquirido, pois R$ 167,00 ainda está no orçamento.
Na terceira varredura ocorre nosso primeiro estouro de orçamento. O Livro de R$ 300,00 está acima do valor disponível. Portanto o algoritmo não adiciona este livro e continua a sua execução.
Primeiro estouro de orçamento. Adquirir o livro de R$ 300,00 está fora de questão.
Perceba que nas próximas tentativas, o único livro que ainda tem possibilidade de entrar em nossa sacola sem estourar o orçamento é o livro de R$ 25,00. Quando isso acontece é hora de refazermos a análise, porém agora iremos começar a partir do livro de 67,00.
Deslize da Janela
No início dessa fase, o orçamento atinge o seu limite na segunda varredura, pois R$ 67,00 + R$ 300,00 vai ultrapassar os R$ 195,00.
Primeiro estouro de orçamento da nova janela.
Apesar disso, obtemos sucesso em todas as outras tentativas de captura. E concluímos que esta é a melhor configuração de nossa sacola (livros de 67, 30, 50, 25 reais).
Configuração ideal, onde compramos uma boa quantidade de livros sem estourar o orçamento
Obs.: O algoritmo continuará executando, mas não irá encontrar outra configuração melhor.
Conclusão
Apesar de parecer simplório, este algoritmo possui diversas aplicações na Ciência da Computação.
Entre elas:
- Compressão de dados: Algoritmos de compressão de dados usam janelas deslizantes para encontrar padrões e repeti-los quando necessários.
- Processamento de imagens: Funções como detecção de objetos e segmentação de imagens podem ser executadas com o auxílio do algoritmo de janelas deslizantes.
- Processamento de sinais: Janelas deslizantes podem auxiliar na identificação de padrões, tendências e anomalias em processamentos de sinais.
- Protocolos de rede: Como já relatado no meu artigo de Back Pressure, Janelas deslizantes podem auxiliar a controlar o fluxo de dados em redes de baixa velocidade e evitar perdas de dados.
Conhecer esse algoritmo é bastante importante até mesmo para entender como outras técnicas são realizadas, com menos dificuldade de entendimento.
Nesta parte 1, utilizei uma janela deslizante de tamanho dinâmico. Na parte 2 irei abordar uma situação onde ela é fixa.
Espero que esse texto tenha sido útil para você e muito obrigado pela leitura.
Referências
https://www.geeksforgeeks.org/window-sliding-technique/
https://www.baeldung.com/cs/sliding-window-algorithm
Minha implementação de Sliding Window na Linguagem C#.Net https://github.com/cezarantoniodevsec/roadmap_dotnet/blob/main/roadmap_dotnet/roadmap_dotnet/DataStructures/SlidingWindow/SlidingWindow.cs
