En guide til algoritmen for glidende vinduer og hvordan den implementeres i Go

Udførelse af operationer på sekvenser af tal og tegn er et afgørende aspekt af programmering. Sliding window-algoritmen er en af ​​standardalgoritmerne til at gøre det.

Det er en elegant og alsidig løsning, der har fundet vej til flere domæner. Fra strengmanipulation til array-gennemløb og ydeevneoptimering kan denne algoritme spille en rolle.

Så hvordan fungerer glidevinduealgoritmen, og hvordan kan du implementere den i Go?

Forstå algoritmen for glidende vinduer

Der er mange topalgoritmer som er nyttige at kende som programmør, og det glidende vindue er en af ​​dem. Denne algoritme kredser om et simpelt koncept med at opretholde et dynamisk vindue over en sekvens af data, for effektivt at behandle og analysere delmængder af disse data.

Du kan anvende algoritmen, når du løser beregningsproblemer, der involverer arrays, strenge eller sekvenser af data.

Kerneideen bag glidende vinduesalgoritmen er at definere et vindue med en fast eller variabel størrelse og flytte det gennem inputdataene. Dette lader dig udforske forskellige undersæt af inputtet uden overflødige beregninger, der kan hindre ydeevnen.

Her er en visuel fremstilling af, hvordan det fungerer:

Vinduets grænser kan justeres i henhold til det specifikke problems krav.

Implementering af Sliding Window Algorithm in Go

Du kan bruge et populært kodningsproblem til at lære, hvordan algoritmen for glidende vinduer fungerer: at finde den største sum af et underarray med en given længde.

Formålet med denne prøveopgave er at finde underarrayet af størrelse k hvis elementer summer til den største værdi. Løsningsfunktionen tager to parametre ind: input-arrayet og et positivt heltal, der repræsenterer k.

Lad sample-arrayet være nums, som koden nedenfor viser:

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

Og lad underarrayets længde være k, med en værdi på 3:

k := 3

Du kan derefter erklære en funktion til at finde den maksimale sum af underarrays med længden k:

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

Du tænker måske, at vinduet skal være et array, der gemmer kopier af målelementerne. Selvom det er en mulighed, fungerer den dårligt.

I stedet skal du blot definere vinduets grænser for at holde styr på det. For eksempel vil det første vindue i dette tilfælde have et startindeks på 0 og et slutindeks på k-1. I færd med at skubbe vinduet, opdaterer du disse grænser.

Det første skridt til at løse dette problem er at få summen af ​​det første underarray af størrelse k. Tilføj følgende kode til din funktion:

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

Ovenstående kode erklærer de nødvendige variabler for algoritmen og finder summen af ​​det første vindue i arrayet. Den initialiseres derefter maxSum med summen af ​​det første vindue.

Næste skridt er at skub vinduet ved at gentage nums array fra indeks k til slutningen. I hvert trin af at skyde vinduet:

1. Opdatering vindueSum ved at tilføje det aktuelle element og trække elementet fra kl vindue Start.
2. Opdatering maxSum hvis den nye værdi af vindueSum er større end det.

Følgende kode implementerer det glidende vindue. Tilføj det til maksimumSubarraySum fungere.

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

Når løkken er færdig, har du den største sum ind maxSum, som du kan returnere som resultatet af funktionen:

return maxSum

Din komplette funktion skulle se sådan ud:

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
}

Du kan definere en hovedfunktion til at teste algoritmen ved at bruge værdierne af nums og k fra tidligere:

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

Udgangen vil i dette tilfælde være 19, som er summen af ​​sub-arrayet [4, 8, 7], som er den største.

Du kan nu anvende den samme teknik på lignende problemer, selv på andre sprog, som at håndtere gentagne elementer i et vindue ved hjælp af en Java hash kort, for eksempel.

Optimale algoritmer resulterer i effektive applikationer

Denne algoritme står som et vidnesbyrd om kraften i effektive løsninger, når det kommer til problemløsning. Det glidende vindue maksimerer ydeevnen og eliminerer unødvendige beregninger.

En solid forståelse af algoritmen for glidende vinduer og dens implementering i Go ruster dig til at tackle virkelige scenarier, når du bygger applikationer.