Vodič za algortihm kliznog prozora i kako ga implementirati u Go

Izvođenje operacija nad nizovima brojeva i znakova ključni je aspekt programiranja. Algoritam kliznog prozora jedan je od standardnih algoritama za to.

To je elegantno i svestrano rješenje koje je pronašlo svoj put u više domena. Ovaj algoritam može odigrati važnu ulogu, od manipulacije nizovima do obilaženja polja i optimizacije performansi.

Dakle, kako funkcionira algoritam kliznog prozora i kako ga možete implementirati u Go?

Razumijevanje algoritma kliznog prozora

Tamo su mnogo vrhunskih algoritama koje je korisno znati kao programer, a klizni prozor je jedan od njih. Ovaj se algoritam vrti oko jednostavnog koncepta održavanja dinamičkog prozora nad nizom podataka, kako bi se učinkovito obradili i analizirali podskupovi tih podataka.

Algoritam možete primijeniti pri rješavanju računalnih problema koji uključuju nizove, nizove ili nizove podataka.

Temeljna ideja iza algoritma kliznog prozora je definiranje prozora fiksne ili varijabilne veličine i njegovo pomicanje kroz ulazne podatke. To vam omogućuje istraživanje različitih podskupova ulaza bez suvišnih izračuna koji mogu ometati izvedbu.

Evo vizualnog prikaza kako funkcionira:

Granice prozora mogu se prilagoditi prema zahtjevima specifičnog problema.

Implementacija algoritma kliznog prozora u Go

Možete upotrijebiti popularan problem kodiranja da naučite kako funkcionira algoritam kliznog prozora: pronalaženje najvećeg zbroja podniza zadane duljine.

Cilj ovog oglednog problema je pronaći podniz veličine k čiji elementi zbrajaju najveću vrijednost. Funkcija rješenja uzima dva parametra: ulazni niz i pozitivni cijeli broj koji predstavlja k.

Neka uzorak niza bude brojevi, kao što pokazuje kod u nastavku:

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

I neka duljina podniza bude k, s vrijednošću 3:

k := 3

Zatim možete deklarirati funkciju za pronalaženje maksimalnog zbroja podnizova duljine k:

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

Možda mislite da prozor mora biti niz koji pohranjuje kopije ciljnih elemenata. Iako je to opcija, ima lošu izvedbu.

Umjesto toga, trebate samo definirati granice prozora da biste ga pratili. Na primjer, u ovom slučaju, prvi prozor će imati početni indeks od 0 i krajnji indeks od k-1. U procesu pomicanja prozora, ažurirat ćete ove granice.

Prvi korak za rješavanje ovog problema je dobivanje zbroja prvog podniza veličine k. Dodajte sljedeći kod svojoj funkciji:

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

Gornji kod deklarira potrebne varijable za algoritam i pronalazi zbroj prvog prozora u nizu. Zatim se inicijalizira maxSum sa zbrojem prvog prozora.

Sljedeći korak je da pomaknite prozor ponavljanjem kroz brojevi niz iz indeksa k do kraja. U svakom koraku pomicanja prozora:

1. Ažuriraj prozorSum dodavanjem trenutnog elementa i oduzimanjem elementa at windowStart.
2. Ažuriraj maxSum ako nova vrijednost od prozorSum je veći od njega.

Sljedeći kod implementira klizni prozor. Dodajte ga u maksimalni zbroj podniza funkcija.

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

Kada se petlja završi, imat ćete najveći iznos maxSum, koji možete vratiti kao rezultat funkcije:

return maxSum

Vaša kompletna funkcija trebala bi izgledati ovako:

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
}

Možete definirati glavnu funkciju za testiranje algoritma, koristeći vrijednosti brojevi i k od ranije:

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

Izlaz će u ovom slučaju biti 19, što je zbroj podniza [4, 8, 7], koji je najveći.

Sada možete primijeniti istu tehniku ​​na slične probleme, čak i na drugim jezicima, poput rukovanja ponovljenim elementima unutar prozora pomoću Java hash karta, na primjer.

Optimalni algoritmi rezultiraju učinkovitim aplikacijama

Ovaj algoritam predstavlja dokaz snage učinkovitih rješenja kada je u pitanju rješavanje problema. Klizni prozor maksimizira performanse i eliminira nepotrebna izračunavanja.

Dobro razumijevanje algoritma kliznog prozora i njegove implementacije u Go osposobljava vas da se uhvatite u koštac sa scenarijima iz stvarnog svijeta pri izradi aplikacija.