Cet algorithme intelligent peut accélérer vos programmes et inspirer votre travail avec les tableaux.
Effectuer des opérations sur des séquences de nombres et de caractères est un aspect crucial de la programmation. L’algorithme de fenêtre glissante est l’un des algorithmes standards pour ce faire.
C’est une solution élégante et polyvalente qui a trouvé sa place dans plusieurs domaines. De la manipulation de chaînes aux traversées de tableaux et à l’optimisation des performances, cet algorithme peut jouer un rôle.
Alors, comment fonctionne l’algorithme de fenêtre glissante et comment pouvez-vous l’implémenter dans Go ?
Comprendre l'algorithme de la fenêtre coulissante
Il y a de nombreux algorithmes de pointe qu'il est utile de connaître en tant que programmeur, et la fenêtre coulissante en fait partie. Cet algorithme s'articule autour d'un concept simple consistant à maintenir une fenêtre dynamique sur une séquence de données, pour traiter et analyser efficacement des sous-ensembles de ces données.
Vous pouvez appliquer l'algorithme lors de la résolution de problèmes informatiques impliquant des tableaux, des chaînes ou des séquences de données.
L'idée principale de l'algorithme de fenêtre glissante est de définir une fenêtre de taille fixe ou variable et de la déplacer dans les données d'entrée. Cela vous permet d'explorer différents sous-ensembles de l'entrée sans calculs redondants susceptibles de nuire aux performances.
Voici une représentation visuelle de son fonctionnement :
Les limites de la fenêtre peuvent s’ajuster en fonction des exigences spécifiques du problème.
Implémentation de l'algorithme de fenêtre coulissante dans Go
Vous pouvez utiliser un problème de codage populaire pour apprendre comment fonctionne l'algorithme de fenêtre glissante: trouver la plus grande somme d'un sous-tableau avec une longueur donnée.
Le but de cet exemple de problème est de trouver le sous-tableau de taille k dont les éléments totalisent la plus grande valeur. La fonction solution prend deux paramètres: le tableau d'entrée et un entier positif représentant k.
Laissez le tableau d'échantillons être chiffres, comme le montre le code ci-dessous :
nums := []int{1, 5, 4, 8, 7, 1, 9}
Et laissez la longueur du sous-tableau être k, avec une valeur de 3 :
k := 3
Vous pouvez ensuite déclarer une fonction pour trouver la somme maximale des sous-tableaux de longueur k :
funcmaximumSubarraySum(nums []int, k int)int {
// body
}
Vous pensez peut-être que la fenêtre doit être un tableau qui stocke des copies des éléments cibles. Bien que ce soit une option, elle fonctionne mal.
Au lieu de cela, il vous suffit de définir les limites de la fenêtre pour en garder une trace. Par exemple, dans ce cas, la première fenêtre aura un indice de départ de 0 et un indice de fin de k-1. En faisant glisser la fenêtre, vous mettrez à jour ces limites.
La première étape pour résoudre ce problème consiste à obtenir la somme du premier sous-tableau de taille k. Ajoutez le code suivant à votre fonction :
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
Le code ci-dessus déclare les variables nécessaires à l'algorithme et trouve la somme de la première fenêtre du tableau. Il initialise ensuite Sommemax avec la somme de la première fenêtre.
La prochaine étape consiste à faites glisser la fenêtre en parcourant le chiffres tableau à partir de l'index k jusqu'à la fin. À chaque étape du coulissement de la fenêtre :
- Mise à jour somme de fenêtre en ajoutant l'élément actuel et en soustrayant l'élément à fenêtreDébut.
- Mise à jour Sommemax si la nouvelle valeur de somme de fenêtre est plus grand que lui.
Le code suivant implémente la fenêtre glissante. Ajoutez-le au maximumSubarraySum fonction.
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
Une fois la boucle terminée, vous aurez la plus grande somme en Sommemax, que vous pouvez renvoyer comme résultat de la fonction :
return maxSum
Votre fonction complète devrait ressembler à ceci :
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
}
Vous pouvez définir une fonction principale pour tester l'algorithme, en utilisant les valeurs de chiffres et k d'avant :
funcmain() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
Le résultat dans ce cas sera 19, qui est la somme du sous-tableau [4, 8, 7], qui est le plus grand.
Vous pouvez désormais appliquer la même technique à des problèmes similaires, même dans d'autres langages, comme la gestion d'éléments répétés dans une fenêtre à l'aide d'un Carte de hachage Java, Par exemple.
Des algorithmes optimaux aboutissent à des applications efficaces
Cet algorithme témoigne de la puissance des solutions efficaces en matière de résolution de problèmes. La fenêtre coulissante maximise les performances et élimine les calculs inutiles.
Une solide compréhension de l'algorithme de fenêtre glissante et de sa mise en œuvre dans Go vous permet d'aborder des scénarios du monde réel lors de la création d'applications.
