Vodnik po algortihmu drsnega okna in kako ga implementirati v Go

Izvajanje operacij nad zaporedji številk in znakov je ključni vidik programiranja. Algoritem drsnega okna je eden od standardnih algoritmov za to.

To je elegantna in vsestranska rešitev, ki je našla svojo pot na več področjih. Ta algoritem ima lahko vlogo od manipulacije z nizi do prečkanja matrike in optimizacije delovanja.

Torej, kako deluje algoritem drsnega okna in kako ga lahko implementirate v Go?

Razumevanje algoritma drsnega okna

obstajajo veliko vrhunskih algoritmov ki jih je koristno poznati kot programer, in drsno okno je eno izmed njih. Ta algoritem se vrti okoli preprostega koncepta vzdrževanja dinamičnega okna v zaporedju podatkov za učinkovito obdelavo in analizo podnaborov teh podatkov.

Algoritem lahko uporabite pri reševanju računskih problemov, ki vključujejo polja, nize ali zaporedja podatkov.

Osnovna ideja za algoritmom drsnega okna je definirati okno fiksne ali spremenljive velikosti in ga premikati skozi vhodne podatke. To vam omogoča raziskovanje različnih podnaborov vnosa brez odvečnih izračunov, ki lahko ovirajo delovanje.

Tukaj je vizualna predstavitev, kako deluje:

Meje okna se lahko prilagodijo glede na zahteve določene težave.

Implementacija algoritma drsnega okna v Go

Uporabite lahko priljubljen problem kodiranja, da se naučite, kako deluje algoritem drsnega okna: iskanje največje vsote podniza z dano dolžino.

Cilj tega vzorčnega problema je najti podniz velikosti k katerih elementi seštevajo največjo vrednost. Funkcija rešitve sprejme dva parametra: vhodno polje in pozitivno celo število, ki predstavlja k.

Naj bo vzorčna matrika številke, kot prikazuje spodnja koda:

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

In naj bo dolžina podniza k, z vrednostjo 3:

k := 3

Nato lahko deklarirate funkcijo za iskanje največje vsote podnizov z dolžino k:

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

Morda mislite, da mora biti okno polje, ki hrani kopije ciljnih elementov. Čeprav je to možnost, deluje slabo.

Namesto tega morate samo določiti meje okna, da mu sledite. Na primer, v tem primeru bo prvo okno imelo začetni indeks 0 in končni indeks k-1. Med pomikanjem okna boste posodobili te meje.

Prvi korak za rešitev te težave je pridobitev vsote prve podmatrike velikosti k. Svoji funkciji dodajte naslednjo kodo:

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

Zgornja koda deklarira potrebne spremenljivke za algoritem in najde vsoto prvega okna v matriki. Nato se inicializira maxSum z vsoto prvega okna.

Naslednji korak je potisnite okno s ponavljanjem skozi številke niz iz indeksa k do konca. V vsakem koraku drsenja okna:

1. Nadgradnja windowSum z dodajanjem trenutnega elementa in odštevanjem elementa pri windowStart.
2. Nadgradnja maxSum če je nova vrednost windowSum je večji od njega.

Naslednja koda implementira drsno okno. Dodajte ga v največjaSubarraySum funkcijo.

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

Ko se zanka zaključi, boste imeli največjo vsoto maxSum, ki ga lahko vrnete kot rezultat funkcije:

return maxSum

Vaša celotna funkcija bi morala izgledati takole:

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
}

Definirate lahko glavno funkcijo za testiranje algoritma z uporabo vrednosti številke in k od prej:

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

Izhod v tem primeru bo 19, ki je vsota podniza [4, 8, 7], ki je največji.

Zdaj lahko uporabite isto tehniko za podobne težave, tudi v drugih jezikih, kot je obravnava ponavljajočih se elementov znotraj okna z Java hash zemljevid, na primer.

Rezultat optimalnih algoritmov so učinkovite aplikacije

Ta algoritem je dokaz moči učinkovitih rešitev, ko gre za reševanje problemov. Drsno okno poveča zmogljivost in odpravi nepotrebne izračune.

Dobro razumevanje algoritma drsnega okna in njegove implementacije v Go vas opremi za reševanje scenarijev iz resničnega sveta pri gradnji aplikacij.