En veiledning til algoritmen for skyvevinduer og hvordan du implementerer den i farten

Å utføre operasjoner på sekvenser av tall og tegn er et avgjørende aspekt ved programmering. Skyvevindusalgoritmen er en av standardalgoritmene for å gjøre det.

Det er en elegant og allsidig løsning som har funnet veien til flere domener. Fra strengmanipulering til array-gjennomganger og ytelsesoptimalisering, kan denne algoritmen spille en rolle.

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

Forstå algoritmen for skyvevinduer

Det er mange toppalgoritmer som er nyttige å kjenne til som programmerer, og skyvevinduet er en av dem. Denne algoritmen dreier seg om et enkelt konsept for å opprettholde et dynamisk vindu over en sekvens av data, for å effektivt behandle og analysere delsett av disse dataene.

Du kan bruke algoritmen når du løser beregningsproblemer som involverer matriser, strenger eller sekvenser av data.

Kjerneideen bak skyvevindusalgoritmen er å definere et vindu med fast eller variabel størrelse og flytte det gjennom inndataene. Dette lar deg utforske ulike delsett av inngangen uten redundante beregninger som kan hindre ytelsen.

Her er en visuell representasjon av hvordan det fungerer:

Vinduets grenser kan justeres i henhold til det spesifikke problemets krav.

Implementering av skyvevindualgoritmen i farten

Du kan bruke et populært kodeproblem for å lære hvordan skyvevindusalgoritmen fungerer: finne den største summen av en undergruppe med en gitt lengde.

Målet med dette prøveproblemet er å finne undergruppen av størrelse k hvis elementer summerer til den største verdien. Løsningsfunksjonen tar inn to parametere: inngangsmatrisen og et positivt heltall som representerer k.

La prøvematrisen være nums, som koden nedenfor viser:

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

Og la sub-array-lengden være k, med en verdi på 3:

k := 3

Du kan deretter deklarere en funksjon for å finne den maksimale summen av undermatriser med lengde k:

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

Du tenker kanskje at vinduet må være en matrise som lagrer kopier av målelementene. Selv om det er et alternativ, fungerer det dårlig.

I stedet trenger du bare å definere grensene til vinduet for å holde styr på det. For eksempel, i dette tilfellet vil det første vinduet ha en startindeks på 0 og en sluttindeks på k-1. I prosessen med å skyve vinduet, vil du oppdatere disse grensene.

Det første trinnet for å løse dette problemet er å få summen av den første undergruppen med størrelse k. Legg til følgende kode til funksjonen din:

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

Koden ovenfor erklærer de nødvendige variablene for algoritmen og finner summen av det første vinduet i matrisen. Deretter initialiseres den maksSum med summen av det første vinduet.

Neste steg er å skyv vinduet ved å iterere gjennom nums array fra indeksen k til slutten. I hvert trinn av å skyve vinduet:

1. Oppdater vinduSum ved å legge til gjeldende element og trekke fra elementet ved vindu Start.
2. Oppdater maksSum hvis den nye verdien av vinduSum er større enn det.

Følgende kode implementerer skyvevinduet. Legg den til maksimumSubarraySum funksjon.

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

Når loopen er fullført, vil du ha den største summen inn maksSum, som du kan returnere som resultat av funksjonen:

return maxSum

Din komplette funksjon skal se slik ut:

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 hovedfunksjon for å teste algoritmen ved å bruke verdiene til nums og k fra tidligere:

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

Utgangen i dette tilfellet vil være 19, som er summen av sub-arrayen [4, 8, 7], som er den største.

Du kan nå bruke den samme teknikken på lignende problemer, selv på andre språk, som å håndtere gjentatte elementer i et vindu ved å bruke en Java hash kart, for eksempel.

Optimale algoritmer resulterer i effektive applikasjoner

Denne algoritmen står som et bevis på kraften til effektive løsninger når det kommer til problemløsning. Skyvevinduet maksimerer ytelsen og eliminerer unødvendige beregninger.

En solid forståelse av skyvevindusalgoritmen og dens implementering i Go utstyrer deg til å takle virkelige scenarier når du bygger applikasjoner.