En guide till algoritmen för skjutfönster och hur man implementerar det i Go

Att utföra operationer på sekvenser av siffror och tecken är en avgörande aspekt av programmering. Algoritmen för glidfönster är en av standardalgoritmerna för att göra det.

Det är en elegant och mångsidig lösning som har hittat sin väg till flera domäner. Från strängmanipulation till array-traversals och prestandaoptimering, denna algoritm kan spela en roll.

Så, hur fungerar den skjutbara fönsteralgoritmen, och hur kan du implementera den i Go?

Förstå algoritmen för skjutfönster

Det finns många toppalgoritmer som är användbara att känna till som programmerare, och det skjutbara fönstret är en av dem. Denna algoritm kretsar kring ett enkelt koncept att upprätthålla ett dynamiskt fönster över en sekvens av data, för att effektivt bearbeta och analysera delmängder av dessa data.

Du kan använda algoritmen när du löser beräkningsproblem som involverar matriser, strängar eller datasekvenser.

Kärnan bakom algoritmen för glidfönster är att definiera ett fönster med en fast eller variabel storlek och flytta det genom indata. Detta låter dig utforska olika delmängder av indata utan redundanta beräkningar som kan hindra prestanda.

Här är en visuell representation av hur det fungerar:

Fönstrets gränser kan anpassas efter det specifika problemets krav.

Implementera algoritmen för skjutfönster i Go

Du kan använda ett populärt kodningsproblem för att lära dig hur algoritmen för glidfönster fungerar: att hitta den största summan av en undermatris med en given längd.

Syftet med detta provproblem är att hitta underarrayen av storlek k vars element summerar till det största värdet. Lösningsfunktionen tar in två parametrar: inmatningsmatrisen och ett positivt heltal som representerar k.

Låt provmatrisen vara nums, som koden nedan visar:

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

Och låt sub-arraylängden vara k, med värdet 3:

k := 3

Du kan sedan deklarera en funktion för att hitta den maximala summan av sub-arrayer med längden k:

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

Du kanske tror att fönstret måste vara en array som lagrar kopior av målelementen. Även om det är ett alternativ, fungerar det dåligt.

Istället behöver du bara definiera gränserna för fönstret för att hålla reda på det. Till exempel, i det här fallet kommer det första fönstret att ha ett startindex på 0 och ett slutindex på k-1. När du skjuter fönstret uppdaterar du dessa gränser.

Det första steget för att lösa detta problem är att få summan av den första undermatrisen av storlek k. Lägg till följande kod till din funktion:

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

Koden ovan deklarerar de nödvändiga variablerna för algoritmen och hittar summan av det första fönstret i arrayen. Den initieras sedan maxSum med summan av det första fönstret.

Nästa steg är att skjut fönstret genom att iterera genom nums array från index k till slutet. I varje steg av att skjuta fönstret:

1. Uppdatering fönstersumma genom att lägga till det aktuella elementet och subtrahera elementet vid fönsterStart.
2. Uppdatering maxSum om det nya värdet av fönstersumma är större än det.

Följande kod implementerar det skjutbara fönstret. Lägg till den i maximumSubarraySum fungera.

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

När slingan är klar har du den största summan in maxSum, som du kan returnera som resultatet av funktionen:

return maxSum

Din fullständiga funktion bör se ut så här:

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 definiera en huvudfunktion för att testa algoritmen med hjälp av värdena på nums och k från tidigare:

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

Utgången i detta fall blir 19, som är summan av sub-arrayen [4, 8, 7], som är den största.

Du kan nu tillämpa samma teknik på liknande problem, även på andra språk, som att hantera upprepade element i ett fönster med en Java hash karta, till exempel.

Optimala algoritmer resulterar i effektiva tillämpningar

Denna algoritm står som ett bevis på kraften i effektiva lösningar när det kommer till problemlösning. Det skjutbara fönstret maximerar prestanda och eliminerar onödiga beräkningar.

En gedigen förståelse för algoritmen för glidfönster och dess implementering i Go utrustar dig för att hantera verkliga scenarier när du bygger applikationer.