Un ghid pentru algoritmul ferestrei glisante și cum să-l implementați în Go

Efectuarea de operații pe secvențe de numere și caractere este un aspect crucial al programării. Algoritmul ferestrei glisante este unul dintre algoritmii standard pentru a face acest lucru.

Este o soluție elegantă și versatilă care și-a găsit drumul în mai multe domenii. De la manipularea șirurilor până la traversări ale matricelor și optimizarea performanței, acest algoritm poate juca un rol.

Deci, cum funcționează algoritmul ferestrei glisante și cum îl puteți implementa în Go?

Înțelegerea algoritmului ferestrei glisante

Sunt mulți algoritmi de top care sunt utile de știut ca programator, iar fereastra glisantă este una dintre ele. Acest algoritm se învârte în jurul unui concept simplu de menținere a unei ferestre dinamice peste o secvență de date, pentru a procesa și analiza eficient subseturi de date respective.

Puteți aplica algoritmul atunci când rezolvați probleme de calcul care implică matrice, șiruri sau secvențe de date.

Ideea de bază din spatele algoritmului ferestrei glisante este de a defini o fereastră de dimensiune fixă ​​sau variabilă și de a o muta prin datele de intrare. Acest lucru vă permite să explorați diferite subseturi de intrare fără calcule redundante care pot împiedica performanța.

Iată o reprezentare vizuală a modului în care funcționează:

Limitele ferestrei se pot ajusta în funcție de cerințele problemei specifice.

Implementarea algoritmului ferestrei glisante în Go

Puteți folosi o problemă populară de codare pentru a afla cum funcționează algoritmul ferestrei glisante: găsirea celei mai mari sume a unei sub-matrice cu o lungime dată.

Scopul acestei probleme eșantion este de a găsi sub-matrice de dimensiune k ale căror elemente se însumează la cea mai mare valoare. Funcția de soluție preia doi parametri: matricea de intrare și un număr întreg pozitiv reprezentând k.

Fie matricea de mostre nums, după cum arată codul de mai jos:

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

Și să fie lungimea sub-matrice k, cu valoarea 3:

k := 3

Apoi puteți declara o funcție pentru a găsi suma maximă de sub-matrice cu lungimea k:

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

S-ar putea să vă gândiți că fereastra trebuie să fie o matrice care stochează copii ale elementelor țintă. Deși aceasta este o opțiune, funcționează slab.

În schimb, trebuie doar să definiți limitele ferestrei pentru a-i urmări. De exemplu, în acest caz, prima fereastră va avea un index de pornire de 0 și un indice final al k-1. În procesul de glisare a ferestrei, veți actualiza aceste limite.

Primul pas pentru a rezolva această problemă este de a obține suma primei sub-matrice de dimensiunea k. Adăugați următorul cod la funcția dvs.:

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

Codul de mai sus declară variabilele necesare pentru algoritm și găsește suma primei ferestre din matrice. Apoi se inițializează maxSum cu suma primei ferestre.

Următorul pas este să glisează fereastra prin iterarea prin nums matrice din index k până la capăt. La fiecare pas al glisării ferestrei:

1. Actualizați windowSum prin adăugarea elementului curent și scăderea elementului la windowStart.
2. Actualizați maxSum dacă noua valoare a windowSum este mai mare decât el.

Următorul cod implementează fereastra glisantă. Adăugați-l la maximumSubarraySum funcţie.

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

Când bucla se termină, veți avea cea mai mare sumă maxSum, pe care îl puteți returna ca rezultat al funcției:

return maxSum

Funcția dvs. completă ar trebui să arate astfel:

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
}

Puteți defini o funcție principală pentru a testa algoritmul, folosind valorile lui nums și k de mai devreme:

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

Ieșirea în acest caz va fi 19, care este suma sub-matricei [4, 8, 7], care este cea mai mare.

Acum puteți aplica aceeași tehnică la probleme similare, chiar și în alte limbi, cum ar fi manipularea elementelor repetate într-o fereastră folosind o Harta hash Java, de exemplu.

Algoritmii optimi au ca rezultat aplicații eficiente

Acest algoritm este o dovadă a puterii soluțiilor eficiente atunci când vine vorba de rezolvarea problemelor. Fereastra glisantă maximizează performanța și elimină calculele inutile.

O înțelegere solidă a algoritmului ferestrei glisante și implementarea acestuia în Go vă echipează să abordați scenarii din lumea reală atunci când construiți aplicații.